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

比眉伴天荒 2022-06-12 04:19 294阅读 0赞

# 约瑟夫斯问题（Josephus Problem） #

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

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

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

![这里写图片描述][SouthEast]

# 思路一：编程模拟 #

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

## 用数组模拟 ##

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

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

![这里写图片描述][20170716121100214]

## 用循环链表模拟 ##

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

#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开始编），示意图（竖着看）如下。

![这里写图片描述][SouthEast 1]

令 `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][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][http_mathworld.wolfram.com_JosephusProblem.html]  
\[3\] [http://blog.163.com/soonhuisky@126/blog/static/157591739201321341221179/][http_blog.163.com_soonhuisky_126_blog_static_157591739201321341221179]

[SouthEast]: /images/20220612/b24eeeb867fc40b8a70c517c9618f872.png
[20170716121100214]: /images/20220612/fc072530e7494bdd87f5996041709e55.png
[SouthEast 1]: /images/20220612/50b34cdfc6a54ed081fe46e7b9cae1b5.png
[https_zh.wikipedia.org_wiki_E7_BA_A6_E7_91_9F_E5_A4_AB_E6_96_AF_E9_97_AE_E9_A2_98]: https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98
[http_mathworld.wolfram.com_JosephusProblem.html]: http://mathworld.wolfram.com/JosephusProblem.html
[http_blog.163.com_soonhuisky_126_blog_static_157591739201321341221179]: http://blog.163.com/soonhuisky@126/blog/static/157591739201321341221179/