7-3 约瑟夫环 分数 10 作者 usx程序设计类课程组 单位 绍兴文理学院 有n个人围成一圈(编号为1~n),从第1号开始进行1、2、3报数,凡报3者就退出,下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人
时间: 2024-05-10 08:17:09 浏览: 289
的编号是多少?
这是经典的约瑟夫环问题,可以使用递归或数学方法解决。
递归方法:
首先定义递归函数 Josephus(n, k),表示 n 个人围成一圈,每次报数 k,最后剩下的人的编号。则有:
Josephus(n, k) = (Josephus(n-1, k) + k - 1) % n + 1
其中 % 表示取模运算。
当 n=1 时,只剩下一个人,其编号为 1,因此可以作为递归的终止条件。
完整代码如下:
def Josephus(n, k):
if n == 1:
return 1
else:
return (Josephus(n-1, k) + k - 1) % n + 1
n = int(input("请输入人数:"))
k = 3 # 报数为 3
print("最后剩下的人的编号是:", Josephus(n, k))
数学方法:
根据数学方法,最后剩下的人的编号为:
f(n, k) = (f(n-1, k) + k) % n
其中 f(1, k) = 0。
完整代码如下:
def Josephus(n, k):
if n == 1:
return 1
else:
return (Josephus(n-1, k) + k - 1) % n + 1
n = int(input("请输入人数:"))
k = 3 # 报数为 3
print("最后剩下的人的编号是:", Josephus(n, k))
相关推荐


















