服务器时间: 2014-10-02 20:24
分享到:文章主题: [转载] Josephus问题
LiangZi楼主
2*1500=2
等级
顾问团
文章
12457

发信人: LiangZi (感受那幸福过后孤独地出发), 信区: Competition
标  题: [转载] Josephus问题
发信站: 碧海青天 (Fri Apr 11 13:52:05 2003), 站内信件
  
【 以下文字转载自 IQrace 讨论区 】
【 原文由
LiangZi 所发表 】
  
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
--
⿵⿺⿶⿹⿸⿹⿺⿵⿺⿹⿵⿺⿵⿺⿵⿺⿵⿹⿵⿹⿺⿵⿹⿵⿺⿺⿶⿵⿹⿺⿵⿹⿵
⿺⿵
⿺⿶⿵⿵⿹⿵⿵⿵⿺⿵⿹⿵⿺⿵⿵⿺⿵⿹⿺⿵⿹⿵⿺⿶⿹⿵⿵⿺⿵⿹⿵
⿺⿵⿵⿵⿺⿵⿴⿺⿺⿹⿹⿵⿺⿵⿵⿺⿵⿹⿺⿵⿵⿹⿺⿵⿵⿵⿹⿺⿵
⿹⿺⿵
⿹⿺⿵⿺⿵⿵⿵⿵⿵⿺⿵⿵⿵⿵⿺⿵⿹⿵⿹⿺⿵⿹⿵⿺⿶⿵⿹⿺⿵⿹⿵⿺
⿴⿺
⿸⿶⿵⿵⿺⿵⿹⿵⿵⿵⿵⿺⿵⿹⿺⿵⿹⿵⿺⿵⿹⿵⿺⿵⿵⿹⿵⿺⿵
⿵⿷⿶
⿹⿵⿵⿺⿵⿵⿵⿺⿶⿴⿵⿵⿺⿵⿹⿹⿺⿵⿹⿵⿺⿵⿺⿵⿹⿵⿶⿵
  
※ 来源:.碧海青天 bbs.dlut.edu.cn.[FROM: 210.30.109.118]
--
※ 转载:.碧海青天 bbs.dlut.edu.cn.[FROM: 210.30.109.118]

返回顶部
  • 主题数:1 分页:
    1. 1