考虑这样一个问题，有 个人，标号从
到
，从第一个人开始数，杀死数到
的人，然后下一个人重新开始数。
问：最后死的人是几号？
假设有 个人，将没有被杀的人重新编号，那么，杀人情况如下表所示
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|
| 11 | 12 | 13 | 14 | 15 | 16 | 17 | |||
| 18 | 19 | 20 | 21 | 22 | |||||
| 23 | 24 | 25 | |||||||
| 26 | 27 | ||||||||
| 28 | |||||||||
| 29 | |||||||||
| 30 |
第一轮杀了 号、
号和
号，
号变成了
号，
号变成了
号等等。
我们可以发现如下性质：
- 每一轮被杀的了人的编号是
的倍数，且第
个被我要的杀的人的当前轮的编号是
。
-
号，那么
号和
号是暂时安全的，因此需要对其编号，其新的编号为
和
，因为杀完
个人。
因此对于第 个被杀死的人，他死亡时编号为
，又因为
或
，显然
，而上一轮的编号为
。
因此可以用下面的方法算出最后一个死的人的原编号
int J(int n) {
int i = 3 * n;
while (i > n) i = (i - n - 1) / 2 + i - n;
return i;
}
如果用 来替换
，发现原迭代式变为
则可以用以下方法求出上面要求的结果
int J(int n) {
int i = 1;
while (i <= 2*n) i = ceil(3.0 * i / 2);
return 3*n + 1 - i;
}
当然，如果循环节的个数不为 ，而是为
，可以用相同的方法证明，有类似的结论
int J(int n, int q) {
int i = 1;
while (i <= (q - 1) * n) d = ceil((double)q * i / (q - 1));
return q*n + 1 - i;
}
