关于约瑟夫环问题的思考（数组做法）

这几天做题时碰见了一个很有意思的问题，也是一个十分经典问题—约瑟夫环问题。问题很简单，就是有n个人围成一个圈，每隔m个人就自杀一个，直到剩下最后一个人为止，问最后剩下的最后一个人是谁？
来看具体的题目描述：这个是C语言网的ACM训练题----出圈

思路：这道题就是让你求解约瑟夫环问题，我在看到这道题时，第一反应是用数组做，用数组来构造一个环。实际上用数组来做没有任何问题，但我却碰到了一个使用for的一个坑，直接影响到了我整道题目，接下来我把代码分享出来，希望大家不要再踩这个坑
错误代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4;
int a[maxn];
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
    //这部分代码我是初始化一个1,2,3,4,5....的数组，他们的下标从0开始分别为0,1,2,4,...
    a[0] = 1;
    for(int i = 0;i<=n-2;i++){
        a[i+1] = a[i]+1;
    }
    //cnt使用来计数，当cnt==m时来选择剔除的的人
    int cnt =0;
    int sum = 0;//剔除的人数，当剔除了n-1个人时，就停止操作，循环的结束条件
    //开始清人，因为我在循环体内重新定义了i，所以这里我把i定义在外面，防止重复定义
    int i = 0;
    for(;i<n;i++){
        //剔除的数组元素，我把他赋值为-1
        if(a[i]!=-1){
            cnt++;
        }
        //隔了m个人，且没有被剔除出去，就把他赋值为-1把他剔除出去，cnt归零重新计数，sum加1
        if(cnt==m&&a[i]!=-1){
            a[i] = -1;
            cnt = 0;
            sum++;
        }

        if(i==n-1){
            //这是一个环，我们遍历完数组，还要重头开始（注意）
            i = 0;
        }
       //循环结束条件，当剔除了n-1个人，还剩一个人时，结束循环
       if(sum==n-1){
            break;
        }
}
//输出打印不是-1的，就是剩下的那个人的值
for(int i = 0;i<n;i++){
    if(a[i]!=-1){
        printf("%d\n",a[i]);
        break;
    }
}
}
return 0;
}

看到这儿，你可以发现其实思路是没问题的，但输出的结果是这样的

我们不管输入什么数据，它给我们的结果都是1，始终都是第一个人最后活下来，那究竟是为什么嘞？
首先我们要明白在循环体内重新对循环变量进行赋值，是有个特别要注意的事项：

int i = 0;
for(;i<n;i++){
   if(i==n-1){
        i = 0;
   }
}

这段代码就是我们用数组构造一个环的关键代码，当程序遍历完数组的最后一个元素时，我们把i重新赋值为0, 使它能像一个环一样能够被重复访问，这个基本的思路是没有问题的。但这里有个细节就是我重新赋值为0，进入下一层for循环时，满足我们for循环的条件，是要先执行i++的。换句话说，我们想要下一次的遍历从下标0开始，但实际上它是从下标1开始的，第一个数字在每次循环遍历都是被排除在外的，那么在约瑟夫环中最后剩下的肯定都是第一个元素。弄清楚错误的原因，我们不妨在初始化数组时就留一手（留一个缓冲位)，如图：
以在5个人中隔3个人就剔除出去为例（n = 5,m =3）

我们在初始化数组时，就留出一个空位，也就说我们从下标1开始赋值，下标0的位置来做一个缓冲的作用。 我们遍历完最后一个元素后，将循环变量重置为下标0, 同样程序还是会先进行i++的操作，那么i 就等于1了，而我们的数字不就是从下标1赋值的吗，刚好合适，就没有把任何元素都排除在外了。
更改后的环代码：

//从下标1开始赋值
    for(int i = 1;i<=n;i++){
        a[i] = i;
    }
//初始的时候还是要从下标1开始的
int i = 1;
for(;i<=n;i++){
   if(i==n){
        i = 0;
   }
}

这样一来，我们对于这个问题数组做法最坑的一部分就解决了（至少我是这么认为），接下来无非就是用代码模拟这个题目要求的步骤，思路很简单，给出完整的AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4;
int a[maxn];
int main(){
int n,m;
while(scanf("%d %d",&n,&m)!=EOF){
    for(int i = 1;i<=n;i++){
        a[i] = i;
    }
    int cnt =0;
    int sum = 0;//剔除的人数
    //开始清人
    int i = 1;
    for(;i<=n;i++){
        //被剔除出去的人已经不算在环里
        if(a[i]!=-1){
            cnt++;
        }
        //隔了m个人，开始剔除一个人
        if(cnt==m&&a[i]!=-1){
            a[i] = -1;
            cnt = 0;
            sum++;
        }

        if(i==n){
            //这是一个环
            i = 0;

        }
      //当剔除到只剩下一个人时，就退出循环
       if(sum==n-1){
            break;
        }
}
for(int i = 1;i<=n;i++){
    if(a[i]!=-1){
        printf("%d\n",a[i]);
        break;
    }
}
}
return 0;
}

根据这个题目，我们可以看出其实在很多题目中，隐藏了很多的细节，很多题AC不了，估计就是这些细节导致的，所以我们一定要注重细节上的东西。