用顺序表解决约瑟夫环问题.doc

计算机科学与工程学院计算机科学与工程学院算法与数据结构试验报告一专业班级试验地点学生学号指导教师学生姓名试验时间试验项目算法与数据结构试验类别基础性（） 设计性（） 综合性（） 其它（ ）试验目的及要求（1） 掌握用VC+上机调试线性表的基本方法； （2）掌握顺序表的存储结构以及基本运算的实现。成 绩 评 定 表类 别评 分 标 准分值得分合 计上机表现积极出勤、遵守纪律主动完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分备注： 评阅教师： 日 期： 年 月 日试 验 内 容 一、实验目的和要求1、实验目的：（1）掌握用VC+上机调试线性表的基本方法； （2）掌握顺序表的存储结构以及基本运算的实现。2、实验内容约瑟夫环问题：设编号为1，2，3，n的n(n0)个人按顺时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的下一个人开始重新从1报数，报到m时停止并且报m的人出列。如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对任意给定的m和n，求出出列编号序列。3、实验要求：用顺序表实现。2、 设计分析根据实验要求，采用顺序表来完成本次实验。实验中采用一维数组屁【】，先将n个人的编号存入到p0pn-1。从编号为1的人 (下标t=0)开始循环报数，数到m的人(下标t=(t+m-1)%i)pt，输出并将其从数组中删除（即将后面的元素前移一个位置），每次报数的起始位置就是上次报数的出列位置。反复执行直到出列n个人为止。3、 源程序代码#include#include#include #define MaxSize 100typedef struct Listint dataMaxSize;int length;*Sqlist;void InitList(Sqlist &L)L=(Sqlist)malloc(sizeof(Sqlist);L-length=0;void CreateList(Sqlist &L) int n; printf(您想输入的人数为:);scanf(%d,&n);printf(最初的顺序表为:n);for(int i=0;idatai=i+1;printf(%d ,L-datai);L-length=n;printf(n);void josephus(Sqlist &L,int m)int i,j,t;t=0; printf(最后的顺序表为:);for(i=L-length;i=1;i-) t=(t+m-1)%i;printf(%d ,L-datat);for(j=t+1;jdataj-1=L-dataj;printf(n);void main()int tt;Sqlist L;InitList( L);CreateList(L);printf(您想出列的序号为:);scanf(%d,&tt);josephus(L,tt);四、测试用例（尽量覆盖所有分支） 1.当nm且n%m!=0时，即当n不是m的倍数时：n=12，m=5时约瑟夫环的实验结果为2.当nm且n%m=0时，即当n是m的倍数时：n=15，m=5时约瑟夫环的实验结果为3. 当nm且n%m=0时，即当n是m的约数时：n=4，m=12时约瑟夫环的实验结果为4.当nm且n%m!=0时，即当n不是