约瑟夫问题(Josephus Problem)

π.Science 2021-11-23 88 次浏览 次点赞

最近《鱿鱼游戏》(Squid Game)很火。《鱿鱼游戏》是由Netflix出品的惊悚悬疑电视剧,讲述了数百名为生活所困的人,为了456亿韩元的奖金参加了6个生死逃杀游戏的故事。

16330974723192.jpg

这种生死逃杀游戏在差不多两千年前古罗马也发生过。

一世纪罗马帝国的犹太历史学家弗拉维奥·约瑟夫(Titus Flavius Josephus)在自己的作品《The Jewish War》中写过一个故事:他和他的40个战友被罗马军队包围在洞中。由于犹太人宁愿自杀也不愿被俘,但约瑟夫可不想自杀,于是告诉大家围成一个圈,由第一个士兵开始报数,每数到三的人就必须自杀,然后由下一个士兵开始报数,直到所有人都自杀身亡。约瑟夫和同谋是最后两个留下的人,他们向罗马军队投降。约瑟夫把他的存活归因于运气或天意,他不知道是哪一个。实际上,《The Jewish War》没有这个机制的细节描述,以上只是其中一个较多提及的自杀版本(k=3)。

通过下面的转盘我们知道,最后两个留下的人一定是16号和31号。实际上,约瑟夫只是为自己和同谋选对了位置。

josephusProblem-1.jpg

后来这个故事被命名为约瑟夫问题(Josephus Problem)——N个人围成一圈,第一个人从1开始报数,报k的将被杀掉,下一个人接着从1开始报。如此反复,最后剩下一个,求最后的胜利者。

Carlos Fleitas设计了一个可视化程序,可以计算N(2,50)、k(2,50)的约瑟夫数排列。

20211121213132.png

约瑟夫问题是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又被称为约瑟夫环(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




本文由 PeakOneTemple 整理创作,参考 知识共享署名 3.0 协议,撰写及摘编内容仅反映个人观点和立场,如果任何可能的雇主与赞助者持有相同的意见,只是巧合;基于互联网链接的腐烂率,无法持续验证外部链接的真实有效性,不对可能的链接无效(linkrot)或者内容转移(Content Drift)负责。

圆周率文化坚持非功利写作和分享,但会有一些获利推荐,以及接受您的打赏,这都会鼓励我
感谢您的支持,我会持续给您山巅.一寺.一壶酒的独特视角!

还不快抢沙发

添加新评论