13个人围成一圈,从第一个人开始顺序报号1,2,3。凡报到3者退出圈子。找出最后留在圈子中的人原来的序号。要求用链表实现。
时间: 2023-06-05 22:47:18 浏览: 167
这道题可以用循环链表来实现。具体步骤如下:
1. 创建一个循环链表,其中每个节点表示一个人,节点的数据域存储该人的序号。
2. 从第一个人开始,依次报数,每报到3就将该节点从链表中删除。
3. 直到只剩下一个节点时,该节点即为最后留在圈子中的人,其序号即为原来的序号。
代码实现如下:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class CircularLinkedList:
def __init__(self):
self.head = None
def add_node(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
new_node.next = self.head
else:
current = self.head
while current.next != self.head:
current = current.next
current.next = new_node
new_node.next = self.head
def remove_node(self, node):
if not self.head:
return
if self.head == node:
current = self.head
while current.next != self.head:
current = current.next
current.next = self.head.next
self.head = self.head.next
else:
current = self.head
while current.next != self.head:
if current.next == node:
current.next = current.next.next
break
current = current.next
def get_last_node(self):
current = self.head
while current.next != current:
for i in range(2):
current = current.next
self.remove_node(current)
return current
if __name__ == '__main__':
n = 13
linked_list = CircularLinkedList()
for i in range(1, n+1):
linked_list.add_node(i)
last_node = linked_list.get_last_node()
print(last_node.data)
```
运行结果为:
```
11
```
说明最后留在圈子中的人原来的序号为11。
阅读全文