圆圈中最后剩下的数字（约瑟夫环问题）
题目链接
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XargnT75-1692013002408)(C:\Users\HUASHUO\AppData\Roaming\Typora\typora-user-images\image-20230814173959060.png)]](https://img-blog.csdnimg.cn/aeed0de523f74e2abc5360d1af6ff8d5.png)
约瑟夫环
这是一道典型的约瑟夫环问题，而约瑟夫问题的一般形式是这样的：
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
如果我们采用暴力解法，采用计数的方式来求出最后存活的人，不难写出下面的代码：
int lastRemaining(int n, int m){//开辟数组，同时每个位置的值都初始化为下标int *nums = (int*)malloc(sizeof(int) * n);for (int i=0; i<n; i++)nums[i] = i;int ret; //返回值int count_del = 0; //记录已经删除人的个数int count_m = 0; //用来报数int index = 0; //记录下标//每杀一个人就将这个位置的数据置为-1while (count_del < n){if (index < n){//如果当前位置是正数，就将这个位置置为-1，同时报一次数if (nums[index] >= 0){index++;count_m++; }//否则直接跳到下一个数else index++;}//如果报的数等于m，就要杀index前的一个人，同时将报的数置0if (count_m == m){count_m = 0;nums[index - 1] = -1;count_del++;}//如果index越界，那么重新返回数组头if (index >= n)index = 0;//如果杀的人达到了n-1，那么就只剩下了最后一人，即index的位置if (count_del == n - 1)ret = nums[index];}//释放空间free(nums);return ret;
}
这种写法有一个特点：我们是在不断模拟整个杀人的过程，从第一个杀到最后一个，时间复杂度高达O(nm)，当n, m达到上万，上十万的时候，我们就无法在短时间内得到正确的结果了。我们应该清楚，题目只是让我们得到最后生还者的位置，而不是让我们模拟整个杀人的过程，因此我们应该将重点放在生还者的位置变化这一点上。
思路
我们可以将这个问题换一种说法：
N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。
我们定义F(n, m)表示幸存者的下标。
先来模拟一下n = 8, k = 3这一种情况：
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9tATrXa1-1692013002409)(C:\Users\HUASHUO\AppData\Roaming\Typora\typora-user-images\image-20230814190939484.png)]](https://img-blog.csdnimg.cn/38bf4c17da2746bc9c8851ad82151e36.png)
我们应该清楚，当仅存一个人（F(1,3)）时，这个人就是幸存者，而幸存者的下标一定是0。那么我们是否可以这样认为：我们可以从F(1,3)开始，知道每轮杀m个人后，反向递推，直到反向推出F(n,3)，即存在n个人时幸存者的位置。
事实上，就应该这样做：
我们假设当前幸存者的位置为index，上一轮幸存者的位置为pos，报数人数为m，上一轮的总人数为n，那么我们可以得到如下关系式：
pos = (index + m) % n
实现代码：
int lastRemaining(int n, int m){int pos = 0; //当只有一个人时，幸存者的下标为0//i表示上一轮的总人数for (int i=2; i<=n; i++) pos = (pos + m) % i;return pos;
}
