浅谈约瑟夫环

       最近在看具体数学，再次碰见了我们的老朋友 --- 约瑟夫环问题，通过对其的较为深度的研究，发现了许多有意思的东西，所以写出来分享一下。
       问题描述：
            约瑟夫环问题(Josephus)       
            约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。我们要找出最后一个出列的人的编号。

        看起来百无聊赖的问题，却发现了几个不同的解法，有通用解法，有特殊解法，还有令我感觉十分舒爽的奇思妙想解法（虽然有些局限，但是个人还是比较喜欢）。废话不多说，下面小菜把几种解法一一分享出来。 

        方法一：构建一个可循环的数据结构，例如循环数组，循环链表。从头部遍历，计数到第m个数时，踢出该元素，继续循环，直至剩下最后一个元素，输出最后一个元素的编号。
        下面是我用循环链表实现的代码，对于循环数组，比较简单，就不做解释了。 
        

/*
*     约瑟夫环问题(Josephus)
*     Code by Boy Yue 2014.4.15
*     http://blog.chinaunix.net/uid/29341537.html
*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

//链表节点
typedef struct Linked
{
    int position;
    struct Linked *next;
}LinkNode, *LinkList;

//创建节点并初始化
LinkNode *creatNode(int const number);
//创建约瑟夫环链表
LinkList creatList(int const count);
//循环运算
LinkNode *dealJosephus(LinkList list, int const key);
//当前节点删除
void deleteNode(LinkNode *node);
//输入规模及key值
void input(int *count, int *key);
//显示胜出者
void showWinner(LinkNode *node);

LinkNode *creatNode(int const number)
{
    LinkNode *node = NULL;

    node = (LinkNode *)malloc(sizeof (LinkNode));
    //初始化
    node -> position = number;
    node -> next = NULL;

    return node;
}

LinkList creatList(int const count)
{
    int num = count;
    LinkList jose_list = NULL;
    LinkNode *head = NULL, *node = NULL;

    head = jose_list = creatNode(count - num + 1);

    // 创建循环链表
    while (--num)    {
        node = creatNode(count - num + 1);
        head -> next = node;
        head = node;
    }

    //构成环形
    head -> next = jose_list;

    return jose_list;
}

void deleteNode(LinkNode *node)
{
    LinkNode *node_next = node -> next;

    *node = *node_next;
    //将后一个节点的数据复制到当前节点并删除后一个节点，使时间复杂度为o(1)
    free(node_next);
}

LinkNode *dealJosephus(LinkList list, int const key)
{
    int num = key;
    LinkNode *node = list;

    //当循环链表只有一个节点时返回当前节点
    if (node -> next == node)
        return node;

    while (--num)
        node = node -> next;

    //showWinner(node);

    deleteNode(node);

    //递归调用
    return dealJosephus(node, key);
}

void input(int *count, int *key)
{
    printf ("Person count = ");
    scanf ("%d", count);
    printf ("Key number = ");
    scanf ("%d", key);

    //判断键入的值是否合法
    if (*count <= 0 || *key <= 0)    {
        printf ("Input Error!\n");
        system("pause");
        exit(0);
    }
}

//显示当前节点信息
void showWinner(LinkNode *node)
{
    printf ("The Winner is number %d\n", node -> position);
}

int main()
{
    int count, key;

    input(&count, &key);
    showWinner(dealJosephus(creatList(count), key));

    return 0;
}

            
             方法二：有点动态规划的感觉，不过是数学的递推关系式。想要解决数据规模为n的时候的问题，先解决数据规模为n-1的问题...（小菜认为这应该就是此方法的解题思想吧）
            仔细想一下，假如当前数据规模为n，并且我们已经得到了在此数据规模下第一个出列的人的编号（m%n-1）。那么当第一个人出列后。剩下的n-1个人又组成了一个新的约瑟夫环，且编号是从m%n开始。
            即（m%n），（m%n+1）， ... n，... n-2， n-1， 1， 2， 3，...， m%n-2
                        0                     1           n-m%n  m%n-2 ...............................     n-2 
            胜利者Win = (Win+m%n)%n

            得到递推式：    a[1] = 0
                                     a[k] = (a[k-1] + m) % n
            通过递推式，我们很容易写出代码：

#include <stdio.h>
#include <stdlib.h>

void input(int *count, int *key);
void dealJosephus(int const count, int const key);

void input(int *count, int *key)
{
    printf ("Person count = ");
    scanf ("%d", count);
    printf ("Key number = ");
    scanf ("%d", key);

    //判断键入的值是否合法
    if (*count <= 0 || *key <= 0) {
        printf ("Input Error!\n");
        system("pause");
        exit(0);
    }
}

void dealJosephus(int const count, int const key)
{
    int winner = 0;
    int num;

    for (num = 2; num <= count; num++)
        winner = (winner + key) % num;

    printf ("The Winner is %d\n", winner+1);
}

int main()
{
    int count, key;

    input (&count, &key);
    dealJosephus(count, key);

    return 0;
}

            显然，上面这段代码的时间复杂度要比第一种方法低的多。第一种方法不仅写起来麻烦，而且时间复杂度为O(nm)，而这种方法的时间复杂度仅仅为O(n)。效率上有很大的提升。

            方法三：此方法比较特殊，首先我们先针对m = 2时的情况进行讨论。
            例如n=10为起始。消去的顺序为2，4，6，8，10，3，7，1，9，于是5为胜利者。
            问题：确定幸存者的号码J(n)。
            假设开始有2n个人。经过第一轮后剩下1， 3， 5， 7， ... ， 2n-3， 2n-1。
            而3号就是下一个要离开的人，除了每个人的号码加倍并减去1之外，这刚好跟n个人开始时的情景类似。也就是说我们可以找到递推式J(2n) = 2J(n) - 1， n >= 1。
            现在可以过渡到大的n。例如，已知J(10) = 5，所以J(20) = 2J(10) - 1 = 9。
            类似的有J(40) = 17，并且我们可以推出J(5 * 2^m) = 2^m+1 + 1。
            同样的对于奇数时的情形，我们可以得到递推式 J(2n+1) = 2J(n) + 1， n >= 1。
            把方程组合起来得到递推式：    J(1) = 1
                                                             J(2n) = 2J(n) - 1 ，n >= 1
                                                             J(2n+1) = 2J(n) + 1， n >= 1
                这种方法相比于方法二的由J(n-1)推出J(n)明显要“高效”的多， 因为每次调用它的时候，它都是缩减2倍。因此相比于方法二的O(n)的时间复杂度，方法三的O(log(n))貌似更加快速。
                    但是有没有更加简单的方法了呢？
            上面我们得到了递推式。但是我们仍然需要一个封闭的形式。因为封闭的形式计算起来更加方便快捷。
            如果我们将n写成n = 2^k + l的形式，其中k是不超过n的2的最大幂的指数，而l是指剩下的数。
            那么递归式的解看起来是 J(2^m + l) = 2l + 1， m >= 0， 0  <= l <= 2^m
                我们需要给出这一解析式的证明。很简单，数学归纳法。这里小菜就不再细说了。

            我们在求解的过程中发现2的幂起到了重要的作用，因此我们来看看能不能从2的幂找到突破口。
                假设n的二进制的展开式是：

                                n = (b_m b_m-1 ··· b₁ b₀)₂
        也就是说
                                n = b_m2^m + b_m-12^m-1 + ··· + b₀
         其中每个 b_i 为0或者1，而首位数字b_m是1。所以我们有：
                                n = (1 b_m-1 ··· b₁ b₀)₂
                                           l = (0 b_m-1 ··· b₁ b₀)₂
                               2 l = (b_m-1 ··· b₁ b₀ 0)₂
                                        J(n) = 2 l + 1  =  (b_m-1 ··· b₁ b₀ 1)₂
       我们惊奇的发现n的二进制向左循环移动一位就得到了J(n)！
     
        同样如果是m = 3时，只要转换成三进制就行呢！依次类推、。。
       实在是不可思议！
        例如如果计算 n = 100 = (1100100)₂，那么J(n) = (1001001)₂= 73.
       不过这种方式有些缺陷。比如当n = 13 时，J(13) = J((1101)₂ ) = (111)₂ = 7并不是正确结果。
     当0为首位时它会消失，导致结果错误。对于其详细的解释以及这种方法的改进推广延伸，有兴趣的话，小伙伴们可以自己研究研究，具体数学中也有较为详细的解释。
        

                
            

                参考书籍：具体数学 ----计算机科学基础(第二版)