用循环链表解决约瑟夫问题的代码
时间: 2023-09-18 14:13:57 浏览: 57
下面是使用双向循环链表解决约瑟夫问题的代码示例,其中n表示总人数,m表示要出圈的数字,last表示最后一个剩下的人的编号:
```python
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def josephus(n, m):
# 初始化循环链表
head = Node(1)
cur = head
for i in range(2, n+1):
node = Node(i)
cur.next = node
node.prev = cur
cur = node
cur.next = head # 建立循环
# 开始遍历链表
cur = head
while cur.next != cur:
# 找到第m个结点
for i in range(m-1):
cur = cur.next
# 删除第m个结点
cur.prev.next = cur.next
cur.next.prev = cur.prev
cur = cur.next
return cur.val
last = josephus(7, 3)
print("最后一个剩下的人的编号为:", last)
```
在上述代码中,我们首先创建了一个含有n个结点的双向循环链表,然后从链表的头部开始遍历,每次遍历m个结点,将第m个结点从链表中删除,直到链表中只剩下一个结点为止。最后返回最后一个剩下的人的编号。