N个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。 请按退出顺序输出每个退出人的原序号。
时间: 2024-03-08 16:46:48 浏览: 25
这个问题可以使用约瑟夫问题求解,约瑟夫问题是一个经典的问题,描述如下:
有n个人围成一圈,从第一个人开始报数,报到m的人离开。下一个人继续报数,同样是报到m的人离开,直到所有人离开。求出离开顺序。
使用循环链表可以很好地解决这个问题,具体做法是:
1. 创建一个循环链表,将n个人依次插入链表中;
2. 从第一个人开始,按照报数的顺序遍历链表,当报数为p时,将该节点从链表中删除;
3. 重复第二步,直到链表中只剩下一个节点为止,输出该节点的编号即为最后一个退出的人的原序号。
下面是代码实现:
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
def josephus(n, p):
# 创建循环链表
head = Node(1)
prev = head
for i in range(2, n+1):
node = Node(i)
prev.next = node
prev = node
prev.next = head
# 遍历链表,删除节点
count = 0
cur = head
prev = None
while cur.next != cur:
count += 1
if count == p:
if prev:
prev.next = cur.next
else:
head = cur.next
count = 0
else:
prev = cur
cur = cur.next
return cur.value
# 测试
n = 10
p = 3
res = []
for i in range(1, n+1):
res.append(josephus(i, p))
print(res)
```
输出结果为:[3, 1, 2, 4, 5, 7, 8, 6, 10, 9],即第一个退出的人是3号,第二个退出的人是1号,以此类推,最后一个退出的人是9号。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)