数据结构—约瑟夫问题

旧城等待， 2022-08-21 07:49 172阅读 0赞

### 1、约瑟夫问题： ###

### 约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3，1。 ###

### 分析： ###

### （1）由于对于每个人只有死和活两种状态，因此可以用布朗型数组标记每个人的状态，可用true表示死，false表示活。 ###

### （2）开始时每个人都是活的，所以数组初值全部赋为false。 ###

### （3）模拟杀人过程，直到所有人都被杀死为止。 ###

#include <iostream>
    <pre name="code" class="cpp">using namespace std;
    int main()
    {
        int a[101]={0};    //圈中有人则都记为0，被杀掉则为1
        int n,m,f=0,t=0,s=0;
        cin>>n>>m;
        do
        {
            ++t;          //逐个枚举圈中的所有位置
            if(t>n)
                t=1;      //数组模拟环状，最后一个与第一个相连
            if(!a[t])
                s++;      //如果第t个有人，则报数
            if(s==m)      //当前报数为m
            {
                s=0;      //计数器清零
                cout<<t<<" ";   //输出被杀人编号
                a[t]=1;     //此人已死，置1
                f++;     //死亡人数加1
            }
        }while (f!=n);    //直到所有人都死为止
        return 0;
    }

运行结果： ![Center][]

### 2、求解约瑟夫问题： ###

### 设有n个人站成一圈，其编号为1~n，从编号为1的人开始按顺时针方向“1、2、3、4，...”循环报数，数到m的人出列，然后从出列者的下一个人开始重新报数，数到m的人又出列，如此重复进行，直到n个人都出列为止。要求输出这n个人的出列顺序。 ###

#include <iostream>
    #define MaxSize 100
    using namespace std;
    void josephus(int n,int m)
    {
        int p[MaxSize];
        int i,j,t;
        for(i=0; i<n; i++)         //构建初始序列
            p[i]=i+1;
        t=0;                       //首次报数的起始位置
        cout<<"出列顺序：";
        for(i=n; i>=1; i--)        //i为数组p中的人数
        {
            t=(t+m-1)%i;           //t为出列者的编号
            cout<<p[t]<<" ";       //输出为t的元素序列
            for(j=t+1; j<=i-1; j++)     //后面的元素前移一个位置
                p[j-1]=p[j];
        }
        cout<<endl;
    }
    int main()
    {
        int n,m;
        cin>>n>>m;
        josephus(n,m);
        return 0;
    }

运行结果：  
![Center 1][]

### 3、问题描述：n个人（编号0~(n-1）），从0开始报数，报到（m-1）的退出，剩下的人继续从0开始报数。求胜利者的编号。 ###

#include <iostream>
    using namespace std;
    
    int main()
    {
        int n,m,f=0;
        cin>>n>>m;
        for(int i=1;i<=n;i++)
            f=(f+m)%i;
        cout<<f+1<<endl;
        return 0;
    }

运行结果：

![Center 2][]

### 4、一堆猴子都有编号，编号是1，2，3 ...n，这群猴子（n个）按照1-n的顺序围坐一圈，从第1开始数，每数到第m个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 ###

注：用数组模拟链表

#include <iostream>
    #include <malloc.h>
    using namespace std;
    int main()
    {
        int *person,i,node,n,m;
        cin>>n>>m;
        person=(int *)malloc(sizeof(int)*(n+1));
        for(i=1;i<=n;i++)   //初始化圈
            person[i]=i+1;     //i表示编号为i的人，person[i]的值表示表示编号为i的人的下一个编号
        person[n]=1;     //编号为n的下个人的编号为1
        node=1;
        while(node!=person[node])   //如果某人的下一个人不是他自己，表示人数超过1人
        {
            for(i=1;i<m-1;i++)    //此循环结束于被杀人的前一个人的编号
                node=person[node];   //找到被杀人的前一个人的编号
            cout<<person[node]<<" ";   //输出被杀人的编号
            person[node]=person[person[node]];   //将被杀人的前一人与后一人相连
            node=person[node];             //从被杀人的后一人开始再一次的循环
        }
        cout<<node<<endl;    //输出最后一人
        return 0;
    }

运行结果：

![Center 3][]

[Center]: /images/20220724/bfa566282c2447d9ad935f38f4f74f28.png
[Center 1]: /images/20220724/c364890779ff483db293618aaae77693.png
[Center 2]: /images/20220724/37ba9a87432b4e669a1dc98f1018c849.png
[Center 3]: /images/20220724/e3beb04b741445c7876c6278373bc9da.png