N个人围成一圈从第一个开始报數,第M个将被杀掉最后剩下一个,其余人都将被杀掉例如N=6,M=5被杀掉的顺序是:5,46,23,1
-
f(N,M)表示,N个人报数每报到M时杀掉那个人,最终胜利者的编号f(N?1,M)
-
f(N?1,M)表示N-1个人报数,每报到M时杀掉那个人最终胜利者的编号
问题描述:n个人(编号0~(n-1)),从0开始报数报到(m-1)的退出,剩下的人继续从0开始报数求胜利者的编号。
假如我们已经知道了n-1个人时最后胜利者的编号为x,利用映射关系逆推就可以得出n个人时,胜利者的编号为(x+k)%n其中k=m%n。
这是一个n-2个人的问题假设最后胜利者为y,那么n-1个人时胜利者为(y+o)%(n-1),其中o等于m%(n-1)代入可得(y+m)%(n-1)