鸟语天空
约瑟夫环
post by:追风剑情 2015-1-30 21:32

问题:

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



评论:
发表评论:
昵称

邮件地址 (选填)

个人主页 (选填)

内容