约瑟夫问题
1 问题描述
夫拉维.约瑟夫(Flavius Josephus)是一世纪著名的历史学家. 在犹太罗马战争期间, 他们 41名犹太反抗者被罗马人困在了洞穴中. 这些反抗者宁愿自杀也不愿被活捉, 他们决定围成 一个圆圈, 并沿着圆圈每三个人杀死一个人, 直到没有人剩下. 但是, 约瑟夫和他的一名朋友 不希望无谓地自杀, 于是他迅速地计算出他和朋友在这个险恶圆圈中的应该站的位置, 最后 生存了下来.
约瑟夫问题的一般描述如下: \(n\)个人围成一圈, 从第1个开始报数, 第\(k\)个人离开, 直到最后剩下\(m\)个人. 指定\(n, k\)时, 求\(m\)个人所在的位置.
2 问题分析
2.1 \(k=2, m=1\)的情况分析
2.1.1 暴力遍历
此问题的暴力遍厉十分简单:
- 构造数组\(candidate_array\), 初始化各项数值为\(1,2,...,n\), 初始化剩余人员数量\(left_candidate\)为n;
- 遍厉数组\(candidate_array\),
2.1.2 非封闭优化解
假设开始时有\(2n\)个人, 第一轮后剩下的是\(1, 3, 5, ..., 2n-3, 2n-1\). 同时3号是 下一个要离开的人. 对比分析\(n\)个人开始时的情况, 是每个人的号码加倍并减1:
\(J.1: J(2n) = 2J(n) - 1, n\ge 1 \)
再分析\(2n+1\)个人的情形, 第一轮后剩下的是\(1, 3, 5, ..., 2n-1, 2n+1\), 标号为1的 人是下一轮第一个离开人选. 1号离去后剩余\(n\)个人\(3, 5, ..., 2n-1, 2n+1\), 离去人 合计\(n+1\)个:
\(J.2: J(2n+1)=2J(n)+1, n\ge 1\)
对于\(n=1\)的情况, 分析可知\(J(1)=1\). 结核J.1和J.2, 已经可以用递归方式解决此问题.
例如: \(J(5)=2J(2)+1=3\) \(J(20)=2J(10)-1=2*(2*J(5)-1)-1=2*(2*3-1)-1=9\)
| n | 1 | 2 3 | 4 5 6 7 | 8 9 10 11 12 13 14 15 | 16 |
|---|---|---|---|---|---|
| J(n) | 1 | 1 3 | 1 3 5 7 | 1 3 5 7 9 11 13 15 | 1 |
\(J(2^m+l)=2l+1\)
请参考2.1.1.