Question

C语言 猴子大王 Josephus

int Joseph(int M,int N)
{
int i, k, idx;
for(i=2,k=0;i<=M;i++)
k=(k+N)%i;

if( (idx=(++k)%M)==0 )
idx = M;

return idx;
}
M只猴子统一编号,围成一圈,从第一只开始报数1,2,3,报到N退出,下一只继续报数1,2,3找出最后留下的那只猴即为大王,这里的M,N为方法的参数.
请高手解释以上方法，重点是for循环的思路

Answer 1

今天才见识到Josephus还有这么好的算法，这是我看到的一个讲解过程，只不过讲解的是M=3的情况，不过看完之后恍然大悟了。
有N个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

Input 输入一个整数N(2 < N <50 )

Output 输出剩下的人的编号

Sample Input 4 Sample Output 1

分析：
1）当有人出局之后，可以用给原来的编号赋新值。因此，当到第二轮时，1和2分别变成n+1和n+2，3已经出局，所以4和5分别变为n+4-1=n+3和n+5-1=n+4，6已经出局，。。。，以此类推；

3k+1和3k+2分别变成n+3k+1-k=n+2k+1和n+3k+2-k=n+2k+2。
2）在上述编号方式下，第k个出局的人的号码一定是3k，所以最后一个出局的人的最终号码为3n。
求解：
3）如果编号N>n，则编号为N的人此前一定有另一个编号。(因为最初的编号是1...n)我们如何求编号N对应的前一个编号呢？因为N=n+2k+1或N=n+2k+2，因此k=(N-n-1)/2。前面的编号分别为3k+1和3k+2，（N=n+2k+1或N=n+2k+2得1=N-n-2k，2=N-n-2k）即有3k+(N-n-2k)=k+N-n,这就求得了编号N对应的前一个编号k+N-n=(N-n-1)/2+N-n。