当前位置:
文档之家› 约瑟夫环问题 实验报告完整版
约瑟夫环问题 实验报告完整版
{
p=p->next;
}
q=p->next;
p->next=q->next;
p=p->next;
printf("第%3d个出圈的人是:%3d\n",i,q->value);
free(q);
}
scanf("\n");
p->next=NULL;
}
(3)主程序执行
主程序运行,调用函数,程序接受数据后,输出出圈列数。
}
(2)约瑟夫环报数的算法在运行为循环方式,报数者除非本身已经出去,否则继续顺序报数,其报数循环的代码为
void Joseph(NODE *p,int number,int n)
{
int i,j;
NODE *q=NULL;
for(i=1; i<=number; i++)
{
for(j=1; j<n-1; j++)
(2)基本要求
建立模型,确定存储结构。
对任意n个人,密码为m,实现约瑟夫环问题。
出圈的顺序可以依次输出,也可以用一个数组存储。
(3)思考:
采用顺序存储结构如何实现约瑟夫环问题?
如果每个人持有的密码不同,应如何实现约瑟夫环问题?
2.数据结构设计
由于约瑟夫环问题本身具有循环性质,考虑采用循环链表,为了统一对表中任意结点的操作,循环链表不带头结点。将循环链表的结点定义为如下结构类型:
printf("请输入总人数n和密码m:\n");
scanf("%d",&number);
scanf("%d",&n);
NODE *head=NULL;
head=link(number);
Joseph(head,number,n);
system("PAUSE");
return 0;
4.界面设计
程序无需复杂的界面设计,包含输入提示功能和输出提示功能。
由于内容的要求以及问题的方便,用循环链表作为本次实验的抽象数据类型。申请一个结点作为第一个结点,之后调用creat_list函数将后续结点一次插入链接,构造为循环链表。
NODE *link(int number)
{
NODE *head=NULL,*p=NULL,*q=NULL;
int i=1;
head=(struct node*)malloc(sizeof(struct node));
实验课名称:数据结构实验一
实验名称:约瑟夫环问题
班级000
学号000
姓名神刀公子
时间
1.问题描述
约瑟夫环问题
(1)问题描述
设有编号为1,2,…,n的n(n>,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。
教师评分:
教师签字:
5.运行测试与分析
(1)输出提示,如图1.2所示。
(2)根据提示,输入圈内人数n和每个人持有的密码m如图1.3所示。
(3)输出结果如图1.4所示
分析
6.实验收获及思考
通过该实验,我进一步增强了对于链表的理解,也对链表的操作和实现更为熟悉,熟练掌握了如何实现置空表、求表的长度、取结点、定位运算、插入运算、删除运算、建立不带头结点的单链表(头插入法建表)、建立带头结点的单链表(尾插入法建表),输出带头结点的单链表等操作。同时,锻炼了实际操作时的动手能力。
head->value=i;
p=head;
for(i=2; i<=number; i++)
{
q=(struct node*)malloc(sizeof(struct node));
if(q==0)
return 0;
p->next=q;
p=q;
p->value=i;
}
p->next=head;
return head;
struct Node
{
int data;//数据域
Node *next;//next指针指向下一个结点
};
3.算法设计
问题要求建立模型,确定存储结构,之后对任意n个人,密码为m,实现约瑟夫环问题,出圈的顺序可以依次输出,也可以用一个数组存储。
设计流程图如图1.1所示。
图1.1设计流程图
(1)创建循环链表