又见约瑟夫环:有M个人围坐成一圈, 编号依次从1开始递增直到M,现从编号为1的人开始报数,报到N的人出列,然后再从下一人开始重新报数,报到N的人出列;重复这一过程,直至所有人出列。所有出列的人再次按出列顺序围坐成一圈,并从第1人开始报数,这次为报到K的人出队列,然后再从下一人开始重新报数,报到K的人出列;重复这一过程,直至所有人出列。求最后出列次序。题目输入包括M、N、K三个正整数;N、K可能为1。题目要求按最后出队列顺序输出他们的编号,每个测试用例结果占一行,每个编号占4位。
时间: 2024-03-15 22:45:04 浏览: 119
这是一个经典的约瑟夫环问题,可以使用模拟的方法来求解。下面是一个 Python 的实现代码:
```python
def josephus_circle(m, n, k):
# 初始化人员列表和出列顺序列表
people = list(range(1, m+1))
out_order = []
# 记录当前报数的人员索引
i = 0
# 当人员列表不为空时循环
while people:
# 计算当前报数的人员索引
i = (i + n - 1) % len(people)
# 将报数到第n个的人员出列,并加入出列顺序列表
out_person = people.pop(i)
out_order.append(out_person)
# 初始化人员列表为出列顺序列表
people = out_order
out_order = []
# 记录当前报数的人员索引
i = k - 1
# 当人员列表不为空时循环
while people:
# 计算当前报数的人员索引
i = i % len(people)
# 将报数到第k个的人员出列,并加入出列顺序列表
out_person = people.pop(i)
out_order.append(out_person)
# 更新当前报数的人员索引
i += k - 1
return out_order
# 测试
print(josephus_circle(5, 2, 3)) # [3, 1, 5, 2, 4]
```
以上代码的时间复杂度为 $O(m^2)$,在 $m$ 很大时效率较低。可以使用数学方法求解,时间复杂度为 $O(m)$,但需要一定的数学知识。
阅读全文