7-3 约瑟夫环 分数 10 作者 usx程序设计类课程组 单位 绍兴文理学院 有n个人围成一圈(编号为1~n),从第1号开始进行1、2、3报数,凡报3者就退出,下一个人又从1开始报数……直到最后只剩下一个人时为止。请问此人

的编号是多少？
这是经典的约瑟夫环问题，可以使用递归或数学方法解决。
递归方法：
首先定义递归函数 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))
登录后复制