目錄

1. 問題

2.? 思路

3. 代碼?

4. 運行

---

1. 問題

????? 本題即為典型的約瑟夫問題，通過遞推公式倒推出問題的解。原始問題是從n個人中每隔m個數踢出一個人，原始問題變成從n-1個人中每隔m個數踢出一個人……

示例 1：

輸入: n = 5, m = 3
輸出:?3

示例 2：

輸入: n = 10, m = 17
輸出:?2

2.? 思路

????? 第一行表示每個人的下標，現在要從11個人中刪除報數為3的人，從圖中可以可看出最后7是勝利者。分析其中的規律：

第一輪中，11個人中勝利者7的角標是6；

第二輪中，10個人中勝利者7的角標是3；

第三輪中，9個人中勝利者7的角標是0；

第四輪中，8個人中勝利者7的角標是6；

第五輪中，7個人中勝利者7的角標是3；

第六輪中，6個人中勝利者7的角標是0；

第七輪中，5個人中勝利者7的角標是3；

第八輪中，4個人中勝利者7的角標是0；

第九輪中，3個人中勝利者7的角標是1；

第十輪中，2個人中勝利者7的角標是1；

第十一輪中，1個人中勝利者7的角標是0；

?

從第十一輪中倒推到第一輪：

從第十一輪中推出第十輪的角標數，f(2,3) = (f(1,3) + m) % 2 =(0+3) % 2 = 1

從第十輪中推出第九輪的角標數，f(3,3) = (f(2,3) + m) % 3 =(1+3) % 3 = 1

從第九輪中推出第八輪的角標數，f(4,3) = (f(3,3) + m) % 4 =(1+3) % 4 = 0

懶得寫了…….

?

結論：從n個人中每隔m刪除一人，遞推公式為 f(n,m) = (f(n-1,m)+m)? %? n

3. 代碼?

#include <iostream>
using namespace std;class Solution {
public:// n表示多少個人，m表示隨機數int LastRemaining_Solution(int n, int m){// 特殊輸入if (n == 0 || m < 0) return -1;// 遞推公式計算int res = 0;for (int i = 1; i <= n; i++){res = (res + m) % i;cout << res << endl;}return res;}
};
int main()
{int n = 11;int m = 3;Solution solution;solution.LastRemaining_Solution(n, m);return 0;
}

4. 運行