《用顺序表解决约瑟夫环问题》由会员分享，可在线阅读，更多相关《用顺序表解决约瑟夫环问题（9页珍藏版）》请在装配图网上搜索。
1、 用顺序表解决约瑟夫环问题 计算机科学与工程学院 算法与数据结构试验报告一 专业班级 试验地点 学生学号 指导教师 学生姓名 试验时间 试验项目 算法与数据结构 试验类别 基础性（）设计性（）综合性（）其它（）试验目的及要求（1）掌握用 VC+上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。成 绩 评 定 表 类 别 评 分 标 准 分值 得分 合 计 上机表现 积极出勤、遵守纪律 主动完成设计任务 30 分 程序与报告 程序代码规范、功能正确 报告详实完整、体现收获 70 分 备注：评阅教师：日 期：年 月 日 试 验 内 容 一、实验目的和要求 1、实验目的：（1）
2、掌握用 VC+上机调试线性表的基本方法；（2）掌握顺序表的存储结构以及基本运算的实现。2、实验内容 约瑟夫环问题：设编号为 1，2，3，n 的 n(n0)个人按顺时针方向围坐一圈，m 为任意一个正整数。从第一个人开始顺时针方向自 1 起顺序报数，报到 m 时停止并且报 m 的人出列，再从他的下一个人开始重新从 1 报数，报到 m 时停止并且报 m 的人出列。如此下去，直到所有人全部出列为止。要求设计一个程序模拟此过程，对任意给定的 m 和 n，求出出列编号序列。3、实验要求：用顺序表实现。二、设计分析 根据实验要求，采用顺序表来完成本次实验。实验中采用一维数组屁【】，先将 n 个人的编号存入到
3、 p0pn-1。从编号为 1 的人(下标 t=0)开始循环报数，数到 m 的人(下标 t=(t+m-1)%i)pt，输出并将其从数组中删除（即将后面的元素前移一个位置），每次报数的起始位置就是上次报数的出列位置。反复执行直到出列 n 个人为止。三、源程序代码#include#include#include#define MaxSize 100 typedef struct List int dataMaxSize;int length;*Sqlist;void InitList(Sqlist&L)L=(Sqlist)malloc(sizeof(Sqlist);L-length=0;void C
4、reateList(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()in
5、t 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 不是 m 的约数时：n=3，m=7 时约瑟夫环的实验结果为 5当 n 或 m 任一个足够大时 n=150，m=7 时约瑟夫环的实验结果为 五、实验总结
用顺序表解决约瑟夫环问题
