看见更大的世界,遇见更好的自己。
See a better world to meet better for ourselves.
猴子选大王
一群猴子要选新猴王。新猴王的选择方法是 让N只候选猴子围成一圈,从某位置起顺序编号为1 N号。
从第1号开始报数,每轮从1报到3,凡报到3的猴子即退出圈子,接着又从紧邻的下一只猴子开始同样的报数。
如此不断循环,最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王?
这道题是典型的约瑟夫环问题。
N = int(input("请输入猴子的数量 "))
monkeys = [] # 列表中存储猴子在圈内(1表示 ,还是已经出圈(0表示
for i in range(1, N + 1):
monkeys.append(1) # 开始,猴子都在圈内,全都赋值1
print(monkeys)
cnt = 0 # 报数
n = N # n存储了圈内猴子的数量,开始猴子都在圈内
while n != 1: # 重复执行直到剩下最后一只猴子
for i in range(0, N): # 遍历所有的猴子
if monkeys[i] == 1: # 如果这只猴子还在圈内,才计数
cnt = cnt + 1 # 报数
if cnt == 3: # 如果报到3
monkeys[i] = 0 # 猴子出局,将猴子标识为0
cnt = 0 # 从头开始报数
n = n 1 # 在圈的猴子数量减1
print(monkeys.index(1) + 1) # 列表中为1的索引+1就是留下的猴子
Powered by HadSky 7.12.6
©2015 - 2023 小羊羔外链网
您的IP:18.206.92.240,2023-03-21 14:24:39,Processed in 0.01771 second(s).