三大类Josephus数

关于Josephus数，应该是比较古老滴了，ccy继续古老中……

 

游戏规则：假设n 个竞赛者排成一个环形，依次顺序编号1，2，…，n。从某个指定号数开始，沿环计数，每数到第m个人就让其出列，且从下一个人开始重新计数，继续进行下去。这个过程一直进行到所有的人都出列为止。记为(n,m)-Josephus。

 

第一类：从1号开始，m=2，最后一个出列的人的编号为第一类Josephus数。

J(1)=1

这个嘛，显而易见。

J(2n)=J(n)*2-1    n>1

如图所示，求J(2n)时，因为是2n，所以，第一轮去掉后一定剩下n个数字，这n个数字是1，3，5，……，2n-1，且再一次踢人也是从编号1开始，这与1，2，3，……，n最后剩下的数字的相对位置一定相同，所以，只需要找1，3，5，……，2n-1与1，2，3，……，n的关系，这个很明显，2倍-1，所以，有递推式：J(2n)=J(n)*2-1。

J(2n+1)=J(n)*2+1     n>1

同上。

这里，第一轮踢人后，编号1一定会被踢，从新一轮开始是从编号3开始。

 

根据递推式，得出有J(n) = 1 + (n << 1) - (2 << (int)(lg(n)/lg(2)))。

关于这个神奇的式子，ccy确实不知道是怎么由那两个递推式推出来的，只能够silly的用数学归纳法证了下。注意，在证明的时候，处理lg时，要抓住这里m=2这个特殊条件。然后，证明很简单，相信上过一堂数学归纳法的同学们都可以证。

 

第二类：m不是个常数，从编号1开始计数，最后一个剩下的人为第二类Josephus数。

ccy前面写Josephus排列的时候有特别说过，这里，重复一下：

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。我们知道第一个人(编号一定是(m-1)%n) 出列之后，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）:
　　k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
　　并且从k开始报0。
　　现在我们把他们的编号做一下转换：
　　k --> 0
　　k+1 --> 1
　　k+2 --> 2
　　...
　　...
　　k-3 --> n-3
　　k-2 --> n-2
　　变换后就完完全全成为了(n-1)个人报数的子问题，假如我们知道这个子问题的解：例如x是最终的胜利者，那么根据上面这个表把这个x变回去不刚好就是n个人情况的解吗？！！变回去的公式很简单，相信大家都可以推出来：x‘=(x+k)%n如何知道(n-1)个人报数的问题的解？对，只要知道(n-2)个人的解就行了。(n-2)个人的解呢？当然是先求(n-3)的情况 ---- 这显然就是一个倒推问题！好了，思路出来了，下面写递推公式：
    令f表示i个人玩游戏报m退出最后胜利者的编号，最后的结果自然是f[n]递推公式
    f[1]=0;
　　f=(f[i-1]+m)%i; (i>1)

 

    其实，这个递推式，ccy纠结了n久，还是以（7，3）为例。

    0 1 2 3 4 5 6

    3 4 5 6 0 1

    6 0 1 3 4         ...

    3 4 6 0           f[4]=(1+3)%4=0

    0 3 4             f[3]=(1+3)%3=1

    0 3               f[2]=(0+3)%2=1

    3                 f[1]=0

    从上往下看，出队后，每个数向前移动m位，即-m，所以，反推时是+m。

 

第三类：m不是常数，开始计数的编号不是1，然后，最后剩的那个数就是第三类Josephus数。

这个很easy，就是第二类Josephus数+start_number-1。

 

第四类：定义第k个出列的人的号码为第四类Josephus数。

这个依然可以借助第二类的思想。

只不过，这时的初始条件不再是f[1]=0,而是f[n-k+1]=m-1;

还是借助下图：

n=7,m=3,k=3;

    0 1 2 3 4 5 6      f[7]=(5+3)%7=1;

    3 4 5 6 0 1        f[6]=(2+3)%6=5;

    6 0 1 3 4          f[7-3+1]=f[5]=2;   

    3 4 6 0          

    0 3 4            

    0 3              

    3               

 

****************************************************************

忽忽，终于完了，四类Josephus数，看完是不是也觉得很古老呢？O(∩_∩)O~

嗯，怎么说呢，觉得比ccy想象中的简单，主要是前天着Josephus虐了，对它极为恐惧。

哈哈，ccy又成功征服了……（虽然是简单问题呢……o(╯□╰)o……）

鼓掌……撒花……