查看文章 |
约瑟夫问题（Josephus问题）的递归解法、递推解法、O(n)解法
2008-07-23 15:04
n个人在一个圆桌上吃饭，每m个人杀掉一个，直到最后剩下一个人。 这就是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 以及一个程序： //函数接收n和m，返回最后出圈的是第几个人 /*e.g. yuesefu(5,2)=3 yuesefu(2,100)=1*/ int yuesefu(int n,int m) { int i,r=0; for (i=2;i<=n;i++) r=(r+m)%i; return r+1; } |
最近读者：