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

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

评阅教师:
日期: 年月日
试验内容

一、实验目的和要求
1、实验目的:
(1)掌握用VC++上机调试线性表的基本方法;
(2)掌握顺序表的存储结构以及基本运算的实现。
2、实验内容
约瑟夫环问题:设编号为1,2,3,……,n的n(n>0)个人按顺时针方向围坐一圈,m为任意一个正整数。从第一个人开始顺时针方向自1起顺序报数,报到m时停止并且报m的人出列,再从他的下一个人开始重新从1报数,报到m时停止并且报m的人出列。如此下去,直到所有人全部出列为止。要求设计一个程序模拟此过程,对任意给定的m和n,求出出列编号序列。
3、实验要求:用顺序表实现。
设计分析
根据实验要求,采用顺序表来完成本次实验。
实验中采用一维数组屁【】,先将n个人的编号存入到p[0]p[n-1]。从编号为1的人(下标t=0)开始循环报数,数到m的人(下标t=(t+m-1)%i)p[t],输出并将其从数组中删除(即将后面的元素前移一个位置),每次报数的起始位置就是上次报数的出列位置。反复执行直到出列n个人为止。
源程序代码
#include<>
#include<>
#include <>
#define MaxSize 100
typedef struct List
{
int data[MaxSize];
int length;
}*Sqlist;
void InitList(Sqlist &L)
{
L=(Sqlist)malloc(sizeof(Sqlist));
L->length=0;
}
void CreateList(Sqlist &L)
{
int n;
printf("您想输入的人数为:");
scanf("%d",&n);
printf("最初的顺序表为:\n");
for(int i=0;i<n;i++)
{
L->data[i]=i+1;
printf("%d ",L->data[i]);
L->length=n;
}
printf("\n");
}
void josephus(Sqlist &L,int m)
{
int i,j,t;
t=0;
printf("最后的顺序