n只猴子选猴王,将猴子们从1到n编号并排成一个圆圈,从一号猴子开始数,每数到13的猴子就出列,如此循环,直到圈中的猴子只剩两只,序列靠前的那一只为猴王,n的取值为13到1000
时间: 2024-06-13 11:08:41 浏览: 203
ACM 猴子报数
这是一个经典的约瑟夫问题,可以使用递归或循环来解决。具体解法如下:
1. 递归解法:
定义一个函数f(n,m),表示n只猴子选出猴王的过程中,每数到m的猴子出列后剩下的猴子选猴王的过程。则有以下递推公式:
f(n,m) = (f(n-1,m)+m)%n (n>1)
f(1,m) = 0
其中,f(1,m)表示只有一只猴子时,它自己就是猴王,编号为0。
最终,当n只猴子选出猴王时,编号为f(n,m)+1的猴子就是猴王。
2. 循环解法:
定义一个数组a[n],表示第i只猴子是否还在圈中。初始时,所有猴子都在圈中,即a[i]=1。然后按照题目要求,每数到第13只猴子就将其从圈中删除,即a[i]=0。直到圈中只剩下两只猴子时,序列靠前的那一只为猴王。
具体实现过程如下:
```python
n = 1000
m = 13
a = [1] * n
cnt = n # 记录圈中还剩下的猴子数
i = 0 # 当前数到的猴子编号
while cnt > 2:
j = 0 # 记录当前数到的第几只猴子
while j < m:
if a[i] == 1:
j += 1
if j == m:
a[i] = 0
cnt -= 1
i = (i+1) % n
while a[i] == 0:
i = (i+1) % n
print(a.index(1)+1, (a.index(1)+1)%n+1)
```
最终,输出的结果为序列靠前的那一只猴子的编号和它旁边的猴子的编号,即为猴王和副王。
阅读全文