约瑟夫环问题实验报告书.doc

算法与程序设计
实验报告

实验课程: 约瑟夫环问题
专业: 计算机与科学技术
班级:
学号:
姓名:
一、课程设计的目的(需求分析)
【实验内容与要求】
问题描述:编号是1,2,…,n(n>0)的n个人按照顺时针方向围坐一圈,每人持有一正整数密码。开始时任选一个正整数作为报数上限值m,从某个人开始按顺时针方向自1开始顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序,并输出结果。
【基本要求】:利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各人的编号。
【实现提示】
由于该问题是由古罗马著名史学家Josephus提出的问题演变而来,所以通常称之为Josephus问题。Josephus问题的解决需要采用循环链表,先构造一个有n个结点的单循环链表,再给出一个报数上限值m(假设m>1),在链表的首结点开始从1计数,计到m时,对应的结点从链表中删除,然后在被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。
本设计采用的是不带头结点的循环链表,其中循环链表中结点的结构如下:
typedef struct
{ int num;
int cipher;
struct node *next;
}linklist;
该问题可由两部分组成,分别由如下两个算法完成:
(1)建立一个由头指针head指示的有n个结点的约瑟夫单循环链表creat。
(2)寻找、输出和删除head所指的单循环链表的第m个结点select。该算法由如下具体步骤组成:
①在head中的第一个结点起循环记数找第m个结点;
②输出该结点的num值,把该结点的cipher(密码)值赋给m;
③删除该结点;
④转去执行①,直到所有结点被删除为止。
二、测试数据
进入程序,显示“ ”输入非0数进入游戏,输入0退出游戏。
进入游戏后显示“输入总人数”,输入大于0的整数;若输入错误,则光标处清空,重新输入。
后提示“输入开始人的序号”;范围是大于零,小于总人数的整数,若输入错误,则光标处清空,重新输入。
后提示“输入间隔数字”,范围是任意正整数;若输入错误,则光标处清空,重新输入。
按回车键,显示结果,并重新询问“ ”。
三、算法思想
首先,设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质,考虑采用循环链表,为了统一对表中任意节点的操作,循环链表不带头结点。循环链表的结点定义为如下结构类型:
typedef struct node
{
int data;
struct node *next;
}LNode;
其次,建立一个不带头结点的循环链表并由头指针p指示。
最后,设计约瑟夫环问题的算法。
1、工作指针first,r,s,p,q初始化
2、输入人数(n)和报数(m)
3、循环n次,用尾插法创建链表
int start=k-1;
LNode *s,*p,*L=0,*t;
if (start==0) start=n;
while (n!=0)
{
s=(L