分类： C/C++
2011-04-16 19:58:21
问题描述：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列，求最后一个出列人的编号。
递归的力量：优化到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)，相比模拟算法，有了很大的改进。
再优化：与人数无关
上面的算法相比最初的模拟算法效率已经大大提升了，那么，该算法还有改进的余地么？
事
实上，如果我们观察上述算法中的变量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; //返回最后一人的位置}
