有n个人围成一圈,顺序排号。从第1个人开始1-3报数,凡报到3的人退出圈子,问最后留下的是原来第几号的那位且记录每个被淘汰的人是在第几圈(1圈中所有人员报数完成后圈数加1)报数时被淘汰的。
时间: 2023-12-27 22:18:20 浏览: 20
这是一个经典的约瑟夫问题,可以用递归或循环来解决。以下是用循环的方法解决该问题,每次删除一个数字后,重新编号,保证下一次从正确的位置开始报数。
假设有n个人,编号从1到n,用一个数组alive来记录每个人是否还在圈子里,0表示已经被淘汰,1表示还在圈子里。用一个变量cnt来记录当前报数到了几个人,当cnt等于3时,将当前位置的人淘汰,并将其记录在另一个数组eliminated中,同时将cnt归零。最后留下的人就是alive数组中值为1的那个位置。
以下是代码实现:
```python
def josephus(n):
alive = [1] * n
eliminated = []
cnt = 0
pos = 0
round = 1
while sum(alive) > 1:
if alive[pos] == 1:
cnt += 1
if cnt == 3:
eliminated.append((pos+1, round))
alive[pos] = 0
cnt = 0
pos = (pos + 1) % n
if pos == 0:
round += 1
for i in range(n):
if alive[i] == 1:
return i+1, eliminated
```
调用josephus函数,传入n即可得到最后留下的人和每个被淘汰的人是在第几圈报数时被淘汰的。
阅读全文