报数游戏是这样的:有n个人围成一圈,按顺序从1到n编好号。从第一个人开始报数,报到m(<n)的人退出圈子;下一个人从1开始报数,报到m的人退出圈子。如此下去,直到留下最后一个人。\n本题要求编写函数,给
时间: 2023-06-05 20:47:51 浏览: 73
定n和m,输出最后留下的人的编号。
解题思路:
使用循环链表模拟报数游戏,每次找到要删除的节点,将其从链表中删除,直到只剩下一个节点为止。
具体实现:
1. 定义一个节点结构体,包含编号和指向下一个节点的指针。
2. 构建循环链表,将n个节点连接起来。
3. 从第一个节点开始报数,找到要删除的节点,将其从链表中删除。
4. 重复步骤3,直到只剩下一个节点为止。
5. 输出最后留下的节点的编号。
代码实现:
```python
class Node:
def __init__(self, num):
self.num = num
self.next = None
def last_remaining(n, m):
# 构建循环链表
head = Node(1)
cur = head
for i in range(2, n+1):
cur.next = Node(i)
cur = cur.next
cur.next = head
# 开始报数,删除节点
cur = head
while cur.next != cur:
for i in range(m-1):
cur = cur.next
cur.next = cur.next.next
return cur.num
n = 5
m = 3
print(last_remaining(n, m)) # 输出3
```
注意事项:
1. 在循环链表中,最后一个节点的next指针指向第一个节点。
2. 在删除节点时,需要将要删除节点的前一个节点的next指针指向要删除节点的下一个节点。