有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的人。
时间: 2023-12-23 07:48:32 浏览: 87
这是一个经典的约瑟夫问题,可以使用递归或循环来解决。
递归解法:
假设有n个人,第一次从第k个人开始报数,报到第m个人出圈。那么我们可以将问题转化为:n-1个人中,从第k个人开始报数,报到第m个人出圈后,剩下的人组成的圈子中,最后剩下的人在原来圈子中的位置是多少。
设f(n,k,m)为n个人中,从第k个人开始报数,报到第m个人出圈后,剩下的人组成的圈子中,最后剩下的人在原来圈子中的位置。
则有:
f(n,k,m) = (f(n-1,k,m) + m) % n
当n=1时,f(n,k,m) = 0,即剩下的那个人在原来圈子中的位置就是0。
代码如下:
```python
def josephus(n, k, m):
if n == 1:
return 0
else:
return (josephus(n-1, k, m) + m) % n
n = 10
k = 1
m = 3
print("最后留下的人在原来圈子中的位置是:", josephus(n, k, m))
```
循环解法:
我们可以用一个列表存储所有人的编号,每次找到报数为3的人并将其从列表中移除,直到只剩下一个人为止。
代码如下:
```python
n = 10
people = list(range(1, n+1)) # 把所有人的编号存入列表
m = 3
i = 0 # i表示当前报数的人的索引
while len(people) > 1:
i = (i + m - 1) % len(people) # 找到报数为3的人的索引
people.pop(i) # 把报数为3的人从列表中移除
print("最后留下的人在原来圈子中的位置是:", people[0])
```
阅读全文