《用顺序表解决约瑟夫环问题》由会员分享，可在线阅读，更多相关《用顺序表解决约瑟夫环问题（9页珍藏版）》请在金锄头文库上搜索。
1、计算机科学与工程学院算法与数据结构试验报告一专业班级试验地点学生学号指导教师学生姓名试验时间试验项目算法与数据结构试验类别基础性（） 设计性（） 综合性（2） 其它（）试 验 目 的 及 要 求（1）掌握用VC+上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。成绩评定表类另S评分标准分值得分合计上机表现积极出勤、遵守纪律主动完成设计任务30分程序与报告程序代码规范、功能正确报告详实完整、体现收获70分计算机科学与工程学院备注:评阅教师：日期：年 月 日试验内容一、实验目的和要求1、实验目的：（1）掌握用VC+上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运
2、算的实现。2、实验内容约瑟夫环问题：设编号为1, 2, 3,n的n（n0）个人按顺 时针方向围坐一圈，m为任意一个正整数。从第一个人开始顺时针 方向自1起顺序报数，报到m时停止并且报m的人出列，再从他的 下一个人开始重新从1报数，报到m时停止并且报m的人出列。如 此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程， 对任意给定的m和n,求出出列编号序列。3、实验要求：用顺序表实现。二、设计分析根据实验要求，采用顺序表来完成本次实验。实验中采用一维数组屁【】，先将n个人的编号存入到p0pn-1。从编 号为1的人（下标t=0）开始循环报数，数到m的人（下标t=（t+m-1）%i）pt， 输
3、出并将其从数组中删除（即将后面的元素前移一个位置），每次报数的起始位 置就是上次报数的出列位置。反复执行直到出列n个人为止。三、源程序代码#include#include#include viostrea m.h#define MaxSize 100 typedef struct Listint dataMaxSize;int length;*Sqlist;void lnitList(Sqlist &L)L=(Sqlist)malloc(sizeof(Sqlist);L-length=0;void CreateList(Sqlist &L)int n;printf(您想输入的人数为:); sc
4、anf(%d,&n);printf(最初的顺序表为:n);for(int i=0;idatai=i+1;printf(%d 丄-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 丄-datat);for(j=t+1;jv=i-1;j+)L-dataj-1=L-dataj; printf(n);void main()int tt;Sqlist L;InitList( L);Creat
5、eList(L);printf（您想出列的序号为:）;scanf（%d，&tt）;josephus（L,tt）;四、测试用例（尽量覆盖所有分支）1.当nm且n%m!=0时，即当n不是 m的倍数时:n=12，m=5时约瑟夫环的实验结果为 D:Program FileiWO.MSDevSB MyPrajectgjXDebuggj exer人表&星扁 的序5的序J 入顺勺列Jw“岀的3 赴刃恿右9S：129 1B 11 12：510 3 9 4 12conilnuv2.当nm且n%m=0时，即当n是m的倍数时:n=15，m=5时约瑟夫环的实验结果为人数为斗最初的顺序表为z1 2 3 4 5 6 ?
6、S 9 10 11 12 3 14 IS 廊想出列的序号为窃 最后和习序E:t；5 10 15 6 12 3 11 4 14 ? 9 13 2 7 1 press anv lev to continue3.当nm且n%m=O时，即当n是m的约数时:n=4, m=12时约瑟夫环的实验结果为4.当n色bugAvuntynexe最初的顺存赛为*1 2 3 4 5 7 8 9 1B 11 12 13 14 1S 16 17 18 19 28 21 22 23 24 2531 ?2 33 24 3S 3& 3739 4& 41 42 43 44 45 4G 47 4S 49 S3 E1 5卜SH 59俪
7、I 84 85 8G 87108 109 110128 129 13014B 149 150您想出列的圧号为最后的顺序表为炸147 4&8 &79 2373 9Q24 52 的 121 6 43 U(4 12B 11 &1 99 141 41 9S 146 関 111 26 1EM 11 &2 &3&4 1&5陌as i凶 70 717273 74 757B 177 788R89 901 9192 93 94 9596 97 981 99诚10110213311111211311411511G117 lie11912012直12212312113213J13413S1361 沖 1301291
8、40141142142111为汐1 142135 42 49 5& 盟 707? 04 91 9811212 20 29 37 45 53 tl &牛 78 P 94 102 110 119 127 125 143 176 87 96 10& 115 124 134 144 3 15 25 3& 47 59 71 81 92 1033462 74 88 100 113 128 139 2 17 32 4S 64 79 93 108 12209 129 14S 13 23 4 7S 97 117 13G Q 31 57 92 1Q4 130 1S0 29 & 72 131 38 123 14? 1& Press y key tn continue五、实验总结
