约瑟夫环的数学解法

约瑟夫环数学算法的优化 摘要：分析了约瑟夫环的模拟算法并推广了Knuth递归算法，并递归算法上进一步改进，在一定范围内，让算法的复杂度与约瑟夫环的人数无关。关键词：约瑟夫环，算法，递归 1、引言约瑟夫环问题来源于公元6世纪犹太人的反罗马起义，这个问题是如此流行，以至于几乎所有的编程入门和算法书籍都会提到这个问题，以作为数据结构或模拟算法的经典入门题。这个问题的一般形式可描述为：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，求最后一个出列人的编号。 2、原始的算法：模拟求解O(N*M) 如果模拟整个过程，这种普遍的解法即：用一数组或是链表去表示约瑟夫环，设计两重循环，内层作m次循环，既每扫描m个数之后，将其从数组、或链表中将其删除，以表示从约瑟夫环中去处相应的人；外循环重数为n-1，表示总共要删除n-1个数，而剩下的最后一个数就是所求的解。 但不管数据结构的表示方法如何，这种算法效率都是O(m*n)。这种算法的问题在于：它模拟了这个问题的整个过程，就是说在n或m很大的情况下，计算出结果需要较长的时间；它没有从数学的角度上去优化，而实际上这个问题往往只要求得到最终的解，并不要求中间的过程带来的而外开销。 3、递归的力量：优化到O(N) 在Donald E. Knuth的《具体数学》中，对m=2的情况使用了递归的解决方法，并推出了一个常数表达式，使得此种情况下，算法的复杂度为常量。同时，这种思路也可以应用于n>2 的情况，但无法得出常数表达式，推广后的递归算法具体的思路如下：当n个人围成一圈并以m为步长第一次报数时，第m个人出列，此时就又组成了一个新的，人数为n-1的约瑟夫环，要求n个人的约瑟夫环问题的解，就依赖于求n-1个人的约瑟夫问题的解，要求n-2个人的约瑟夫问题的解，则依赖于求n-2个人的约瑟夫换问题的解，依次类推，直至求1个人的时候，该问题的解。让我们回到问题的原始描述中，m是一个固定的值，即步长；n为一个圈的总人数，k为这个圈第一个报数的人的编号，显然，n在每次递归过程中会减1，而k则可以由m,n来唯一确定，这样的话，当n=1的时候，我们所确定的当前的k值，就是我们所要求的解。那么，我们可列出如下的递归式： P(n, m, k)=1 (i = 1)P(n, m, k)=(P(i - 1, m, k ) + m - 1) % n + 1; (i > 1) （此处m需先减1是为了让模n的值不为0） 这样，我们可以很轻松的将此算法具体实现。这里给出它的递推表示法以方便进下一步讨论（C言描述）： long Josephus(long n,long m,long k) //参数分别为：人数，出圈步长，起使报数位置,...{ for (long i = 1; i <= n; i++) ...{ k = (k + m - 1) % i + 1; } return k; //返回最后一人的位置} 显然，这个算法的复杂度仅为O(n)，相比模拟算法，有了很大的改进。 4、再优化：与人数无关 上面的算法相比最初的模拟算法效率已经大大提升了，那么，该算法还有改进的余地么？ 事实上，如果我们观察上述算法中的变量k，他的初始值为第一个出圈人的编号，但在循环的过程中，我们会发现它常常处在一种等差递增的状态，我来看这个式子：k = (k + m - 1) % i + 1，可以看出，当i比较大而k+m-1比较小的时候，k就处于一种等差递增的状态，这个等差递增的过程并不是必须的，可以跳过。我们设一中间变量x，列出如下等式：k + m * x – 1 = i + x解出x，令k = k + m * x，将i + x直接赋值给 i，这样就跳过了中间共x重的循环，从而节省了等差递增的时间开销。可是其中求出来的x + i可能会超过n，这样的结果事实上已经告诉我们此时可以直接结束算法了，即：k = k + m * (n - i) ;i = n;结束。 另外对于m = 1的情况可以单独讨论：当k == 1时，最终结果就是n；当k != 1时，最终结果就是(k + n - 1) % n。整个算法的C语言描述如下： long Josephus(long n,long m,long k) //分别为：人数，出圈步长，起使报数位置,...{ if (m == 1) k = k == 1 ? n : (k + n - 1) % n; else ...{ for (long i = 1; i <= n; i++) ...{ if ((k + m) < i) ...{ x = (i - k + 1) / (m - 1) - 1; if (i + x < n) ...{ i = i + x; k = (k + m * x); } else ...{ k = k + m * (n - i) ; i = n; } } k = (k + m - 1) % i + 1; } }return k; //返回最后一人的位置} 该算法的算法复杂度在m<n时已经与一个圈中的人数n没有关系了，即使在n=2000000000，m=3，k=1的情况下，也只做了54次循环，事实上，大多数的情况都是m<n，且m相对来说很小，此时，这个算法的复杂度仅为O(m)；但当而m>=n时，用方程求出的值不能减少循环重数，算法复杂度仍为O(n)。 参考文献[1] Grahm, Knuth, Patashnik . Concrete Mathematics.Addison Wesley. 1984[2 ]T.H.Cormen, C.E.Leierson, R.L.Rivest, and Stein. Introduction to Algorithms. MIT Press. 2001[3] 严蔚敏,吴伟明.数据结构.清华大学出版社.1997 最后的说明,源代码在细节上有些错误的,仅供交流讨论Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1906316