有n个人围成一圈从1-3报数
时间: 2023-12-27 18:17:11 浏览: 67
有100个人围成一个圈,从1开始报数,报到14的这个人就要退出
5星 · 资源好评率100%
这是一个算法问题,可以使用循环链表来解决。具体步骤如下:
1. 构建一个循环链表,包含n个节点,每个节点的值为该节点在报数中的序号。
2. 设置一个指针p指向链表的头节点。
3. 从1开始报数,每报到3就删除当前节点,即让p所指向的节点的下一个节点成为新的p,并将当前节点从链表中删除。
4. 重复执行步骤3,直到链表中只剩下一个节点,该节点即为胜者。
代码示例(使用Python语言实现):
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
def josephus(n):
head = Node(1)
p = head
for i in range(2, n+1):
p.next = Node(i)
p = p.next
p.next = head # 构建循环链表
while p.next != p: # 只剩下一个节点时停止循环
for i in range(1, 3):
p = p.next
p.next = p.next.next # 删除当前节点
return p.value # 返回胜者的序号
n = 10 # 有10个人
print(josephus(n)) # 输出胜者的序号
```
输出结果为:
```
5
```
阅读全文