约瑟夫问题.docx
- 文档编号:2362979
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:19
- 大小:120.42KB
约瑟夫问题.docx
《约瑟夫问题.docx》由会员分享,可在线阅读,更多相关《约瑟夫问题.docx(19页珍藏版)》请在冰点文库上搜索。
约瑟夫问题
《数据结构》实验报告
◎实验题目:
约瑟夫环问题
◎实验目的:
有效掌握循环链表和顺序表的使用,对于两种结构有更深层次的理解。
◎实验内容:
设有N个人围坐一圈,先从某个人开始报数,数到M的人出列,接着从出列的下一个人开始重新报数,数到M的人出列,如此下去,直到所有人都出列为止。
试设计确定他们的出列次序序列的程序。
分别用单向循环链表和顺序表作为存储结构模拟整个过程。
一、需求分析
1.本演示程序中,人数n应为任意的小于等于30的整数,首先应输入一个值赋给初始报数m以及起始位置k,从第k个人开始,程序中会将数到m的人的序号输出,再从输出的人的下一个人开始,再将数到m的人的序号输出,如此循环,直至所有人都出列为止。
2.程序的输出为数到m的人的序号。
3.程序执行的命令包括:
单向循环链表:
(1)创建循环链表
(2)输入总人数、报号数、起始位置的数据(3)执行报数,输出出列人的序号,再进行下一次循环(4)直到所有人都输出结束
顺序表:
(1)创建顺序表
(2)输入总人数、报号数、起始位置的数据(3)执行报数,输出出列人的序号,再进行下一次循环(4)直到所有人都输出结束
4.测试数据
(1)n=8,m=4,k=2,8人的序号依次为:
12345678,则出列次序为51632487。
二概要设计
单向循环链表:
为了实现上述操作,应以单向循环链表为存储结构。
本程序中创建链表函数linklist*create(intn)
操作结果:
构造空链表,若成功就初始化每个人的相关信息
解决约瑟夫问题函数voidjose(linklist*p,intn,intm,intk)两个子函数
初始条件:
线性链表存在
操作结果:
输出报数人序号,释放指向出列的人的结点,并重新报数。
本程序的主程序包括
(1)主程序模块
(2)链表初始化模块
(3)输出报数人序号模块
各程序模块之间的层次(调用)关系
顺序表:
为了实现上述操作,应以顺序表为存储结构。
创建顺序表函数:
voidcreatelist(seqlist&l,intn)
操作结果:
构造空顺序表,若成功就初始化每个人的相关信息
初始化顺序表函数:
voidinitlist(seqlist&l)
操作结果:
使顺序表初始化
删除数到的人的编号函数:
voiddele(seqlist&l,inti)
操作结果:
将数到的人从顺序表中删除
解决约瑟夫问题函数:
voidyusefu(seqlistl,intn,intm,intk)
操作结果:
输出报数人的序号
本程序的主程序包括
(1)主程序模块
(2)顺序表初始化模块
(3)创建顺序表模块
(4)输出报数人序号模块
(5)删除数到的人的编号模块
各程序模块之间的层次(调用)关系
三详细设计
单向循环链表:
1.元素类型,结点类型和指针类型:
typedefintelemtype;
typedefstructlnode
{
elemtypedata;
structlnode*next;
}linklist;
linklist*p,*q,*head;
2.每个模块的分析:
(1)主程序模块:
intmain()
{
intk,n=0,m=0;
linklist*head=NULL;
printf("请输入总人数n:
\n");
scanf("%d",&n);
while(n>30||n==0)/*设定输入条件*/
{
printf("错误\n");
printf("请重新输入总人数n:
\n");
scanf("%d",&n);
}
printf("请输入出列数:
\n");
scanf("%d",&m);
printf("请输入起始位置:
\n");
scanf("%d",&k);
head=create(n);
jose(head,n,m,k);
getchar();
getchar();
return1;
}
(2)链表初始化模块;
linklist*create(intn)
{
linklist*p,*q,*head;
q=NULL;
head=NULL;
inti=1;
head=(linklist*)malloc(sizeof(linklist));/*创建头节点*/
head->data=i;
p=head;
for(i=2;i<=n;i++)
{
q=(linklist*)malloc(sizeof(linklist));
if(q==0)return0;
p->next=q;/*给链表赋值*/
p=q;
p->data=i;
}
p->next=head;/*将指针指向头节点,构成循环链表*/
returnhead;
}
(3)输出报数人序号模块
voidjose(linklist*p,intn,intm,intk)
{
inti,j;
linklist*q=NULL;
for(i=1;i { p=p->next; } for(i=1;i<=n;i++) { for(j=1;j { p=p->next; } q=p->next; p->next=q->next; p=p->next; printf("第%3d个出列号为: %3d\n",i,q->data); free(q); } printf("\n"); } (4)函数调用关系图 main(); linklist*create(); voidjose(); 3.完整的程序: (见源文件). 顺序表: 1.元素类型,结点类型和指针类型: typedefintelemtype; typedefstruct { elemtypedata[maxsize]; intlength; }seqlist; 2.每个模块的分析: (1)主程序模块: intmain() { intk,n=0,m=0; seqlistl; initlist(l); printf("请输入总人数n: \n"); scanf("%d",&n); while(n>30||n==0)/*设定输入条件*/ { printf("错误\n"); printf("请重新输入总人数n: \n"); scanf("%d",&n); } printf("请输入出列数: \n"); scanf("%d",&m); printf("请输入起始位置: \n"); scanf("%d",&k); createlist(l,n); yusefu(l,n,m,k); getchar(); getchar(); return0; } (2)顺序表初始化模块 voidinitlist(seqlist&l) { l.length=0; } (3)创建顺序表模块 voidinitlist(seqlist&l) { l.length=0; } (4)删除数到的人的编号模块 voiddele(seqlist&l,inti) { intj; if(i<1||i>l.length) return; for(j=i+1;j<=l.length;j++) { l.data[j-2]=l.data[j-1];/*调整数组数据*/ } l.length--; } (5)输出数到的人的序号模块 voidyusefu(seqlistl,intn,intm,intk) { inti=k,number=0; while(l.length>1) { number++; if(number==m) { printf("%3d",l.data[i-1]);/*输出查找到的数*/ dele(l,i);/*删除该数并调整数组数据*/ number=0; i=i; if(i>l.length) i=1; } else { i=i+1; if(i>l.length) i=1; } } printf("%3d\n",l.data[0]);/*输出最后一个数据*/ } (6)函数调用关系图 main() initlist() createlist() yusefu() dele() 3.完整的程序: (见源文件). 四使用说明、测试分析及结果 单向循环链表: 1.程序使用说明 (1)本程序的运行环境为VC6.0。 (2)进入演示程序后即显示提示信息: 请输入总人数: 请输入出列数: 请输入起始位置: 2.测试结果 当输入n=8,m=4,k=2,时,则输出正确的出列顺序为: 51632487。 3.调试中的错误及解决办法。 刚开始做时并未考虑输入人数为0的情况,经改正可以解决。 4.运行界面 顺序表: 1.程序使用说明 (1)本程序的运行环境为VC6.0。 (2)进入演示程序后即显示提示信息: 请输入总人数: 请输入出列数: 请输入起始位置: 2.测试结果 当输入n=8,m=4,k=2,时,则输出正确的出列顺序为: 51632487。 3.调试中的错误及解决办法。 刚开始做时并未考虑输入人数为0的情况,经改正可以解决。 4.运行界面 五、实验总结 由于本次问题比较简单,所以花了两个小时编写并调试运行成功,在编写中遇到了数据无法输出的问题,经检查是由于链表指针在指向时发生错误,经改正可以顺利使用,顺序表编写时没有遇到问题,通过这次的编写,对于循环链表以及顺序表的创建及使用有了更深的了解和熟悉。 约瑟夫链表 #include #include #include #defineLENsizeof(linklist) typedefintelemtype; typedefstructlnode { elemtypedata; structlnode*next; }linklist; //创建循环链表 linklist*create(intn) { linklist*p,*q,*head; q=NULL; head=NULL; inti=1; head=(linklist*)malloc(sizeof(linklist));/*创建头节点*/ head->data=i; p=head; for(i=2;i<=n;i++) { q=(linklist*)malloc(sizeof(linklist)); if(q==0)return0; p->next=q;/*给链表赋值*/ p=q; p->data=i; } p->next=head;/*将指针指向头节点,构成循环链表*/ returnhead; } //解决约瑟夫问题 voidjose(linklist*p,intn,intm,intk) { inti,j; linklist*q=NULL; for(i=1;i { p=p->next; } for(i=1;i<=n;i++) { for(j=1;j { p=p->next; } q=p->next; p->next=q->next; p=p->next; printf("第%3d个出列号为: %3d\n",i,q->data); free(q); } printf("\n"); } intmain() { intk,n=0,m=0; linklist*head=NULL; printf("请输入总人数n: \n"); scanf("%d",&n); while(n>30||n==0)/*设定输入条件*/ { printf("错误\n"); printf("请重新输入总人数n: \n"); scanf("%d",&n); } printf("请输入出列数: \n"); scanf("%d",&m); printf("请输入起始位置: \n"); scanf("%d",&k); head=create(n); jose(head,n,m,k); getchar(); getchar(); return1; } 约瑟夫顺序表 #include #include #definemaxsize30 typedefintelemtype; typedefstruct { elemtypedata[maxsize]; intlength; }seqlist; //建立顺序表 voidcreatelist(seqlist&l,intn) { inti; for(i=0;i l.data[i]=i+1; l.length=n; } //初始化顺序表 voidinitlist(seqlist&l) { l.length=0; } //删除数到的人的编号 voiddele(seqlist&l,inti) { intj; if(i<1||i>l.length) return; for(j=i+1;j<=l.length;j++) { l.data[j-2]=l.data[j-1];/*调整数组数据*/ } l.length--; } //对于约瑟夫的求解 voidyusefu(seqlistl,intn,intm,intk) { inti=k,number=0; while(l.length>1) { number++; if(number==m) { printf("%3d",l.data[i-1]);/*输出查找到的数*/ dele(l,i);/*删除该数并调整数组数据*/ number=0; i=i; if(i>l.length) i=1; } else { i=i+1; if(i>l.length) i=1; } } printf("%3d\n",l.data[0]);/*输出最后一个数据*/ } intmain() { intk,n=0,m=0; seqlistl; initlist(l); printf("请输入总人数n: \n"); scanf("%d",&n); while(n>30||n==0)/*设定输入条件*/ { printf("错误\n"); printf("请重新输入总人数n: \n"); scanf("%d",&n); } printf("请输入出列数: \n"); scanf("%d",&m); printf("请输入起始位置: \n"); scanf("%d",&k); createlist(l,n); yusefu(l,n,m,k); getchar(); getchar(); return0; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 约瑟夫 问题