约瑟夫环实验报告.doc

约瑟夫环实验报告xx大学xx学院算法与数据结构试验报告设计名称:算法与数据结构设计题目:顺序表的应用学生学号:xx专业班级:xx学生姓名:xx学生成绩:指导教师(职称):xx课题工作时间:2012年3月29日说明:实验课程类别:课程内实验实验课程性质:必修适用专业、年级:2010级计算机工程、计算机网络开课院、系:计算机科学与工程学院计算机工程教研室学时:18编写依据:《算法与数据结构》实验教学大纲修订时间:2012年2月《算法与数据结构》课程实验指导书(以下简称:指导书)是针对计算机学院所开设的对应课程的上机实验而编写的教学文件,供学生上机实验时使用。上机的工作环境要求:Windows2000或以上操作系统、VC++。学生应按指导教师的要求独立完成实验,并按要求撰写实验报告。每一个实验,编程上机调试并且提交电子文档实验报告,以学号姓名作为文件名上传。报告内容至少包含如下内容:1、学生基本情况:专业班级、学号、姓名2、实验题目、实验内容3、设计分析4、源程序代码5、测试用例(尽量覆盖所有分支)6、实验总结一(实验内容与学时分配序实验实验学基本技能训练次题目类型时(1)掌握线性结构的常用操作;线性结构综合应用综合性10一(2)能够应用线性结构解决比较简单的问题。(1)掌握树形、图形结构的插入、删除、查找等算法;非线性结构综合应综合性4二用(2)能够应用二叉树解决比较简单的问题。(1)熟练掌握查找的常用算法;查找技术综合应用综合性2三(2)熟练设计和应用查找算法解决简单的实际问题。(1)熟练掌握常用的排序方法,并掌握用高级语言实现排序算法的方法;(2)深刻理解排序的定义和各种排序方法的特点,并综合性2排序技术综合应用四能加以灵活应用;(3)了解各种方法的排序过程及其依据的原则,并掌握各种排序方法的时间复杂度的分析方法。一、试验课题顺序表的应用二、试验内容约瑟夫环问题:设编号为1,2,3,……,n的n(n>0)个人按顺时针方向围坐一圈,m为任意一个正整数。从第一个人开始顺时针方向自1起顺序报数,报到m时停止并且报m的人出列,再从他的下一个人开始重新从1报数,报到m时停止并且报m的人出列。如此下去,直到所有人全部出列为止。要求设计一个程序模拟此过程,对任意给定的m和n,求出出列编号序列。三、试验分析先设一个一维数组p[n],分别把数值1,2,3…赋值给p[0],p[1],p[2]…一开始时,是从编号为1(即下标为t=0)的人开始循环报数,数到m,第一次数到编号为m的人时,让p[m-1]出列,即输出p[m-1],并让p[m]以后的所有数组里面的数往前挪动一个,总人数i减1;如果从p[t-1]往后数m个数,这时可能会循环到开头,所以这时数到的人的编号则为(t+m)%i,对应的数组的下标为t=(t+m-1)%i;这样就可以按照之前的算法,依次输出,直到出列n个人为止。下标编号0**********……………………n-1n四、源程序代码#include<>#include""#defineMaxSize100voidjosephus(intn,intm);voidmain(){intn,m;printf("请输入人数n(不超过100人):");for(;;){fflush(stdin);/*清空输入缓冲区