最近《鱿鱼游戏》(Squid Game)很火。《鱿鱼游戏》是由
这种生死逃杀游戏在差不多两千年前古罗马也发生过。
一世纪罗马帝国的犹太历史学家弗拉维奥·约瑟夫(Titus Flavius Josephus)在自己的作品《The Jewish War》中写过一个故事:他和他的
通过下面的转盘我们知道,最后两个留下的人一定是

后来这个故事被命名为约瑟夫问题(Josephus Problem)——N
Carlos Fleitas
约瑟夫问题是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又被称为约瑟夫环(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;它们以及这个链接都列出了使用
以下是
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))
以下用
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)
解析资源
两个视频教程:威斯康星大学麦迪逊分校
约瑟夫问题的变种
李永乐在约瑟夫问题一节中讲道,日本
17
我们尝试用上述第二个👍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