约瑟夫环 数学解法

题目

【约瑟夫环】

这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。

例如，0,1,2,3,4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是2,0,4,1，因此最后剩下的数字是 3。

数学方法推导

解决约瑟夫环问题，我们采用倒推，我们倒推出：最后剩下的这个数字，在最开始的数组中的位置。

剩下最后一个数字（简称“它”）的时候，总个数为 1，它的下标pos = 0。
那么它在上一轮也是安全的，总个数为 2，它的下标 (0+m)%2；

（解释：在上一轮中，它前面的数字（即红色的数字，下标为 m-1）被移走了；因此它的下标是m；由于是环，因此需要%2）

那么它在上上轮也是安全的，总个数为3，它的下标 ((0+m)%2+m)%3；
那么它在上上上轮也是安全的，总个数为4，它的下标 (((0+m)%2+m)%3+m)%4；
…
那么它在游戏开始的第一轮也是安全的，总个数为n，它的下标 pos就是所求。
即如果从下向上反推的时候：假如它下一轮的下标为pos，那么当前轮次的下标就是：(pos+m)%当前轮次的人数。

最后，由于给出的数字是nums = 0,1,2,…,n-1，即nums[i] = i，因此找出下标 [公式] 就相当于找到这个数字。

解决约瑟夫环的代码

#include<iostream>
#include<list>
using namespace std;

int main(){
    int m,n;
    cin >> n >> m;
    int idx = 0;
    for(int i = 2; i <= n; ++i){
        idx = (idx + m)% i;
    }
    cout << idx + 1 << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

该数学方法的进阶应用

【报数游戏】100个人围成一圈，每个人有一个编码，编号从1开始到100。他们从1开始依次报数，报到为M的人自动退出圈圈，然后下一个人接着从1开始报数， 直到剩余的人数小于M。请问最后剩余的人在原先的编号为多少？

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int m;
    cin >> m;
    vector<int> cap(m - 1,0);
    for(int i = 0; i < m - 1;++i){
        cap[i] = i;
    }
    for(int i = m; i <= 100; ++i){
        for(int j = 0; j < m - 1; ++j){
            cap[j] = (cap[j] + m) % i;
        }
    }
    for(int i = 0; i < m - 1; ++i){
        cout << cap[i] + 1 << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21