约瑟夫问题.txt

ACM解题报告

Josephus问题
约瑟夫问题

设n个人围成一圈，标号为0..n-1，从第一个人开始依次从1到k循环报数，当报到
k的时候此人出圈。设J(n, k, i)表示第i个出圈的人的标号。

定理一:
J(n, k, 1) = (k-1) mod n, (n >= 1, k >= 1)             ………… （1）

证明：
由定义直接得证。                Q.E.D.

定理二：
J(n+1，k, i+1) = (k + J(n, k, i)) mod (n+1),  (n >= 1, k >= 1, 1<= i 
<= n) ………… （2）

证明：
设J(n, k, i) = g，因此如果有n个人，从0开始报号，第i个出圈的标号为g。现在
考虑J(n+1, k,i+1)，因为J(n+1, k, 1) = (k-1) mod (n+1)，即第一步的时候删
除数字(k-1) mod (n+1)，第二步的时候从数字k开始数起。因而问题变为了找到剩
下的n个数字中从k开始数起被删除的第i个数字（注意这时(k-1) mod (n+1)已经被
删除了），而这恰好就是(g+k) mod (n+1)，(2)成立。                             
   Q.E.D.


根据（2），很容易求得n个数里面第i个出圈的数。


对于k = 2, 3的情况，直接可以推导出公式来。但是对于k>=4的情况，还没有推导
出公式来，目前最好的算法是一个根据估计J(n, k, i)上下界的快速算法。


更具体的分析，参见
[1] Lorenz Halbeisen, The Josephus Problem, 1994
[2] Woodhouse, D. , The extended Josephus problem, Rev.Mat. Hisp.-Amer.
(4) 33 (1973), 207-218
[3] Robinson, W. J.，The Josephus problem, Math. Gazette 44 (1960), 
47-52
[4] Jakobczyk, F. , On the generalized Josephus problem, Glasgow Math.
J.14(1973), 168-173