算法科普：什么是约瑟夫环

红太狼 2022-02-15 23:53 273阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

### 1 问题描述 ###

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知 n 个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为 k 的人开始报数，数到 m 的那个人出圈；他的下一个人又从 1 开始报数，数到 m 的那个人又出圈；依此规律重复下去，直到剩余最后一个胜利者。

例如：有10个人围成一圈进行此游戏，每个人编号为 1-10 。若规定数到 3 的人出圈。则游戏过程如下。

（1）开始报数，第一个数到 3 的人为 3 号，3 号出圈。  
  1， 2， 【**3**】， 4， 5， 6， 7， 8， 9， 10。  
（2）从4号重新从1开始计数，则接下来数到3的人为6号，6号出圈。  
  1， 2， 【**3**】， 4， 5， 【**6**】， 7， 8， 9， 10。  
（3）从7号重新从1开始计数，则接下来数到3的人为9号，9号出圈。  
  1， 2， 【**3**】， 4， 5， 【**6**】， 7， 8， 【**9**】， 10。  
（4）从10号重新从1开始计数，由于10个人称环形结构，则接下来数到3的人为2号，2号出圈。  
  1， 【**2**】， 【**3**】， 4， 5， 【**6**】， 7， 8， 【**9**】， 10。  
（5）从4号重新从1开始计数，则接下来数到3的人为7号，7号出圈。  
  1， 【**2**】， 【**3**】， 4， 5， 【**6**】， 【**7**】， 8， 【**9**】， 10。  
（6）从8号重新从1开始计数，则接下来数到3的人为1号，1号出圈。  
  【**1**】， 【**2**】， 【**3**】， 4， 5， 【**6**】， 【**7**】， 8， 【**9**】， 10。  
（7）从4号重新从1开始计数，则接下来数到3的人为8号，8号出圈。  
  【**1**】， 【**2**】， 【**3**】， 4， 5， 【**6**】， 【**7**】， 【**8**】， 【**9**】， 10。  
（8）从10号重新从1开始计数，则接下来数到3的人为5号，5号出圈。  
  【**1**】， 【**2**】， 【**3**】， 4， 【**5**】， 【**6**】， 【**7**】， 【**8**】， 【**9**】， 10。  
（9）从10号重新从1开始计数，则接下来数到3的人为10号，10号出圈。  
  【**1**】， 【**2**】， 【**3**】， 4， 【**5**】， 【**6**】， 【**7**】， 【**8**】， 【**9**】， 【**10**】。  
（10）最终剩余 4 号，4 号为胜利者。

### 2 数组求解 ###

#### 2.1 解题思想 ####

用数组求解的基本思想就是用一个一维数组去标识这 n 个人的状态，默认全为 1 ，也就是都在圈子内，当数到 m的人出圈之后，标识置为 0（就是出圈了），同时报数器清 0，下一个人要从 1 开始。在每次报数之前要判断他是否在圈子内（也就是他的标识是否为 1 ），如果在圈子里面才会继续报数。定义一个变量记录出圈的人数， 出圈的人数等于 n-1 时，则游戏结束。

#### 2.2 代码实现 ####

#include<stdio.h>
    #define N 1000000 //记录玩游戏最大人数
    int flag【N】 = {
        0};
    int main()
    {
        
        int n = 0, m = 0;
        scanf("%d%d", &n, &m);//输入玩游戏人数和计数m
        int i = 0;
        int count = 0;  //记录已经出圈的人数
        int num = 0;    //报数器
        for(i = 1; i <= n; i++) {
        
            flag【i】 = 1;//所有人入圈
        }
        while(count < n - 1) {
        
            for(i = 1; i <= n; i++ ) {
        
                if (1 == flag【i】) {
        //在未出圈的人数中计数
                    num++;
                    if(num == m) {
        //此人数到m则出圈
                        printf("%d\n", i);
                        count++;//出圈人数加1
                        flag【i】 = 0;//出圈
                        num = 0;
                    }
                    if(count == n - 1) {
        
                        break;
                    }
                }
            }
        }
        for(i = 1; i <= n; i++) {
        
            if(1 == flag【i】) {
        //输出赢家，标识为1
                printf("The last one is : %d\n", i);
            }
        }
        return 0;
    }

### 3 循环链表求解 ###

#### 3.1 解题思想 ####

约瑟夫环问题可以转化为循环链表的数据结构来求解。可以将每个人看做链表的单个节点，每个节点之间通过链表的 next 指针连接起来，并且将链表末尾节点指向头节点就形成的环，由链表构成的环形结构在数据结构中称为循环链表。

#### 3.2 代码实现 ####

#include <stdio.h>
    #include <stdlib.h>
    
    /*声明一个链表节点*/
    typedef struct node  
    {
         
        int number;//数据域，存储编号数值
        struct node *next;//指针域，指向下一个节点
    }Node;
    
    /*创建链表节点的函数*/ 
    Node* CreatNode(int x) 
    {
        
        Node *p;
        p = (Node*)malloc(sizeof(Node));
        p->number = x;//将链表节点的数据域赋值为编号
        p->next = NULL;
        return p;
    }
    
    /*创建环形链表，存放整数1到n*/
    Node* CreatJoseph(int n) 
    {
        
        Node *head,*p,*q;
        int i;
        for(i = 1;  i <= n; i++)
        {
        
            p = CreatNode(i);//创建链表节点，并完成赋值
            if(i == 1)//如果是头结点
                head = p;
            else//不是头结点，则指向下一个节点
                q->next = p;
                q = p;
        }
        q->next = head;//末尾节点指向头结点，构成循环链表
        return head;
    }
    
    /*模拟运行约瑟夫环，每数到一个数，将它从环形链表中删除，并打印出来*/
    void RunJoseph(int n,int m) 
    {
        
        Node *p,*q;
        p = CreatJoseph(n);//创建循环链表形式的约瑟夫环
        int i;
        while(p->next != p)//循环条件，当前链表数目大于1
        {
        
            for(i = 1; i < m-1; i++)//开始计数
            {
        
                p = p->next;
            }
            //第m个人出圈
            q = p->next;
            p->next = q->next;
            p = p->next;
            printf("%d--",q->number);//输出出圈的序号
            free(q);
        }
        printf("\n最后剩下的数为：%d\n",p->number);
    }
    
    int main()
    {
        
        int n,m;
        scanf("%d %d",&n,&m);
        RunJoseph(n,m);
        return 0;
    }

### 4 递推公式求解 ###

#### 4.1 解题思想 ####

约瑟夫环中，每当有一个人出圈，出圈的人的下一个人成为新的环的头，相当于把数组向前移动 m 位。若已知 n-1 个人时，胜利者的下标位置位 f(n−1,m) ，则 n 个人的时候，就是往后移动 m 位，(因为有可能数组越界，超过的部分会被接到头上，所以还要模 n )，根据此推导过程得到的计算公式为：  
  **f(n,m) = (f(n−1,m) + m) % n**。  
其中，f(n,m) 表示 n 个人进行报数时，每报到 m 时杀掉那个人，最终的编号，f(n−1,m) 表示，n-1 个人报数，每报到 m 时杀掉那个人，最终胜利者的编号。有了递推公式后即可使用递归的方式实现。

#### 4.2 递归代码实现 ####

#include <stdio.h>
    int Joseph(int n,int m)/*计算约瑟夫环的递归函数*/
    {
        
        if(n <= 1 || m <= 1)//设置游戏人数限定值
            return -1;
    
        if(n == 2)//设置边界值
        {
        
            if(m % 2 == 0)
                return 1;
            else
                return 2;
        }
        else
        {
        
            return (Joseph(n-1,m) + m-1) % n+1;//递归调用
        }
    }
    
    int main()
    {
        
        int n,m,x;
        scanf("%d %d",&n,&m);
        x=Joseph(n,m);
        printf("最后一个数为：%d\n",x);
        return 0;
    }

#### 4.3 迭代代码实现 ####

#include <stdio.h>
    /*计算约瑟夫环问题的迭代法函数*/
    int Joseph(int n,int m)
    {
        
        int i;
        int x,y;
        if(n <= 1 || m <= 1)
            return -1;
        if(m % 2 == 0)
            y = 1;
        else
            y = 2;
    
        for(i = 3; i <= n; i++)
        {
        
            x = (y-1 + m) % i + 1;
            y = x;
        }
        return y;
    }
    
    int main()
    {
        
        int n,m,x;
        scanf("%d %d",&n,&m);
        x = Joseph(n,m);
        printf("最后一个的编号是：%d\n",x);
        return 0;
    }

### 实际应用 ###

比如你们公司需要团建，你可以设计这个游戏，根据游戏人数的多少，将你和你心仪的妹子安排在合适的座位上，一同进最后的决赛圈~

**推荐阅读**

[拜托，面试官别问我「布隆」了][Link 1]

[数据结构与算法：三十张图弄懂「图的两种遍历方式」][Link 2]

[昨天，终于拿到了腾讯 offer][offer]

[几道和「二叉树」有关的算法面试题][Link 3]

[几道和散列（哈希）表有关的面试题][Link 4]

[一道看完答案你会觉得很沙雕的「动态规划算法题」][Link 5]

[几道和「堆栈、队列」有关的面试算法题][Link 6]

[链表算法面试问题？看我就够了！][Link 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

欢迎关注![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20220216/d92e6a8fc7844fedb2830bd8ac22aff2.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485011&idx=1&sn=a3031a3d3ad033e44439d42d72753e16&chksm=fa0e69d2cd79e0c45b1eb017c65b60662890f67ec70ef44e92ef7f5cddfc313ea6ab353952f4&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485076&idx=1&sn=ba747d1efd4c009da83681a6bb4ff549&chksm=fa0e6915cd79e003249e9ee045d09a174b0e5aff2a6ecd807e10fd01bfbc1a37da688eb51637&scene=21#wechat_redirect
[offer]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485001&idx=1&sn=cdcebef70aaabcafa3403c2dd51bdfb7&chksm=fa0e69c8cd79e0de12ece3a9e48430099c429aff816cc3a9e40035192dc07a864864888d1078&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484985&idx=1&sn=93343d355abf36c77a361c9931cbe2d1&chksm=fa0e69b8cd79e0ae1e6b57665a456da5f421cc92fe6934337f1eb1e18c3fd6a3c1adc8ca88c2&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484977&idx=1&sn=f4a6148480555e3cca83231ac1df8d02&chksm=fa0e69b0cd79e0a686e31c547fc783eb9663d9fe19cc95ecd524e9f8f7e0d4a168945f8755e5&scene=21#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484875&idx=1&sn=72cf66da1c970ba345e8b1ab3586c10d&chksm=fa0e6a4acd79e35c32c9201e99cc93a71d0f2a331319addf5303c76ac05738b312ab238a8304&scene=21#wechat_redirect
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484846&idx=2&sn=e508da06e9f7a0b3d00db5415d7ce622&chksm=fa0e6a2fcd79e3397fe8083f9493ae639f47c9448ac2a0026026494d098c47ecc6e08f1f8e28&scene=21#wechat_redirect
[Link 7]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484830&idx=1&sn=9d24fc787da4b49b82ac01c7f8de257b&chksm=fa0e6a1fcd79e309a2e7f3e09ec9913a55f1c077287c907f13528578b7785831a2effb3104e0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 1]: /images/20220216/704a984aa2aa4a78bd9af51a051cf4ee.png
[640_wx_fmt_png]: /images/20220216/9915e3b101804893bec7c60db6b17460.png