要求:求出这个圆圈中剩下的最后一个数字.
所以最终为 3.
通过上面的流程可以发现:每隔 m 个数就要删除一个数,那么被删除的这个数的下一个数就会成为新的起点.就相当于数组进行左移了 m 位.反过来思考的话,从最后一步向前推,则每一步都向右移动了 m 位(包括胜利者).
即等于 n - 1 个数构成的环没删除 m 个数后最终胜利者的位置,像右移动 m 次.
问题是现在并不是真的进行了右移,因为当前数组右移后超过数组容量的部分应该重新放到数组头部位置.所以公式应为:f(n m) = [f(n - 1 m) + m] % n,n 为反过来向前推的时候,每一步剩余的数字个数(比如第二步推回第一步,n 4),则反过来递推公式为:
接下来就是递推求解了.