输入正整数n、m(m<n),设有n个人坐成一圈,从第1个人开始循环报数,报到m的人出列,然后再从下一个人开始报数,报到m的人又出列,如此重复,直到所有的人都出列为止。要求用链式结构和顺序结构实现,按出
时间: 2023-05-01 07:05:07 浏览: 185
这道题的意思是让我们输入整数n和m(m小于n),设有n个人坐成一圈,从第1个人开始顺时针报数,报到m的人出列,然后从下一个人开始继续报数,直到所有人均出列为止。要求用链式结构和顺序结构实现,按出列顺序输出。
相关问题
有M个人围坐成一圈, 编号依次从1开始递增直到M,现从编号为1的人开始报数,报到N的人出列,然后再从下一人开始重新报数,报到N的人出列;重复这一过程,直至所有人出列。所有出列的人再次按出列顺序围坐成一圈,并从第1人开始报数,这次为报到K的人出队列,然后再从下一人开始重新报数,报到K的人出列;重复这一过程,直至所有人出列。求最后出列次序。题目输入包括M、N、K三个正整数;N、K可能为1。题目要求按最后出队列顺序输出他们的编号,每个测试用例结果占一行,每个编号占4位。
这是经典的约瑟夫问题,可以使用循环链表或者数学方法来解决。以下是使用循环链表的解法:
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)$。
注意,这个解法只考虑了最后一次出列的顺序,如果要考虑所有出列的顺序,可以使用一个列表来记录每次出列的顺序,最后将两个列表合并即可。
输入两个正整数 n 和 m( (1<m<n<=50)),有 n 个人围成一圈,按顺序从 1 到 n 编号。从第一个人开始报数,报数 m 的人退出圈子,下一个人从 1 开始重新报数,报数 m 的人退出圈子。如此循环,直到留下最后一个人。请按退出顺序输出退出圈子的人的编号,以及最后一个人的编号。 提示:将每个人的编号存入数组,从第一个人开始报数,输出报数 m 的人的编号,并将该编号清除为0,重复这样的操作直至只剩下一个不为0的数,该数就是最后一个人的编号。 输入输出示例:括号内为说明,无需输入输出
题目大意:输入两个正整数n和m(1<m<n<=50),有n个人围成一个圈,按顺序从1到n编号。从第一个人开始报数,报到m的人出圈,下一个人从1开始重新报数,直到只剩下最后一个人。请按退出顺序输出退出圈子的人的编号,以及最后一个人的编号。
提示:将每个人的编号存入数组,从第一个人开始报数,输出报数为m的人的编号,并将该编号清除为0,直到只剩下一个非零的编号,即为最后一个人的编号。
相关推荐













