实验一约瑟夫环问题
- 格式：pdf
- 大小：244.45 KB
- 文档页数：12
实验四 约瑟夫环问题
一、问题描述 设有编号为1，2，…n的n(n＞0)个人围成一个圈．每个人持有个密码m。从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下个人起重新报数，报到m时停止报数，报m的出圈……如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 二、基本要求 (1)建立模型，确定存储结构 (2)对任意n个人，密码为m，实现约瑟夫环问题 (3)出圈的顺序可以依次输出，也可以用一个数组存储 三、实验步骤
1．需求分析
本演示程序用VC++编写,生成一个循环链表，输入人数输入密码，在执行报数输出操作，输出报数序列；
① 输入的形式和输入值的范围：输入的总共报数人数以及报数密码，在所有输入中，输入数据都为正整数。
② 输出的形式：在输出报数顺序是输出报数顺序序号对应报数本身编号。输出完成后输出是否重新进行提示信息。
③ 程序所能达到的功能：任意输入的报数人数people，及出列密码num输出报数出列顺序编号。
④ 测试数据：
A． 输入报数人数：50，初始化循环链表；
B． 输入报数密码：3，输出报数出列序列
2．概要设计
1）为了实现上述程序功能，需要定义循环链表的抽象数据类型：
ADT LinkList { 数据对象：D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
数据关系：R={|ai,ai+1 ∈D}
基本操作：
creatcirlink(int n)
操作结果：建立循环链表并进行初始化
report_num(cirlink &hand,int m,int max)
初始条件：循环链表hand已建立；
操作结果：报数输出相应的元素data；
Game()
初始条件：循环链表hand已建立；
操作结果：输入报数人people数及密码num
Menu()
操作结果：在屏幕上显示操作菜单
}
2）本程序包含4个函数：
① 主函数main()
②显示操作菜单函数menu()
③报数出列函数report_num ()
④ 输入人数和密码函数Game()
3．详细设计
设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node ｛ int data; //编号 Node * next； ｝；
建立一个不带头结点的循环链表并由头指针hand指示。
2) 关于约瑟夫问题的基本操作
建立循环链表
status creatcirlink(int n) { ｛
hand=(struct node*)malloc(LEN);
hand->data=1;
rear=hand;
for(i=2;i<=n;i++)
{
p=(struct node*)malloc(LEN);
p->data=i;
rear->next=p;
rear=p;
}
rear->next=hand;
return(OK);
}
void report_num(cirlink &hand,int m,int max)
{ int j=0,count=1;
p=hand;
do{q=p;
p=p->next;
count++;
if(count%m==0)
{
j++;
printf("\n\t\t\tj=%2d\tno=%2d",j,p->data);
q->next=p->next;
free(p);
p=q->next;
count++;
}
}while(j!=max);
}
void Game()
{
do{
scanf("%d",&people);
scanf("%d",&num);
hand=creatcirlink(people);
report_num(hand,num,people);
} }
int menu()
{
printf("\t\t\t 1.开始报数\n");
printf("\t\t\t 2.退出报数\n");
do{
scanf("%d",&k);
}while(k<1||k>2);
return k;
}
void main()
{
int n;
n=menu();
switch(n)
{
case 1 : Game();break;
case 2 : exit(0);
}
}
4．程序源码
#include #include
#include
#define Null 0
#define LEN sizeof(cirlink)
typedef struct node /*定义结点结构*/
{
int data;
struct node *next;
}cirlink;
cirlink *t;
cirlink *creatcirlink(int n) /*初始化建立单向循环链表*/
{
cirlink *hand,*rear=Null,*p;
int i=0;
hand=(struct node*)malloc(LEN);/*建立循环链表的头结点*/
hand->data=1;
rear=hand; /*尾指针初值为head*/
for(i=2;i<=n;i++)
{
p=(struct node*)malloc(LEN); /*生成新的结点*/
p->data=i; /*新结点的数据域输入数据*/
rear->next=p; /*将新结点插入表尾*/
rear=p; /*将表尾指针rear指向新的表尾*/ }
rear->next=hand; /*将表尾结点的指针域指向链表头结点*/
return(hand);
}
void report_num(cirlink *hand,int m,int max)/*报数输出函数*/
{
cirlink *q,*p;
int j=0,count=1;/*计数器初始化为1*/
p=hand;
printf("\n\t\t\t报数输出顺序为：");
do{q=p;/*p结点给q*/
p=p->next;/*p指针后移指向下一个结点*/
count++;/*计数器加1*/
if(count%m==0)/*当输入的count个结点能被m整除时输出该结点*/
{
j++;/*统计输出结点数*/
printf("\n\t\t\t第%d个\tno=%2d",j,p->data);
q->next=p->next;/*q的后继指向p的后继结点*/
free(p);/*释放结点p*/
p=q->next;/*q的后继结点给p*/
count++; /*计数器自加*/
}
}while(j!=max);/*当输出结点数大于等于结点总数时跳出循环*/ printf("\n");
}
void Game() /*输入数据函数*/
{
char c;
cirlink *hand;
int people=0,num=0;
do{
printf("\n\t\t\t请输入人数：");
scanf("%d",&people);
printf("\n\t\t\t请输入密码：");
scanf("%d",&num);
hand=creatcirlink(people);/*建立有people个结点的单循环链表并初始化*/
report_num(hand,num,people);/*报数输出出列顺序*/
printf("\t\t约瑟夫环问题报数结束是否重新开始？（Y/N）");
cin>>c; /*输入是否重新开始信息*/
if((c=='y')||(c=='n')) /*当输入为小写字母是转化为大写字母*/
c=c-32;
delete(t);/*释放t所指空间*/
}while(c=='Y');
}
int menu() /*菜单显示函数*/
{
int k;
printf("\t\t\t约瑟夫环问题功能模块：\n\n");
printf("\t\t\t 1.开始报数\n");
printf("\t\t\t 2.退出报数\n");
printf("\t\t ****************************\n");
do{
printf("\n\t\t\t请输入你的选择：");
scanf("%d",&k);
}while(k<1||k>2);/*当输入的选择小于1或大于2重新输入*/
return k;
}
void main() /*主函数*/
{
int n;
printf("\t\t 欢迎进入约瑟夫环问题报数系统\n");
printf("\t\t ****************************\n");
n=menu();
switch(n)
{
case 1 : Game();break;
case 2 : exit(0);
}
