最近《鱿鱼游戏》(Squid Game)很火。《鱿鱼游戏》是由Netflix出品的惊悚悬疑电视剧,讲述了数百名为生活所困的人,为了456亿韩元的奖金参加了6个生死逃杀游戏的故事。
这种生死逃杀游戏在差不多两千年前古罗马也发生过。
一世纪罗马帝国的犹太历史学家弗拉维奥·约瑟夫(Titus Flavius Josephus)在自己的作品《The Jewish War》中写过一个故事:他和他的40个战友被罗马军队包围在洞中。由于犹太人宁愿自杀也不愿被俘,但约瑟夫可不想自杀,于是告诉大家围成一个圈,由第一个士兵开始报数,每数到三的人就必须自杀,然后由下一个士兵开始报数,直到所有人都自杀身亡。约瑟夫和同谋是最后两个留下的人,他们向罗马军队投降。约瑟夫把他的存活归因于运气或天意,他不知道是哪一个。实际上,《The Jewish War》没有这个机制的细节描述,以上只是其中一个较多提及的自杀版本(k=3)。
通过下面的转盘我们知道,最后两个留下的人一定是16号和31号。实际上,约瑟夫只是为自己和同谋选对了位置。
后来这个故事被命名为约瑟夫问题(Josephus Problem)——N个人围成一圈,第一个人从1开始报数,报k的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个,求最后的胜利者。
Carlos Fleitas设计了一个可视化程序,可以计算N(2,50)、k(2,50)的约瑟夫数排列。
约瑟夫问题是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又被称为约瑟夫环(Josephus Circle)。约瑟夫问题具有以下递归结构:
- f(1, k) = 1
- f(n, k) = (f(n - 1, k) + k-1) % n + 1
使用递归(recursive)的解决方案:Josephus problem | Set 1 (A O(n) Solution);还可以有使用循环列表(circular list)的解决方案:Josephus Circle implementation using STL list;它们以及这个链接都列出了使用C++、Java、Python3、C#和Javascript模拟解法的过程。
以下是Python的递归解法。
def josephus(n, k):
if (n == 1):
return 1
else:
return (josephus(n - 1, k) + k-1) % n + 1
n = 41
k = 3
print("The Josephus Position is ", josephus(n, k))
以下用Python列出约瑟夫数排列。
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
def create_linkList(n):
head = Node(1)
pre = head
for i in range(2, n+1):
newNode = Node(i)
pre.next= newNode
pre = newNode
pre.next = head
return head
n = 41
k = 3
if k == 1:
print (n)
else:
head = create_linkList(n)
pre = None
cur = head
while cur.next != cur:
for i in range(k-1):
pre = cur
cur = cur.next
print (cur.value)
pre.next = cur.next
cur.next = None
cur = pre.next
print (cur.value)
解析资源
两个视频教程:威斯康星大学麦迪逊分校Daniel Erman主讲约瑟夫问题,以及中国人民大学附属中学物理教师李永乐主讲约瑟夫问题。维基百科词条,以及一个Javascript实现的约瑟夫计算器。
约瑟夫问题的变种
李永乐在约瑟夫问题一节中讲道,日本“继子立”问题指若干财产继承人围立一圈,按特定顺序淘汰一些人,而让另一些人继承财产,日本江户时代的数学家关孝和对继子立有过一般性讨论;中国清朝数学家方中通在《数度衍》中也描述过类似的问题。
17世纪的法国数学家加斯帕在《数目的游戏问题》中讲了这样一个故事:15个教徒和15个非教徒在深海上遇险,必须将一半的人投入海中,其余的人才能幸免于难,于是想了一个办法:30个人围成一圆圈,从第一个人开始依次报数,每数到第九个人就将他扔入大海,如此循环进行直到仅余15个人为止。问怎样排法,才能使每次投入大海的都是非教徒。
我们尝试用上述第二个Python程序列出约瑟夫数排列f(n=30, k=9),把非教徒安排在前15个位置即可。👍
9、18、27、6、16、26、7、19、30、12、24、8、22、5、23、
11、29、17、10、2、28、25、1、4、15、13、14、3、20、21
「圆周率文化是个人站点,重点分享科技、商业、医学及人文资讯。
「圆周率文化得到中国汽车绞盘网的支持,深表感谢。中国汽车绞盘网业务始创于2001年,为越野车、清障车、消防车、军用车、特种车及工程应用等拖曳、救援场景提供手动绞盘、电动绞盘、液压绞盘和技术支持。