问题描述
历史典故：
据说著名犹太历史学家 Josephus有过以下的故事：
在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，
于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。
然而Josephus 和他的朋友并不想遵从。
首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。
问题是，给定了和，一开始要站在什么地方才能避免被处决？
Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
问题描述
约瑟夫环：已知n个人(以编号1，2，3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列;他的下一个人又从1开始报数，数到m的那个人又出列;依此规律重复下去，直到圆桌周围的人全部出列。最优一个出列的为获胜者W
example:
N = [1,2,3,4,5,6]； M = 3；则出列顺序为：3,6,4,2,5,1；所以获胜者W=1
思路1
递归解法：
import copy
def rescue_jose(N,M):
orders = []
def rescue(N,M): # 每一次出列，循环一次
if not N: # 递归终止条件
return
MM = M
while MM > len(N):
MM -= len(N)
# print(MM)
orders.append(N[MM-1])
rescue(N[MM:] + N[0:MM-1],M)
rescue(N,M)
return orders
orders = rescue_jose(N,M)
print(orders)
时间复杂度较高
思路2--一种特殊情况
固定M=2
通过代码生成大量case/data
分析规律
M = 2
for i in range(1,42):
res[i] = rescue_jose(list(range(1,i+1)),M)[-1]
for k,v in res.items():
print(k,v)
1 1
2 1
3 3
4 1
5 3
6 5
7 7
8 1
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1
17 3
当M = 2
设n为所有人的人数
当n = 2^a 则获胜的肯定是1
n = 2^a + l 则获胜者是 2*l + 1
思路2参考：
[互砍惨案！约瑟夫斯问题 @圆桌字幕组](https://www.bilibili.com/video/av7885066)
思路3
[1, 2, 3, 4, 5, 6]
[4, 5, 6, 1, 2]
[1, 2, 4, 5]
[5, 1, 2]
[5, 1]
[1]
最终获胜者W的位置变化
0->3->0->1->1->0
数学可表示为：
(f(n)-M+N)%N
逆推：
(f(n)+M)%N
根据递推关系求解
#include/*
序列:0,1,2,3,4...n-1
n 表示当前序列长度
ｆ[n] 胜利者的编号
f[1] = 0
(f[n-1]+m)%n
*/
void whoWin()
// 求出最后的胜利者的序号
{
int n, m, i, s = 0;
printf ("N M = ");
scanf("%d%d", &n, &m);
for (i = 2; i <= n; i++)
{
s = (s + m) % i;
printf("%d\n",s);
}
printf ("\nThe winner is %d\n", s+1);
}
int main()
{
whoWin();
}
网友评论