约瑟夫问题(数组+队列+公式迭代+递归)

青旅半醒 2023-10-06 18:34 32阅读 0赞

## 约瑟夫问题(数组+队列+公式迭代+递归) ##

约瑟夫环问题起源于一个犹太故事：  
罗马人攻占了桥塔帕特，41个人藏在一个山洞中躲过了这场浩劫。这41个人中，包括历史学家Josephus（约瑟夫）和他的一个朋友。剩余的39个人为了表示不向罗马人屈服，决定集体自杀。大家制定了一个自杀方案，所有这41个人围成一个圆圈，由第一个人开始顺时针报数，每报数为3的人就立刻自杀，然后再由下一个人重新开始报数，仍然是每报数为3的人就立刻自杀……，直到所有的人都自杀身亡为止。约瑟夫和他的朋友并不想自杀，于是约瑟夫想到了一个计策，他们两个同样参与到自杀方案中，但是最后却躲过了自杀。

简化一下问题(不这么血腥的例题):

--------------------

设有n个人围坐一圈，编号为1到n，现从编号为1的人开始报数，数到m的人出列，接着从出列的下一个编号（人）开始重新报数，数到m的人出列，如此下去，直到只剩下最后一个人，并输出其编号。

--------------------

例如输入

4 5

输出结果

--------------------

### 用数组的思路很简单（这也是刚开始接触这道题我的做法） ###

基本思路(容易理解):一开始，将全部数字存入数组中并全部初始化为0，定义一个变量c表示当前数到的人的编号，再定义一个变量k表示从1开始数到m的人的个数，再再定义一个变量s表示出圈的人的个数。  
代码如下:

#include<iostream>
    using namespace std;
    int main()
    {
        
        int n,m;//n表示多少个人参与游戏，m表示数到多少个人出圈
        cin>>n>>m;
        int arr[1000]= {
        0}; //0表示人还在圈中
        int k=0;//报数数到几
        int c=0;//当前人的编号
        int s=0;//出圈的人数和
        while(s!=n)
        {
        
            c++;
            if(c>n)c=1;//大于总人数时，重新开始报数
            if(arr[c]==0)
            {
        
                k++;
                if(m==k)
                {
        
                    arr[c]=1;//标记后下次不报数
                    s++;
                    //cout<<c<<" ";
                    k=0;//使下一个人从1开始报数
                }
            }
        }
        cout<<c;
    }

编译结果如下：  
![在这里插入图片描述][20210719150608539.png_pic_center]

--------------------

### 队列的方法（C++） ###

相比于数组，队列的方法更好写，同时也很好理解。

解法：将人数按编号1-n依次存入队列中，然后做双重循环，将队头元素放到队尾，每隔m-1个退出循环，弹出队

头元素（相当于杀掉的人），再一直循环到只剩最后一人为止。

#include<iostream>
    #include<queue>
    using namespace std;
    int main()
    {
        
        queue<int>Q;
        int i,j,n,m;
        cin>>n>>m;
        for(i=1;i<=n;i++)
        {
        
            Q.push(i);
        }
        while(n!=1)
        {
        
            for(j=1;j<m;j++)//相当于j<=m-1；起计数的作用
            {
        
                Q.push(Q.front());//队头元素放到队尾
                Q.pop();//弹出队头元素
            }
            Q.pop();//杀掉的人
            n--;//总人数减一
        }
        cout<<Q.front();
    }

运行结果如下：  
![在这里插入图片描述][20210719150629262.png_pic_center]

当然这里队列queue也可以转换为数组，即用f，r++。。。来做。这里就不写了。

--------------------

### 找规律的方法(公式法) ###

理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。

这里要真正理解可以参考这篇文章  
[点击打开大佬的文章][Link 1]

#include<iostream>
    using namespace std;
    int main()
    {
        
        int n,m;//n表示多少个人参与游戏，m表示数到多少个人出圈
        int k=0;
        cin>>n>>m;//输入n和m
        for(int i=2;i<=n;i++)
        {
        
            k=(k+m)%i;
        }
        cout<<k+1;//记录的是下标，所以要加上1
    }

编译结果如下：  
![在这里插入图片描述][20210719150909685.png_pic_center]

和递归的递推公式相比，似乎看上去很像，但它们之间的思想有着本质的区别。递归推导式是从上到下，不断进入

递归再回溯；而这种推导式，是从下到上，符合正常的逻辑思维，比较容易理解。

--------------------

### 递归的思想比较复杂（其实就是公式法），但代码量炒鸡短。 ###

f(n,k)中的n为未报过数的人数，k为报数的数，等号右边就是最后剩下的人的编号。（从编号1开始）

迭代法 k=5

f(n,k) = \[f(n-1,k) + k\] % n

f(4,5)=2

f(3,5)=1

这样下去，倒推向前。

拓展：

从第一个士兵开始remove ;

f(3,5)=3

f(4,5)=2

显然和前面的规则而言，相当于不是从1开始数数，而是从2开始数数。所以公式不変!只是人数记得改成n-1

f(n,k) = \[f(n-1,k) + k\] % (n-1)

f(4,5) = 2

= \[f(3,5)+5\] % (4-1)

=(3+5)%3

这里遍历多加上了一个变量n用于递归结束的标志。

#include<iostream>
    using namespace std;
    int recursion(int sum,int value,int n)
    {
        
        if(n==1)return(sum+value-1)%sum;//递归结束的标志：剩下最后一个人
        else return (recursion(sum-1,value,n-1)+value)%sum;
    }
    int main()
    {
        
        int n,m;//n表示多少个人参与游戏，m表示数到多少个人出圈
        cin>>n>>m;
        cout<<recursion(n,m,n)+1;
    }

运行结果如下：  
![在这里插入图片描述][20210719150926865.png_pic_center]

--------------------

### 当然除了以上方法外，还有就是循环链表的方法，较为繁琐。这里以后有空再更新。 ###

主要是链表的代码较为复杂又臭又长。

--------------------

## 总结 ##

其实，要你直接写出约瑟夫问题的题目不多，更多的是将几种方法和约瑟夫问题结合起来的题目。因此，个人认为数组，队列的放法必须要掌握，递归和公式法因为不同题目有不同问题，会比较难理解也会很难写出来，链表嘛要是题目没明确规定，还是别了吧！

以上纯个人笔记，若有不对的地方，请及时纠正。

[20210719150608539.png_pic_center]: https://img-blog.csdnimg.cn/20210719150608539.png#pic_center
[20210719150629262.png_pic_center]: https://img-blog.csdnimg.cn/20210719150629262.png#pic_center
[Link 1]: https://blog.csdn.net/u011500062/article/details/72855826?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162667845316780366596287%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=162667845316780366596287&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-1-72855826.pc_search_result_before_js&utm_term=%E7%BA%A6%E7%91%9F%E5%A4%AB%E9%97%AE%E9%A2%98%E5%85%AC%E5%BC%8F&spm=1018.2226.3001.4187
[20210719150909685.png_pic_center]: https://img-blog.csdnimg.cn/20210719150909685.png#pic_center
[20210719150926865.png_pic_center]: https://img-blog.csdnimg.cn/20210719150926865.png#pic_center