约瑟夫斯问题求解.docx

实验一：约瑟夫斯问题求解
一、问题描述
1．实验题目：约瑟夫斯问题的一种描述是：编号为1，2，……n的n个人按顺时针方向围坐一圈，每人持有一个密码9(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始按照顺时针方向自1开始报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。
2．基本要求：利用单向循环链表模拟此过程，按照出列的顺序印出各人编号。
3．测试数据：n=7,7个人的密码依次为3，1，7，2，4，8，4.m的初始值为6（正确的出列顺序应为6，1，4，7，2，3，5。
二、需求分析
1．程序所能达到的基本可能：本程序能够按出列顺序印出各人编号，程序运行后显示提示信息，提示用户输入人数n,初始报数值m，n个人的密码，程序需自动考虑重复的，用户输入完毕后，程序自动输出运算结果。
2．输入的形式及输入值范围：输入人数n,初始报数值m，n个人的密码，所有值均为正整数int型。
3．输出的形式：输出的是按出列顺序印出各人编号，为正整数int型。
4．测试数据要求：测试数据要求为int型
三、概要设计
1.所用到得数据结构及其ADT
为了实现上述功能，应以单向循环链表有序链表表示集合
数据类型。
1.单向循环链表抽象数据类型定义：
typedefstructnode
{
ElemTypedata;
ElemTypenum;
structnode*next;
}SLNODE;
基本操作：
structnode*create_sl(intn);//创建单向循环链表
主程序流程及其模块调用关系
1）创建循环链表的流程图

约瑟夫问题求解流程图

主函数流程图

四、详细设计
1.实现每个操作的伪码，重点语句加注释
主程序：
voidmain()
{
SLNODE*head;
intn,m;
head=(SLNODE*)malloc(sizeof(SLNODE));
printf("/*************************************/\n");//初始界面
printf("学号：031350102\n");
printf("姓名：王亚文\n");
printf("约瑟夫斯问题求解\n");
printf("/*************************************/\n");
printf("输入总人数n=\n");
scanf("%d",&n);
printf("输入初始报数值m=\n");
scanf("%d",&m);
head=create_sl(n);
Josephus(head,n,m);
}
2.创建循环单链表
structnode*create_sl(intn)
{
SLNODE*p,*s,*head;
ElemTypex;
inta;
head=(SLNODE*)malloc(sizeof(SLNODE));
p=head;
head->next=head;
for(a=1;a<=n;a++)//循环直到输入n个密码值跳出循环
{
s=(SLNODE*)malloc(sizeof(SLNODE));
printf("请输入第%d个人的密码值\n",a);
scanf("%d",&x);
s->data=x;
s->num=a;
if(head->next==head)head=s;
elsep->next=s;
p=s;
}
p->next=head;
returnhead;
}
3.约瑟夫斯问题求解：
voidJosephus(SLNODE*head,intn,intm)
{
SLNODE*p,*q;
inti;
p=head;
printf("出列序列:");
while(p->next!=p)
{
for(i=1;i<m;i++)//报数报的m时跳出循环
{
q=p;
p=p->next;
}
m=p->data;//读取新的密码值
printf("%4d",p->num);
q->next=p->next;//删除p节点
free(p);
p=q->next;
}
printf("%4d\n",p->num);
}
4.函数调用关系图
主函数中调用了structnode*create_sl(intn);
voidJosephus(SLNODE*head,intn,intm);两个函数

五、调试分析
1.设计与调试过程中遇到的问题分析、体会
1）创建单链表时，一开始写的程序是voidcreate_sl(SLNODE*head,intn),并没有没有报错，但最后运行时却不是想象的结果，然后尝试在主函数中写一个printf函数看一下