The Josephus Problem（约瑟夫问题）

1. 约瑟夫问题¶

约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

——约瑟夫问题 -Wikipedia

现在给定人数 n、起点 1、方向顺时针、要跳过的数字 1，求应该选择初始圆圈中的什么位置以避免被处决？

2. 模拟筛选的过程¶

最简单的解法，即按问题的描述直接翻译成程序求解。使用数组或单向循环链表来模拟筛选的过程：

def josephus(n):
    circle = list(range(1, n + 1))  # 使用数组
    i = 0
    while n > 1:
        circle.pop((i + 1) % n)
        i = (i + 1) % n
        n -= 1
    return circle[0]

有没有更简单的解法呢？

有。

3. 解析解¶

解析解又叫公式解。在 Online Judge 系统中，如果你看到排行榜上某解法的运行时间比你的循环/递归版本快几个数量级，那么很有可能是他发现了解析解。

在上述的过程中，每一圈筛选过后，人数都会减半。

1. 如果 n 为偶数，那么第一圈筛选过后，剩下的位置 p 上的人的编号 q = 2p - 1，接下来一圈会跳过 1 号。

2. 如果 n = 2^m，那么每一圈筛选后，1 号都会被跳过。此种情况下，1 号成为驻点，会最终留下。

推广到一般情况，n 可以表示成 n = 2^m + k 的形式，其中 m = floor(log(n))，则 0 <= k < n/2。

此时，当去掉 k 名成员后，这个问题就变成了上述第二条的情况 2^m，刚才去掉的第 k 名成员的下一位成为驻点，会最终留下。

由于：

1. k < n/2，而首轮筛选就会去掉 n/2 个人，则第 k 个被去掉的人在第一轮就可以找到，编号为 2k。
2. 他的下一位，2k + 1 成为驻点，最终留下。

因此，最终留下的人编号为 s = 2k + 1，其中 n = 2^m + k ， m = floor(log(n))，

化简得 s = 2(n - 2^( floor(log(n)) )) + 1。

4. 解的二进制表示¶

上述结果用二进制表示更加简洁，

由于 n = b_mb_m-1b_m-2...b₀ ，

则 k = b_m-1b_m-2…b₀，

幸存者编号 s = 2k + 1 = b_m-1b_m-2…b₀1 = b_m-1b_m-2...b₀b_m。

即将 n 二进制中首位移到末尾即可。

5. 新的问题¶

1. 最后留下的倒数第二个人的编号是多少？
2. 当间隔不为 1 的时候，最终幸存者编号是多少？