约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
在不改变原意的情况下改变描述：
n个人(编号0~(n-1))，从0开始报数，报到m-1的退出，剩下的人继续从0开始报数。求胜利者的编号。
O(n)算法：
我们知道第一个人（编号一定是（m-1）%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）。
假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去刚好就是n个人情况的解。
∵ k=m%n;
∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n ∴x'= (x+ m%n)%n = (x+m)%n 得到 x'=(x+m)%n。
严谨推导后得出递推公式：
第i轮出局的人为f(i)=(f(i-1)+m-1)%(n-i+1),f(0)=0; f(i) 表示当前子序列中要退出的那个人（当前序列编号为0~(n-i));
拿个例子说：K=4,M=30;
f(0)=0;
f(1)=(f(0)+30-1)%8=5; 序列（0,1,2,3,4,5,6,7）中的5
f(2)=(f(1)+30-1)%7=6; 序列（0,1,2,3,4,6,7）中的7
f(3)=(f(2)+30-1)%6=5; 序列（0,1,2,3,4,6）中的6
f(4)=(f(3)+30-1)%5=4; 序列（0,1,2,3,4）中的4
每隔一人退出的特殊情况
在这种特殊情况下，算法的时间复杂度可以大大简化。
理论参见《具体数学》7-14页
Read full article from 约瑟夫环学习小记 - whyorwhnt的专栏 - 博客频道 - CSDN.NET
No comments:
Post a Comment