问题:
将编号为0~(N-1)这N个人进行圆形排列。按顺时针从0开始报数,报到M-1的人退出圆形队列,剩下的人继续从0开始报数,不断重复。求最后出列者最初在圆形队列中的编号。
这N个人的原始编号为:
0, 1, 2, 3 ... N-3, N-2, N-1
第一个出列人的编号一定是(M-1)%N, 则第一个人出列后的列表为:
0, 1, 2, 3, M-3, M-2, M, M+1, M+2 ... N-2, N-1
按上面的顺序重新编号得到以下对应关系:
A表: 0, 1, 2 ... N-3, N-2
B表: M,M+1,M+2 ... N-2, N-1, 0, 1 ... M-3, M-2
A表中的N-1个人够成一个新的环,如果我们知道A表中最后一个出列者编号为x,那么通过A表与B表的对应关系可以知道B表(即N个人)中最后出列者的编号为(x+M)%N
综上所述,得到以下递推公式:用F(N)表示N个人时最后出列者编号
F(1)=0
F(N)=[F(N-1)+M]%N (N>1)