约瑟夫问题O(n)解法剖析

之前听说约瑟夫问题O(n)解法的时候，记得还是在北邮人论坛上看到的。不过当时也没有太多的理解，比较单纯的记了下公式也就了事。今天在翻看具体数学第三章的时候，又看到了O(n)的解法。感觉很强大。摘录下以作备忘。

问题的描述是：有n个人，从1到n进行编号，每次取第q个人之后从之后的人开始计数取人，循环以至剩下最后一个人，求此人的初始编号。

我们现在假设一种构造：当一个人被越过去的时候，顺序给他一个新的编号。比如说1,2..k-1被越过之后会被赋予n+1,n+2…等等，编号依次顺序递增。更普遍的说法是：编号为qk+m(0的人会被赋予n+(q-1)k+m…则我们假设最后的编号是qn(也许没有这么大，但是这是上界，我们可以假设只剩下一个人的时候继续递增编号直到qn为止)。假设对于一个大于N的编号，其必然存在一个的初始编号，我们现在就是要找到这个初始的编号。

因为N=n+(q-1)k+m,可以得出k=floor((N-n-m)/(q-1)).由于m<=q-1,故此时m可以用1代替。与N对应的以前的数为qk+m,即qk+(N-n-(q-1)k)=N-n+k.

由此可以得到计算方法如下：

N=qn;

While N>n

         N=N-n+floor((N-n-1)/(q-1)); (1)

Ans=N

上面这个式子使用自下向上的方法求原始标号。我们可以通过适当的变量代换来实现从上往下的方法进行求解。

令D=qn+1-N,带入(1)式化简可得：

D=ceil(q/(q-1)*D)

所以有：

D=1:

While D<=(q-1)n

         D= ceil(q/(q-1)*D)

Ans=qn+1-D

Ans即为最后的答案。