约瑟夫算法

约瑟夫算法：n个人围成一圈，每人有一个各不相同的编号，选择一个人作为起点，然后顺时针从1到k数数，每数到k的人退出圈子，圈子缩小，然后从下一个人继续从1到k数数，重复上面过程。求最后推出圈子的那个人原来的编号。

要模拟整个过程，不仅程序写起来比较烦，而且时间复杂度为O(nm)，当n,m非常大时，几乎是没有办法在短时间里出结果的，先把问题变一下，并不影响原意：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数，求最后的人的编号。

我们知道第一个人（编号一定是m%(n-1))出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）：

k,k+1,k+2,...,n-2,n-1,0,1,2,...,k-2并且从k开始报0。

现在我们把他们的编号做一下转换：

k -->0

k+1 -->1

k+2 -->2

...

k-2 -->n-2

k-1 -->n-1

变换后就完完全全成为了(n-1)个人报数的子问题了，假如知道这个问题解：例如x是最后那个人，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？变回去的公式很简单，即：

x'=(x+k)%n

如何知道n-1个人报数的问题的解？对，只要知道n-2个人的解就行了，n-2个人的解呢？当然先求n-3的情况...

令f[i]表示i个人报m退出最后那个人的编号，最后的结果自然是f[n]

地推公式：

f[1]=0;

f[i]=(f[i-1]+m)%i;（i>1)

有了这个公式，要做的就是从n-1顺序算出f[i]的数值，最后结构是f[n]，因为实际生活中编号总是从1开始的，我们输出f[n]+1，由于是逐渐递推，不要保存每个f[i]，因此程序很简单：

#include

int main(void)

{

int i;

int s = 0;

int n;

int m;

scanf("%d%d", &n, &m);

for (i = 2; i <= n; i++)

{

s = (s + m) % i;

}

printf("最后的人是: %d\n", s + 1);

return 0;

}