约瑟夫生者死者游戏.docx
- 文档编号:18216468
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:14
- 大小:183.65KB
约瑟夫生者死者游戏.docx
《约瑟夫生者死者游戏.docx》由会员分享,可在线阅读,更多相关《约瑟夫生者死者游戏.docx(14页珍藏版)》请在冰点文库上搜索。
约瑟夫生者死者游戏
课程设计报告
约瑟夫生者死者游戏
学生姓名:
专业:
班级:
学号:
指导教师:
2017年3月29日
一、实验题目
约瑟夫生者死者游戏
二、实验目的
本次课程设计的主要目的是综合运用所学的数据结构知识解决Jonsepu环问题,侧重对循环链表等相关内容的综合应用,使自己能进一步熟悉掌握数据结构的基础知识,进一步提升自己的解决问题和编程调试能力,为后续专业课程的学习打下良好的基础。
三、实验要求
设计要求
本游戏的数学建模如下:
假设n个旅客排成一个环形,依次顺序编号1,2,…,n。
从某个指定的第1号开始,沿环计数,每数到第m个人就让其出列,且从下一个人开始重新计数,继续进行下去。
这个过程一直进行到剩下k个旅客为止。
本游戏的要求用户输入的内容包括:
1.旅客的个数,也就是n的值;
2.离开旅客的间隔数,也就是m的值;
3.所有旅客的序号作为一组数据要求存放在某种数据结构中。
本游戏要求输出的内容是包括
1.离开旅客的序号;
2.剩余旅客的序号;
四、实现过程
1、总体设计:
1.主流程图:
2.Out函数流程图
是
2、详细设计:
1.结构体
typedefstructJonse/*定义结构体*/
{
intcode;/*编号(分配位置)*/
structJonse*next;
}jonse;
2.链表的构造函数
jonse*Create(intn)/*建立n个节点的单向循环链表函数*/
{
Jonse*h,*p;
inti;
h=(Jonse*)malloc(sizeof(Jonse));/*为头结点分配空间*/
p=h;
for(i=1;i<=n;i++)/*建立n个节点的单向链表*/
{
p->code=i;
if(i { p->next=(Jonse*)malloc(sizeof(Jonse));/*创建新节点*/ p=p->next; } } p->next=h;/*返回头结点,完成单向循环链表的建立*/ returnh; } 3.输出链表的函数 voidShowList(Jonse*h)/*打印链表函数*/ { Jonse*p; p=h; do { printf("%d\t",p->code); p=p->next; }while(p! =h); } 4.实现将人剔除的函数 voidOut(Jonse*h,inti,intd,ints)/*出队函数*/ { intc; c=s; Jonse*p,*q; intk; p=h; for(q=h;q->next! =h;q=q->next);/*初始化链表*/ for(k=1;k 设置好开始报数的人所在位置*/ { q=p;p=p->next; } while(p! =p->next)/*循环删除队列结点*/ { for(k=1;k { q=p; p=p->next; } printf("%d",p->code);/*输出被踢节点的位置*/ q->next=p->next; free(p);/*释放被踢出的结点*/ p=NULL;/*让p指针赋值为空指针*/ p=q->next; flag++; if(num-flag==c)break; } printf("\n剩余游客的编号: \n"); //free(p);/*释放被踢出的结点*/ p=NULL;/*让p指针赋值为空指针*/ p=h; do { printf("%d",p->code); p=p->next; }while(p! =h); printf("\n"); } 3、调试分析: 程序的编写和调试基本正常。 遇到的问题主要是: 链表的指向的边界问题。 本实验采用数据抽象与模块化程序设计方法,思路清晰,实验时调试顺利,各模块具有很好的可重用性,得到了一次良好的程序设计训练。 本实验算法是使用循环链表的方法,由于这种方法在删除一个节点后对其他节点的位置改动放不大,所以很浪费时间,每次都删除第m个数字,都要用O(m)的时间,一共有n个数字,想要剩下一个,其余都要删除,那么就要用(n-1)*O(m)的时间,所以算法的时间复杂度为O(mn)。 还可以用数组来实现本实验,减少时间的浪费。 4、运行结果: 1.要求输入参与者的总人数: 2.打印出创建好的链表,并提示输入开始报数的位置: 3.输入报数人所在的位置,并提示输入报数的最大值: 4.输入报数的最大值,并提示输入留下的人数: 5.输入留下人数,计算显示结果: 结果为删除的人所在的位置和留下的人数: 5、实验总结: 通过本次课程设计的锻炼,使我对数据结构又有了许多新的深刻认识,更深的理解了数据结构的难点,并且通过这次课程设计,我把以前认为没有实际用途的知识转化为了实际问题来解决,非常有意思,同时也觉得这种学习方法,更好的提高学习的效率,以下就是我做这次课程设计的主要体会: 一方面,在程序设计语言中,每一个数据都属于某种数据类型。 类型明显或隐含地规定了数据的取值范围、存储方式以及允许进行的运算。 另一方面,在程序设计过程中,当需要引入某种新的数据结构时,总是借助编程语言所提供的数据类型来描述数据的存储结构。 同时,做好课程设计更能体现出同学的学习态度,对于新知识的渴望与追求,能够反映出同学对自己负责任的态度。 五、参考文献 [1]严蔚敏,吴伟民,《数据结构》,北京: 清华大学出版社,2006年 [2]苏小红,《C语言程序设计》(第3版)2015年 六、附录 #include #include typedefstructJonse/*定义结构体*/ { intcode;/*编号(分配位置)*/ structJonse*next; }jonse; jonse*Create(intn); voidShowList(Jonse*); voidOut(Jonse*,int,int,int); intflag,num; /*主函数*/ main() { Jonse*head; intval,beg,huo; flag=0; printf("\n请输入游客总人数: "); scanf("%d",&num); head=Create(num); ShowList(head); printf("\n请输入报数的人所在位置: "); scanf("%d",&beg); printf("\n请输入报数最大值: "); scanf("%d",&val); printf("\n请输入留下的人数: "); scanf("%d",&huo); printf("\n将被扔下大海的游客的编号: \n"); Out(head,beg,val,huo); return0; } jonse*Create(intn)/*建立n个节点的单向循环链表函数*/ { Jonse*h,*p; inti; h=(Jonse*)malloc(sizeof(Jonse));/*为头结点分配空间*/ p=h; for(i=1;i<=n;i++)/*建立n个节点的单向链表*/ { p->code=i; if(i { p->next=(Jonse*)malloc(sizeof(Jonse));/*创建新节点*/ p=p->next; } } p->next=h;/*返回头结点,完成单向循环链表的建立*/ returnh; } voidShowList(Jonse*h)/*打印链表函数*/ { Jonse*p; p=h; do { printf("%d\t",p->code); p=p->next; }while(p! =h); } voidOut(Jonse*h,inti,intd,ints)/*出队函数*/ { intc; c=s; Jonse*p,*q; intk; p=h; for(q=h;q->next! =h;q=q->next);/*初始化链表*/ for(k=1;k 设置好开始报数的人所在位置*/ { q=p;p=p->next; } while(p! =p->next)/*循环删除队列结点*/ { for(k=1;k { q=p; p=p->next; } printf("%d",p->code);/*输出被踢节点的位置*/ q->next=p->next; free(p);/*释放被踢出的结点*/ p=NULL;/*让p指针赋值为空指针*/ p=q->next; flag++; if(num-flag==c)break; } printf("\n剩余游客的编号: \n"); //free(p);/*释放被踢出的结点*/ p=NULL;/*让p指针赋值为空指针*/ p=h; do { printf("%d",p->code); p=p->next; }while(p! =h); printf("\n"); }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 约瑟夫 死者 游戏