约瑟夫问题规律讨论

考虑这样一个问题，有 个人，标号从 到 ，从第一个人开始数，杀死数到 的人，然后下一个人重新开始数。
问：最后死的人是几号？

假设有 个人，将没有被杀的人重新编号，那么，杀人情况如下表所示

第一轮杀了 号、 号和 号， 号变成了 号， 号变成了 号等等。

我们可以发现如下性质：

• 每一轮被杀的了人的编号是 的倍数，且第 个被我要的杀的人的当前轮的编号是 。
• 号被杀后，下一个被杀的人是 号，那么 号和 号是暂时安全的，因此需要对其编号，其新的编号为 和 ，因为杀完 号后相当于杀了 个人，还有 个人。

因此对于第 个被杀死的人，他死亡时编号为 ，又因为 或 ，显然 ，而上一轮的编号为 。
因此可以用下面的方法算出最后一个死的人的原编号

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;
}