圆圈中最后剩下的数字（约瑟夫环问题）
约瑟夫环
这是一道典型的约瑟夫环问题，而约瑟夫问题的一般形式是这样的：
约瑟夫问题是个有名的问题：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; //记录下标 //每杀一个人就将这个位置的数据置为-1 while (count_del < n) { if (index < n) { //如果当前位置是正数，就将这个位置置为-1，同时报一次数 if (nums[index] >= 0) { index++; count_m++; } //否则直接跳到下一个数 else index++; } //如果报的数等于m，就要杀index前的一个人，同时将报的数置0 if (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这一种情况：
我们应该清楚，当仅存一个人（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; }
