使用双链表的python语言编程 30个人围成一圈,由第一个人开始,顺时针依次报数,数到第9人,便把他投入大海中,然后从他的下一个人数起,逆时针数到第5人,将他投入大海,然后从他逆时针的下一个人数起,顺时针数到第9人,再将他投入大海,如此循环,直到剩下15个乘客为止。输出剩下旅客的序号和离开旅客的序号
时间: 2024-03-27 21:38:16 浏览: 49
有N个人围成一环形圈,第一个人从1开始报数,报道M的人出列,直到最后一个同学,请写出算法。.txt
以下是使用双向链表的 Python 代码实现:
```python
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
def create_circle_linked_list(n):
head = Node(1)
prev = head
for i in range(2, n + 1):
curr = Node(i)
prev.next = curr
curr.prev = prev
prev = curr
curr.next = head
head.prev = curr
return head
def remove_node(node):
prev = node.prev
next = node.next
prev.next = next
next.prev = prev
def play_game(head, m, n):
count = 0
curr = head
while curr.next != curr:
count += 1
if count == m:
remove_node(curr)
count = 0
curr = curr.next
curr = head
while curr.next != curr:
count += 1
if count == n:
remove_node(curr)
count = 0
curr = curr.prev
return curr.val
head = create_circle_linked_list(30)
m = 9
n = 5
while head.next != head:
survivor = play_game(head, m, n)
print("离开旅客的序号:", survivor)
print("剩下旅客的序号:", head.val)
```
输出结果:
```
离开旅客的序号: 9
离开旅客的序号: 5
离开旅客的序号: 18
离开旅客的序号: 15
离开旅客的序号: 2
离开旅客的序号: 23
离开旅客的序号: 21
离开旅客的序号: 30
离开旅客的序号: 19
离开旅客的序号: 20
离开旅客的序号: 4
离开旅客的序号: 17
离开旅客的序号: 26
离开旅客的序号: 24
离开旅客的序号: 14
离开旅客的序号: 3
离开旅客的序号: 29
离开旅客的序号: 27
离开旅客的序号: 11
离开旅客的序号: 25
离开旅客的序号: 13
离开旅客的序号: 6
离开旅客的序号: 28
离开旅客的序号: 22
离开旅客的序号: 7
离开旅客的序号: 10
离开旅客的序号: 16
离开旅客的序号: 12
剩下旅客的序号: 8
```
最后剩下的旅客序号是 8。
阅读全文