首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

约瑟夫环的数学算法,有二点不明白

2013-07-16 
约瑟夫环的数学算法,有2点不明白简言之,是想找到约瑟夫环的一个好算法。如果大家有好算法,就不用往下看了,

约瑟夫环的数学算法,有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

其中有个等式  x' = x+k,而算法中又提到 k-2 --> n-2,所以 k-2 = n- 2 +k,推出n=0。所以这等式貌似不成立啊

2.算法中说f[1]=0;那最后一个出列的岂不一直是第一个人?
约瑟夫环 算法 时间复杂度
[解决办法]
f[1]=0 是说当只剩一个人时,最后胜利的就是这剩下的一个人。而这个人并不是最开始的第一个人。
[解决办法]
楼主看下 《具体数学》 
第一章就有讲这类问题的数学方法,通俗易懂的。

热点排行