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

1、邦接7允“学计算机科学与工程学院算法与数据结构试验报告一专业班级试验地点学生学号指导教师学生姓名试验时间试验项目算法与数据结构试验类别基砒性（） 设计性（） 综合性（，） 其它（）试（1）掌握用VC+吐机调试线性表的基本方法；验（2）掌握顺序表的存储结构以及基本运算的实现。目的及要求成绩评定表类 别评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成设计任务30分程序与报告程序代码规范、功能正确 报告详实完整、体现收获70分计算机科学与工程学院备注:评阅教师：日期：年 月 日试验内容一、实验目的和要求1、实验目的：(1)掌握用VC+吐机调试线性表的基本方法；(2)掌握顺序表的存储结构以及基本

2、运算的实现。2、实验内容约瑟夫环问题：设编号为1, 2, 3,，n的n(n>0)个人按顺 时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针 方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的 下一个人开始重新从1报数，报到m时停止并且报m的人出列。如 此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程， 对任意给定的m和n,求出出列编号序列。3、实验要求：用顺序表实现。二、设计分析根据实验要求，采用顺序表来完成本次实验。实验中采用一维数组屁口 ，先将n个人的编号存入到p0pn-1。从编 号为1的人(下标t=0)开始循环报数，数到 m的人(下标t=(t+m-1)%

3、i)pt, 输出并将其从数组中删除(即将后面的元素前移一个位置)，每次报数的起始位 置就是上次报数的出列位置。反复执行直到出列n个人为止。三、源程序代码#include<stdio.h>#include<stdlib.h>#include <iostream.h>#define MaxSize 100typedef struct Listint dataMaxSize;int length;*Sqlist;void InitList(Sqlist &L)L=(Sqlist)malloc(sizeof(Sqlist);L->length=0;vo

4、id CreateList(Sqlist &L)int n;printf("您想输入的人数为：”);scanf("%d",&n);printf("最初的顺序表为：n");for(int i=0;i<n;i+)L->datai=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(

5、i=L->length;i>=1;i-)t=(t+m-1)%i;printf("%d ”,L->datat);for(j=t+1;j<=i-1;j+)L->dataj-1=L->dataj;printf("n");void main()int tt;Sqlist L;InitList( L);CreateList(L);printf(“您想出列的序号为：”)；scanf("%d”,&tt);josephus(L,tt);四、测试用例(尽量覆盖所有分支)1 .当n>m且n%m!=0时，即当n不是 m的倍数时

6、:n=12, m=5时约瑟夫环的实验结果为, 'D:Program FilDevSB'' MyPrajectgjXDebuggj.exer算法与数据结构试验报告9：129 1B 11 12：510 3 9 4 12 coniinue.2 .当n>m且n%m=0时，即当n是m的倍数时:n=15, m=5时约瑟夫环的实验结果为Q 'T:HSDev9BlM您想甄入的人数为二居最初的顺序表为二1 2 3 4 5 6 7 S 9 10 11 12 13 14 1S唇想出列的序节为:5最后的顺序表为:5 10 15 6 12 3 11 4 14 7 9 13 2 7 1Press anv Jsev to continue3 .当n<m且n%m=0时，即当n是 m的约数时:n=4, m