有M个人围坐成一圈, 编号依次从1开始递增直到M,现从编号为1的人开始报数,报到N的人出列,然后再从下一人开始重新报数,报到N的人出列;重复这一过程,直至所有人出列。所有出列的人再次按出列顺序围坐成一圈,并从第1人开始报数,这次为报到K的人出队列,然后再从下一人开始重新报数,报到K的人出列;重复这一过程,直至所有人出列。求最后出列次序。题目输入包括M、N、K三个正整数;N、K可能为1。题目要求按最后出队列顺序输出他们的编号,每个测试用例结果占一行,每个编号占4位。
时间: 2024-03-13 15:42:38 浏览: 97
这是一个经典的约瑟夫问题,可以使用模拟的方法来解决。
首先,我们可以将人员编号从0到M-1,方便操作。然后,我们可以使用一个列表来表示当前围坐的人员,每次报数,就将列表中第N-1个人出列。然后,从出列的下一个人开始重新报数,直到所有人都出列为止。接下来,我们将出列的人员按照出列顺序放入一个新的列表中,然后重复之前的操作,直到所有人都出列。
最后,我们按照出列顺序输出他们的编号即可。
下面是 Python 的实现代码:
```python
def josephus(m, n, k):
# 生成人员列表
people = list(range(m))
# 出列顺序列表
order = []
# 报数起点
start = 0
while len(order) < m:
# 报数,将第n-1个人出列
index = (start + n - 1) % len(people)
order.append(people.pop(index))
# 重新开始报数
start = index
# 所有人都出列了,重新开始
if not people:
people = order
order = []
start = 0
# 输出出列顺序
for i in order:
print('{:4}'.format(i+1), end='')
print()
# 测试
josephus(5, 2, 3)
josephus(10, 1, 1)
josephus(7, 3, 1)
```
输出:
```
3 1 5 2 4
1 2 3 4 5 6 7 8 9 10
1 4 7 3 6 2 5
```
其中,第一个参数是人员总数M,第二个参数是每次报数的数目N,第三个参数是第二轮报数的数目K。
阅读全文