程序员面试系列——约瑟夫环

约瑟夫斯问题（Josephus Problem）

约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为“约瑟夫环”，也有的地方叫做“丢手绢”。

问题是这样的：
有编号从1 到n的 n个人围坐成一圈。从编号为1的人开始报数，报到 m 的人出局，下一位再从 1 开始报数，报到 m 的人出局，……如此持续，直到剩下一人为止，假设此人的原始编号是x。给定 n和 m，求出x。

为了说明问题，我们举个例子。这个例子中n=4, m=2. 最终结果x=1.
以下是示意图（横着看）

思路一：编程模拟

若编程解决此问题，很容易想到用数组或者循环链表模拟整个过程，直到剩下一个人。

用数组模拟

C语言代码如下。

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

void josephus(int n,int m)  //一共n个人，报m的人被淘汰
{
    if((n<=1) || (m<=1)) //n和m最小是2
        return;

    //数组的下标作为每个人的编号。a[0]不使用
    int *a = (int *)malloc(sizeof(int)*(n+1)); 
    if(a==NULL)
    {
        printf("内存分配失败\n");
        return;
    }
    int i;
    for(i=1;i<n+1;++i)
        a[i]=1; // 初始化，1表示人存在

    int count = 0; //用来模拟报数，取值从0到m 
    int left = n; // 用来记录剩下的人数
    while(1)
    {
        for(i=1;i<=n;++i)
        {
            if(a[i]) //如果人存在
            {               
                ++count; //模拟报数，这里取值从1到m
                if(count == m)
                {
                    a[i]=0;          //此人被淘汰
                    printf("%d ",i); //打印被淘汰的人的编号
                    count=0;         //重置为0，准备下一轮报数
                    --left;
                    if(left == 1)    //说明只剩一个人,这时候跳出死循环
                        goto out;
                } 
            }               
        }
    }

out:
    for(i=1;i<=n;++i)
    {
        if(a[i])      //找到最后的那个人，打印其编号
        {
            printf("%d ",i);
            break;
        }
    }
    printf("\n");

    free(a);
}


int main(void) //测试代码
{
    josephus(41,3); 
    return 0;
}

运行结果如下：

3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31

为了验证结果的正确，除了人工计算外，我从网上找了一张图片来对比：

用循环链表模拟

【错误的代码】本来想删除这部分内容，算了，留个纪念吧。

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

void josephus(int n,int m);

int main(void)
{
    josephus(41,3);
    return 0;
}


struct node
{
    int data;
    struct node *next;
};
typedef struct node node_t;



void josephus(int n,int m)
{
    // 创建头结点
    node_t *head = (node_t *)malloc(sizeof(node_t));
    if(head==NULL)
    {
        printf("内存分配失败\n");
        return;
    }

    node_t *pre = head;
    node_t *cur;

    for(int i=1;i<=n;++i)
    {
        cur = (node_t *)malloc(sizeof(node_t));
        if(cur==NULL)
        {
            printf("内存分配失败\n");
            return;
        }
        cur->data = i;  //用data字段存储编号
        pre->next = cur;
        pre = cur;
    }   //以上带头结点的单向链表创建完毕，此时cur指向最后一个结点

    cur->next = head->next; //最后一个结点的next域指向第一个结点，构成循环链表

    cur = head->next; // 让cur指向第一个人
    free(head);   //头结点不再使用，释放头结点

    int skip;
    while(n--)  //每次循环淘汰一人（包括胜利者），循环n次
    {
        skip = m-1; //从1报数到m,即跳过（m-1）个人
        while(skip--)
        {
            pre = cur;
            cur = cur->next;     //cur指向下一个人
        }
        pre->next = cur->next;   //淘汰一人
        printf("%d ",cur->data); //打印被淘汰者的编号
        free(cur);               //释放结点 
        cur = pre->next;         //从1开始报数，cur指向报1的人     
    }
    printf("\n");
}

测试上面的代码，虽然结果正确，但是我发现了一个BUG，请注意64~65这两行

        free(cur);               //释放结点 
        cur = pre->next;         //从1开始报数，cur指向报1的人 

当执行最后一次循环体的时候，此时只剩一个人，cur和pre指向的是同一个地址，执行完free(cur);与此地址关联的内存已经被释放，cur和pre都不能被引用了（除非它们又指向了其他有效的内存区域）。但是，cur = pre->next这条语句又引用了pre。所以，这是一个BUG！

所以，我修改了while循环（见下面33~46行）。
【正确的代码】

void josephus(int n,int m)
{
    // 创建头结点
    node_t *head = (node_t *)malloc(sizeof(node_t));
    if(head==NULL)
    {
        printf("内存分配失败\n");
        return;
    }

    node_t *pre = head;
    node_t *cur;

    for(int i=1;i<=n;++i)
    {
        cur = (node_t *)malloc(sizeof(node_t));
        if(cur==NULL)
        {
            printf("内存分配失败\n");
            return;
        }
        cur->data = i;  //用data字段存储编号
        pre->next = cur;
        pre = cur;
    }   //以上带头结点的单向链表创建完毕

    cur->next = head->next; //最后一个结点的next指向第一个结点，构成循环链表

    cur = head->next; // cur指向第一个人
    free(head);   //头结点不再使用，释放头结点

    int skip;
    while(cur->next != cur)  //不断淘汰，直到剩下一个人
    {
        skip = m-1; //从1报数到m,即跳过（m-1）个人
        while(skip--)
        {
            pre = cur;
            cur = cur->next;     //cur指向下一个人
        }
        pre->next = cur->next;   //淘汰
        printf("%d ",cur->data); //打印被淘汰者的编号
        free(cur);               //释放结点

        cur = pre->next;         //从1开始报数，cur指向报1的人 
    }   
    printf("%d\n",cur->data);    //打印最后一个人的编号
    free(cur);
}

思路二：数学公式法

无论是用数组还是用循环链表求解，都有一个共同点——要模拟整个过程，时间复杂度高达O(n*m)，当n*m非常大（例如上百万、上千万）的时候，是非常耗时间的。

注意到原问题仅仅要求算出最后胜利者的编号，而不是要求模拟整个过程。因此要追求效率，就要打破常规，比如利用数学方法。

为了讨论方便，先把问题稍微改变一下，并不影响原意。

有编号从0 到n-1的 n个人围坐成一圈。从编号为0的人开始报数，报到 m-1 的人出局，下一位再从 0 开始报数，报到 m-1 的人出局，……如此持续，直到剩下一人为止，假设此人的原始编号是x。给定 n和 m，求出x。

还是以n=4, m=2为例，每淘汰一个人后（绿色表示），我们给余下的人重新编号（从0开始编），示意图（竖着看）如下。

令 f(i) 表示i个人玩此游戏最后胜利者的编号，那么本问题就是求f(n).
不管多少人玩这个游戏，最后胜出者的新编号都是0，所以我们规定
f(1)=0;
由上图第一行可以得出：
f(2)=0, f(3)=2, f(4)=0;
其中的规律是：
f[i]=(f[i-1]+m)%i; (i>1)

也就是说递推公式如下：
f[i]=0; (i=1)
f[i]=(f[i-1]+m)%i; (i>1)

公式的证明可以参考*，这里略去。
根据公式我们就可以写出代码，C语言代码如下。

void josephus(int n,int m)
{
    int s = 0;
    for(int i=2; i<=n; ++i)
    {
        s = (s+m)%i;
    }
    printf("the winner = %d\n",s);
}

测试代码是

int main(void)
{
    josephus(41,3);
    return 0;
}

运行结果是

the winner = 30

如果编号从1开始，那么获胜者的编号是31，这和前两种方法得出的结果是一致的。

【参考资料】
[1] *https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98
[2] http://mathworld.wolfram.com/JosephusProblem.html
[3] http://blog.163.com/[email protected]/blog/static/157591739201321341221179/