约瑟夫环实验报告(2)

数据结构上级实验用顺序表解决约瑟夫环问题

说明：

实验课程类别：课程内实验 实验课程性质：必修

适用专业、年级：2010级计算机工程、计算机网络 开课院、系：计算机科学与工程学院计算机工程教研室 学时：18

编写依据：《算法与数据结构》实验教学大纲 修订时间：2012年2月

《算法与数据结构》课程实验指导书（以下简称：指导书）是针对计算机学院所开设的对应课程的上机实验而编写的教学文件，供学生上机实验时使用。

上机的工作环境要求：Windows 2000或以上操作系统、VC++ 6.0或者其它高级程序设计语言。

学生应按指导教师的要求独立完成实验，并按要求撰写实验报告。

每一个实验，编程上机调试并且提交电子文档实验报告，以学号姓名作为文件名上传。报告内容至少包含如下内容：

1、 学生基本情况：专业班级、学号、姓名 2、 实验题目、实验内容 3、 设计分析 4、 源程序代码

5、 测试用例（尽量覆盖所有分支） 6、 实验总结

一．实验内容与学时分配

数据结构上级实验用顺序表解决约瑟夫环问题

一、试验课题

顺序表的应用

二、试验内容

约瑟夫环问题：设编号为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个人为止。