n个人围成一圈,按1到n的顺序编号,从第一个人开始报数(从1到m报数),凡报到m的人退出圈子,问最后留下的是原来的第几号
时间: 2023-10-22 09:04:57 浏览: 146
Python使用列表完成程序的编写:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到m报数),凡是报到m的人退出圈子,问最后留下的是原来第几号的人。
5星 · 资源好评率100%
这是经典的约瑟夫问题(Josephus problem),可以用递归或数学公式求解。假设最后留下的人的编号为f(n,m),则有以下递推公式:
f(1,m) = 0 (只剩一个人,编号为0)
f(n,m) = (f(n-1,m) + m) % n (剩下n个人,第一次报数后,剩下n-1个人,编号重新从0开始)
根据递推公式,可以写出以下 Python 代码来求解:
```python
def josephus(n, m):
if n == 1:
return 0
else:
return (josephus(n-1, m) + m) % n
n = 10 # 总人数
m = 3 # 报数到m的人出圈
print(josephus(n, m)) # 输出最后留下的人的编号
```
对于 n=10, m=3 的情况,输出为 4,即原来的第4号留下来了。
阅读全文