C语言算法
约瑟夫环问题.有n个人围成一个圈,1~3循环报数,报3的出列,问最后剩下的是谁.
#include <stdio.h>
void main()
{
int n, s = 0;
scanf("%d", &n);
for (int i = 2; i <= n;++i)
{
s = (s + 3) % i;
}
printf("%d\n", s+1);
}
请问其数学原理是什么?
[解决办法]
楼主，详见百度百科，约瑟夫环的Josephus(约瑟夫)问题的数学方法
网址http://baike.baidu.com/view/717633.htm#4
[解决办法]
LZ可以把这个圈圈变成一条线，但是线的结尾和开头是隐式相连的；
每隔3就被剔除，剔除一个后，下一个被剔除的位置需要+1；
+1正是i增加的原因；
由此可得结果
[解决办法]
其实n * 3就是最后剩下的人到圈里第一个人的“绝对距离”，但是报一次数圈里就会少一个人所以要对i求余。最后一次对n求余前得到的就是最后离开的人和第一个人在原始圈中的距离，最后对n求余得到其序号。
可以自己画n * 3个格，然后2, 3, 4, 5, ..., n这么切开，再反过来把序号填进去基本上就能明白了
