C++语言基础实践参考——Josephus 约瑟夫环问题

桃扇骨 2022-04-16 05:26 179阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

返回：[贺老师课程教学链接][Link 1] [项目要求][Link 2]

【项目-Josephus(约瑟夫环)问题】  
n个小孩子围成一圈，从第一个小孩子开始顺时针方向数数字，到第m个小孩子离开，这样反反复复，最终只剩下一个小孩子，求第几个小孩子留下？  
提示：约瑟夫环即是一个首尾相连的链表，在建立好这个环以后，从头结点开始，每次间隔m孩子删除一个结点，直至只余下一个结点（删除了n-1个）。  
![20130604071651484][]  
  
参考下面的代码，也可以自行设计类。

//链表结点kid,其中number为这个人的编号struct kid{
             int number;    kid *next;};//约瑟夫环类class joseph_ring{
         private:    int n;//用于存放人数    int m;//用于存放初始密码    kid *head;//链表的头结点，初始化时指向1号孩子public:    joseph_ring(int nn, int mm);//创建nn个孩子，间隔为mm的约瑟夫环    void show();//运算并输出的成员函数};//定义joseph_ring类中的成员函数……int main(){    int n,m;    cout<<"n=";    cin>>n;    cout<<"m=";    cin>>m;    joseph_ring j(n,m);    j.show();    return 0;}

\[参考解答\]

#include <iostream>using namespace std;//链表结点kid,其中number为这个人的编号struct kid{
             int number;    kid *next;};//约瑟夫环类class joseph_ring{
         private:    int n;//用于存放人数    int m;//用于存放间隔    kid *head;//链表的头结点public:    joseph_ring(int nn, int mm);//创建nn个孩子，间隔为mm的约瑟夫环    ~joseph_ring();    void show();//运算并输出的成员函数};//创建nn个孩子，间隔为mm的约瑟夫环joseph_ring::joseph_ring(int nn, int mm){    n=nn;    //构造函数,把成员变量赋初值    m=mm;    kid *p1,*p2; //定义2个临时指针    for(int i=1; i<=n; i++)//for循环用于初始化环    {        p1=new kid;        p1->number=i;  //编号        if(i==1)       //如果当前链表为空,头指针指向第一个人        {            head=p1;            p2=p1;        }        else     //否则,p2永远指向尾结点,新建立的结点都插入到p2之后        {            p2->next=p1;            p2=p1;        }    }    p2->next=head;//把链表连成一个循环链表}joseph_ring::~joseph_ring(){    delete head;    head=NULL;}void joseph_ring::show()  //执行出圈操作{    kid *p1,*p2,*p;    int count;    p1=head;    for(int i=1; i<=n-1; i++)//有n个人,所以执行n-1次循环，删除n-1个人    {        count=1;  //用count定位到第m个人,循环后,p1指向这个人,p2指向这个人的上一个人        while(count<m)        {            p2=p1;  //p2指向前一个            p1=p1->next;            count++;        }        cout<<p1->number<<"\t";//这指向的是当前要删除人        p=p1;//p指向当前这个人        p2->next=p1->next;//将当前出圈人的直接前驱和直接后继连接起来        p1=p1->next;//下次从当前人的下一个人开始数        delete p;//释放内存    }    cout<<endl;    cout<<"The last one is No. "<<p1->number<<endl;    head=p1; //环中只剩下了一个结点}int main(){    int n,m;    cout<<"n=";    cin>>n;    cout<<"m=";    cin>>m;    joseph_ring j(n,m);    j.show();    return 0;}

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[Link 1]: http://blog.csdn.net/sxhelijian/article/details/8001601
[Link 2]: http://write.blog.csdn.net/postedit/46011465
[20130604071651484]: /images/20220416/912f49b3a2c44ed3bce6191e9ad28aa1.png
[SouthEast]: /images/20220416/0f55ac26a8764923ac73a96da8d360de.png