首先阐述一下问题:n个人(编号0—n-1)围成一圈,从1开始报数,报到m的人出列,然后从出列的人的下一个人开始,从1开始报数,报到m的人出列,求出最后幸存的那个人的原始编号。
如果单纯的是模拟整个游戏过程的话,实现起来并不难。今天我学习到的是另一种算法。举个例子,第一轮以后,假设被淘汰的人编号是k-1,报数是m,那么接下来的n-1的应该是这样排序x`(x),x`表示上一轮的编号,x表示本轮的编号。那么目前的情况应该是这样的k(0)、k+1(1)、k+2(2)、……、k-2(n-2),我们可以得出这么一个公式x`=(x+k)%N因为最后一个幸存者他最后的编号一定是0,那么有此推出他的上一轮编号……直到推出一开始的编号为止