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

简介: 返回:贺老师课程教学链接  项目要求【项目-Josephus(约瑟夫环)问题】n个小孩子围成一圈,从第一个小孩子开始顺时针方向数数字,到第m个小孩子离开,这样反反复复,最终只剩下一个小孩子,求第几个小孩子留下?    提示:约瑟夫环即是一个首尾相连的链表,在建立好这个环以后,从头结点开始,每次间隔m孩子删除一个结点,直至只余下一个结点(删除了n-1个)。    参考下面的代码,也可以自行

返回:贺老师课程教学链接  项目要求


【项目-Josephus(约瑟夫环)问题】
n个小孩子围成一圈,从第一个小孩子开始顺时针方向数数字,到第m个小孩子离开,这样反反复复,最终只剩下一个小孩子,求第几个小孩子留下?
    提示:约瑟夫环即是一个首尾相连的链表,在建立好这个环以后,从头结点开始,每次间隔m孩子删除一个结点,直至只余下一个结点(删除了n-1个)。


    参考下面的代码,也可以自行设计类。

//链表结点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;
}



目录
相关文章
|
24天前
|
存储 C++
【C++篇】C++类和对象实践篇——从零带你实现日期类的超详细指南
【C++篇】C++类和对象实践篇——从零带你实现日期类的超详细指南
23 2
【C++篇】C++类和对象实践篇——从零带你实现日期类的超详细指南
|
24天前
|
存储 编译器 C语言
C++类与对象深度解析(一):从抽象到实践的全面入门指南
C++类与对象深度解析(一):从抽象到实践的全面入门指南
44 8
|
6月前
|
C++
C++代码的可读性与可维护性:技术探讨与实践
C++代码的可读性与可维护性:技术探讨与实践
100 1
|
2月前
|
C++
c++继承层次结构实践
这篇文章通过多个示例代码,讲解了C++中继承层次结构的实践应用,包括多态、抽象类引用、基类调用派生类函数,以及基类指针引用派生类对象的情况,并提供了相关的参考链接。
|
5月前
|
关系型数据库 MySQL 测试技术
技术分享:深入C++时间操作函数的应用与实践
技术分享:深入C++时间操作函数的应用与实践
43 1
|
5月前
|
C++
C++解决线性代数矩阵转置 小实践
【6月更文挑战第3天】C++解决线性代数矩阵转置
66 2
|
5月前
|
存储 算法 安全
用C++打造极致高效的框架:技术探索与实践
本文探讨了如何使用C++构建高性能框架。C++凭借其高性能、灵活性和跨平台性成为框架开发的理想选择。关键技术和实践包括:内存管理优化(如智能指针和自定义内存池)、并发编程(利用C++的并发工具)、模板与泛型编程以提高代码复用性,以及性能分析和优化。在实践中,应注意代码简洁性、遵循最佳实践、错误处理和充分测试。随着技术发展,不断提升对框架性能的要求,持续学习是提升C++框架开发能力的关键。
103 1
|
5月前
|
C++
C++程序设计实践一上(题目来自杭州电子科技大学ACM)
C++程序设计实践一上(题目来自杭州电子科技大学ACM)
33 2
|
5月前
|
C++
C++程序设计实践一下(题目来自杭州电子科技大学ACM)
C++程序设计实践一下(题目来自杭州电子科技大学ACM)
40 1
|
5月前
|
存储 编译器 程序员
C++语言基础学习
C++语言基础学习