问题描述:
Josephus 问题是一个古老而著名的问题，最早的记载来自犹太历史学家弗拉维奥·约瑟夫斯（FlaviusJosephus），他在犹太战争中被罗马军队包围，为了不被俘虏，他和他的 39 个战友决定自杀，但是他们并不想自己亲手杀死自己，于是决定站在一个圆圈里，从一个人开始，每报数到第 14 个人，第 14 个人就会被杀掉，然后从下一个人开始重新报数，直到最后只剩下一个人，那个人就可以幸存。
这个问题的一般形式是：有 n 个人围成一圈，从第一个人开始报数，数到第 k 个人，然后第 k 个人出列，再从出列的下一个人开始重新报数，如此循环，直到最后只剩下一个人。
问题解决
递推关系式
n 为人数, k 为轮数
令 f(n, k)表示 n 个人中最后幸存者的编号，Josephus 问题的递推关系式为：
f(n, k)=((f(n-1, k)+k)mod n)+1
其中，f(1, k)= 1。这个递推关系式描述了每一轮中幸存者的编号与上一轮中的关系。
递推推导
假设轮数 k = 2, 列表如下
| 人数 | 幸存者编号 | 与上一轮关系 |
|---|---|---|
| 1 | 1 | (上一轮幸存者编号+ 轮数)%本轮人数 |
| 2 | 1 | (1+2)%2 = 1 |
| 3 | 3 | (1+2)%3 = 3 |
| 4 | 1 | (3+2)%4 = 1 |
| 5 | 3 | (1+2)%5 = 3 |
| 6 | 5 | (3+2)%6 = 5 |
| 7 | 7 | (5+2)%7 = 7 |
| 8 | 1 | (7+2)%8 = 1 |
| 9 | 3 | (1+2)%9 = 3 |
| 10 | 5 | (3+2)%10 = 5 |
| 11 | 7 | (5+2)%11 = 7 |
| 12 | 9 | (7+2)%12 = 9 |
| 13 | 11 | (9+2)%13 = 11 |
| 14 | 13 | (11+2)%14 = 13 |
| 15 | 15 | (13+2)%15 = 15 |
| 16 | 1 | (15+2)%16 = 1 |
| 17 | 3 | (1+2)%17 = 3 |
| 18 | 5 | (3+2)%18 = 5 |
| 19 | 7 | (5+2)%19 = 7 |
| 20 | 9 | (7+2)%20 = 9 |
逻辑解释
我们要讨论的是，从 n 个人中 选择出 幸存者 与 从 n-1 个人中选择出幸存者之间的关系
简单情况
以11个人和10个人，按照k=2来看
根据表格，我们已经知道, n=10时 ,幸存者为编号5
我们可以将n=11 的问题转换成n=10的问题:
n=11时，从第一个被杀掉的人开始报数，这个问题就是n=10的问题了。
首先，被杀掉的第一个人是编号2
那么，剩下的人就是从编号3开始报数，n=10的问题了
参考一开始那个n=10的问题，我们可以推出幸存者为编号7
将n=11的问题转换成n=10的问题时,编号之间的关系?
我们可以看到,大多数编号之间的关系为 +k， 我们可以 得出一个**不完全准确**的结论:
n=x的幸存者编号为 n=x-1的幸存者编号+ k
即 f(n,k) =f(n-1,k) +k
特殊情况
考虑n=16 和n=15 、k=2的情况
n=15时，幸存者为编号15:
将n=16的问题转换成n=15的问题
幸存者为编号1
n=16和n=15问题并不是完全直接转化的。
数量的不同代表着他们每次从编号第一个到编号最后一个所需的次数是不同的:
即，虽然理论上,问题转换后,幸存者为编号16的下一个编号17，但很显然不是，编号16报完数之后进入下一轮循环了，从编号1 开始，编号1 为幸存者。
此时就需要用到模运算了。
它们之间的关系如下:
f(n, k)=((f(n-1, k)+k)mod n)+1 (注:没有编号为0的情况,都是从编号1 开始,因此最后要加一)
代码实现
python代码如下:
def josephus(n, k):
if n == 1:
return 1
else:
return ((josephus(n-1, k) + k -1) % n) + 1
文章参考:
博客地址: qwrdxer.github.io
欢迎交流: qq1944270374
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1944270374@qq.com