约瑟夫环的数学算法,有2点不明白
简言之,是想找到约瑟夫环的一个好算法。如果大家有好算法,就不用往下看了,请直接描述下你的算法
另外,《算法导论》里的,貌似只计算m=2,但是我希望知道一个通用算法
下面比较长,希望同志们hold住
百度百科里提到一个数学算法。算法太长,不好贴出来,这是链接,请同志们动动手指http://baike.baidu.com/view/717633.htm#4
这个算法,有2点让我想不通
1.算法中有这么一段话:
变换后就完完全全成为了(n-1)个人报数的子问题,假如我们知道这个子问题的解:例如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