约瑟夫环

作者：追风剑情发布于：2015-1-30 21:32 分类：Algorithms

问题：

将编号为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)

鸟语天空