有M个人围坐成一圈, 编号依次从1开始递增直到M,现从编号为1的人开始报数,报到N的人出列,然后再从下一人开始重新报数,报到N的人出列;重复这一过程,直至所有人出列。所有出列的人再次按出列顺序围坐成一圈,并从第1人开始报数,这次为报到K的人出队列,然后再从下一人开始重新报数,报到K的人出列;重复这一过程,直至所有人出列。求最后出列次序。题目输入包括M、N、K三个正整数;N、K可能为1。题目要求按最后出队列顺序输出他们的编号,每个测试用例结果占一行,每个编号占4位。
时间: 2024-03-08 08:47:12 浏览: 82
这是经典的约瑟夫问题,可以使用循环链表或者数学方法来解决。以下是使用循环链表的解法:
```python
class Node:
def __init__(self, val=None):
self.val = val
self.next = None
def josephus(m, n, k):
# 构造循环链表
head = Node(1)
curr = head
for i in range(2, m+1):
curr.next = Node(i)
curr = curr.next
curr.next = head
# 开始报数
curr = head
while curr.next != curr:
# 找到报数的前一个人
for i in range(n-1):
curr = curr.next
# 删除报数的人
print("{:4d}".format(curr.next.val), end='')
curr.next = curr.next.next
# 重新开始报数
for i in range(k-1):
curr = curr.next
print("{:4d}".format(curr.val), end='')
# 测试
josephus(5, 3, 2) # 输出 3 1 5 2 4
```
时间复杂度为 $O(mn)$,空间复杂度为 $O(m)$。
注意,这个解法只考虑了最后一次出列的顺序,如果要考虑所有出列的顺序,可以使用一个列表来记录每次出列的顺序,最后将两个列表合并即可。
阅读全文