有关约瑟夫环问题(Josephus Game)

n个小朋友手拉手围成一个圈,给定一个数字m。

这时以第一个小朋友为起点开始报数,数到m的小朋友出列;

m的下家为新的起点,开始重新开始报数;

如此反复,一直到剩下最后一个小朋友。

请问如何可以求得这最后的小朋友是谁?

最容易想到的就是写个程序直接模拟游戏的全过程

动态规划的解法要更加的优雅简单

定义方法:getSurvive(n, m) 返回(n,m)的最终生还者编号。

1
2
3
4
5
6
7
8
9
10
11
12
def getSurvive(n, m):
if n == 1:
return 0
else:
return (getSurvive(n - 1, m) + m) % n