约瑟夫问题求解

作者: 零岁的我 | 来源:发表于2020-02-11 11:39 被阅读0次

    一、问题描述

    约瑟夫问题是:有 n 只猴子,按顺时针方向围成一圈选大王(编号为 1~n),从第 1 号开始报数,一直数到 m,数到 m 的猴子退到圈外,剩下的猴子再接着从 1 开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王。编程求输入 n、m 后,输出最后猴王的编号。

    输入数据:每行是用空格分开的两个整数,第一个是 n,第二个是 m(0<m, n<=1 000 000)。最后一行是:
    0 0

    输出要求:对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号。

    输入样例:
    6 2
    12 4
    8 3
    0 0

    输出样例:
    5
    1
    7


    二、求解

    1.用C++ list容器求解

    #include<iostream>
    #include<list>
    using namespace std;
    /*
    约瑟夫问题是:有 n 只猴子,按顺时针方向围成一圈选大王(编号为 1~n),
    从第 1 号开始报数,一直数到 m,数到 m 的猴子退到圈外,剩下的猴子再接着从 1 开始报数。
    就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王。
    编程求输入 n、m 后,输出最后猴王的编号
    */
    int main(int argc,char **argv)
    {
        list<int> monkeys;
        int n,m;
        while(true){
            cin>>n>>m;
            if(n==0 && m==0){  //输入0 0退出游戏
                break;
            }
            monkeys.clear(); //清空list容器
            for(int i=1;i<=n;++i){
                monkeys.push_back(i); //初始化猴子的编号
            }
            list<int>::iterator it=monkeys.begin();
            cout<<"出局monkeys顺序:";
            while(monkeys.size()>1){ //只要容器中不止一只猴子,游戏就要继续
                for(int i=1;i<m;++i){
                    ++it;
                    if(it==monkeys.end())
                        it=monkeys.begin();
                }
                cout<<*it<<" "; //输出出局猴子的编号
                it=monkeys.erase(it);//erase成员函数返回删除元素的下一个元素的迭代器
                if(it==monkeys.end())
                    it=monkeys.begin();
            }
            cout<<endl;
            cout<<monkeys.front()<<endl; //输出最后选出的猴王
        }
        return 0;
    }
    
    
    运行结果分析
    1. 用循环链表求解(C语言实现)
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct Sqlist{
        int val;
        struct Sqlist *next;
    }Sqlist;
    
    //初始化循环链表
    Sqlist *initList(int n)
    {
        Sqlist *head=(Sqlist*)malloc(sizeof(Sqlist));
        head->val=1;
        head->next=NULL;
        Sqlist *body=head;
        int i;
        for(i=2;i<=n;++i){
            Sqlist *tmp=(Sqlist*)malloc(sizeof(Sqlist));
            tmp->val=i;
            tmp->next=NULL;
            body->next=tmp;
            body=body->next;
        }
        body->next=head; //首尾相连
        return head;
    }
    
    //找到编号为k的人开始报数,数到m的人出列
    void findAndKillm(Sqlist *head,int m,int k)
    {
        Sqlist *tmp=head;
        //遍历链表到第k个
        while(tmp->val!=k){
            tmp=tmp->next;
        }
        int i;
        Sqlist *fro=tmp;
    
        while(tmp->next!=tmp){ //当tmp->next=tmp时,说明链表中只剩一个人,即胜利者
            for(i=1;i<m;++i){
                fro=tmp;
                tmp=tmp->next;
            }
            fro->next=tmp->next;
            printf("%d ",tmp->val);
            free(tmp);
            tmp=fro->next;
        }
        printf("\n");
        printf("最后胜出者:%d\n",tmp->val);
    }
    
    void solution()
    {
        int n,m,k;
        while(1){
            printf("输入总人数n:n=");
            scanf("%d",&n);
            printf("数到m的人出列:m=");
            scanf("%d",&m);
            if(n==0 || m==0){
                exit(0);
            }
            Sqlist *head=initList(n);
    
            printf("从第k人开始报数(k>0):k=");
            scanf("%d",&k);
    
            printf("出列人的顺序为:");
            findAndKillm(head,m,k);
        }
    }
    
    int main(int argc,char **argv)
    {
        solution();
        return 0;
    }
    
    
    求解结果

    欢迎不同求解方案探讨
    欢迎点赞!

    相关文章

      网友评论

        本文标题:约瑟夫问题求解

        本文链接:https://www.haomeiwen.com/subject/pvotfhtx.html