要从n只猴子中选出一位大王。它们决定使用下面的方法:\nn只猴子围成一圈,从1到n顺序编号。从第q只猴子开始,从1到m报数,凡报到m的猴子退出竞选,下一次又从退出的那只猴子的下一只开始从1到m报数,直至
时间: 2023-04-23 22:05:56 浏览: 326
最后只剩下一只猴子为止,这只猴子就是大王。请问,最后当选的大王是第几只猴子?
这是一个经典的约瑟夫问题,可以用数学归纳法证明,最后当选的大王编号为:
f(n,m) = (f(n-1,m)+m) % n
其中,f(n,m)表示n只猴子中最后当选的大王编号,m表示报数到m的猴子退出竞选。当n=1时,f(n,m)=0,即只有一只猴子时,它就是大王。
例如,当n=5,m=3时,最后当选的大王编号为:
f(5,3) = (f(4,3)+3) % 5 = ((f(3,3)+3)+3) % 5 = (((f(2,3)+3)+3)+3) % 5 = ((((f(1,3)+3)+3)+3)+3) % 5 = (((0+3)+3)+3)+3) % 5 = 3
因此,最后当选的大王是第3只猴子。
阅读全文