没有合适的资源?快使用搜索试试~ 我知道了~
约瑟夫的详细解释!顶顶顶
需积分: 9 1 下载量 54 浏览量
2010-06-19
21:20:00
上传
评论
收藏 1KB TXT 举报
温馨提示
试读
2页
详解约瑟夫问题,能让你更容易了解此问题。。。。。。。。
资源推荐
资源详情
资源评论
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)上下界的快速算法。
约瑟夫问题
设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)上下界的快速算法。
资源评论
gaoruowen
- 粉丝: 0
- 资源: 1
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功