约瑟夫问题求解

---

一、问题描述

约瑟夫问题是：有 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;
}

运行结果分析

---

2. 用循环链表求解（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;
}

求解结果

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