约瑟夫环实习报告
- 格式:docx
- 大小:36.04 KB
- 文档页数:5
约瑟夫环
实习报告
题目:编制一个程序求出约瑟夫环问题的出列顺序。
班级:06计算机A班姓名:林树地学号:0615111044 完成日期:2008-05-01
顺序表实现
一、需求分析
1. 本程序需要由用户在键盘上输入程序中的相关数据。
2. 先输入初始密码m (m>0)和环中人的个数n(n<50),再依次输入每个人的密码。输
入形式是以“回车”为结束标志的整型数。
3. 依次输出约瑟夫环中的出列者的编号。
4. 测试数据:
初值m=20,n=7,7个人的密码依次为:3,1,7,2,4,8,4。
出列顺序应为6,1,4,7,2,3,5。
二、概要设计
以顺序表表示环中的人:
1.顺序表数据类型定义为:
ADT sqlist{
数据对象:D={ a i|a i∈Elemtype,i=1,2,……n;n≥0}
数据关系:R1={| a i-1,a i∈D,i=2,……,n}
基本操作:
initlist_sq(&l)
操作结果:构造一个空的顺序表
}ADT sqlist
2.本程序包含两个模块
①主程序模块
void main(){
接受命令;
处理命令;
}
②顺序表单元模块——实现顺序表抽象数据类型;
各模式块之间的调用关系如下;
主程序模块→顺序表单元模块
三、详细设计
1.顺序表类型
typedef struct{
int elem[50];//存密码
int length;
}sqlist;
2.主函数和其他函数的伪码算法
void main()
{
int m,n;//m为密码,n为小孩个数
cout<<"请输入初始密码m和人数n(n不大于50):";
while(n<1||n>50)
{
cin>>m>>n;
if(n<1||n>50) cout<<"人数不合法,请重输"< } sqlist Jos; initlist_sq(Jos);// 初始化线性表 cout<<"请依次输入"< for(;Jos.length cin>>Jos.elem[Jos.length];//存密码 cout<<"出列顺序为:"; int i=-1;//i为数组下标(下一值为0) for(int k=0;k { for(int j=0;j { i=(i+1)%n;//对下标加1求模 if(Jos.elem[i]!=0)//判断是否已出列 j++; } cout< m=Jos.elem[i];//输出已出列的编号 Jos.elem[i]=0;//标识已出列 } cout< } void initlist_sq(sqlist &l){ l.length=0; } 3.函数调用关系: main InitList 四、调试分析 1.刚开始忽略了对输入数据合法性的判断,可能造成存储空间不足。 2.算法时空分析 主函数中,时间复杂度为O(n*m)。 五、测试结果 循环链表实现 一、需求分析 1. 本程序需要由用户在键盘上输入程序中的相关数据。 2. 先输入初始密码m (m>0)和环中人的个数n (n>0),再依次输入每个人的密码。输入 形式是以“回车”为结束标志的整型数。 3. 依次输出约瑟夫环中的出列者的编号。 4. 测试数据: 初值m=20,n=7,7个人的密码依次为:3,1,7,2,4,8,4。 出列顺序应为6,1,4,7,2,3,5。 二、概要设计 以循环链表存储结构表示环中的人。 1.本程序包含两个模块 ①主程序模块 void main(){ 初始化; 接受命令; ②顺序表单元模块——实现循环链表抽象数据类型; 各模式块之间的调用关系如下; 主程序模块→循环链表单元模块 三、详细设计 1.元素类型、节点类型和指针类型 typedef struct Lnode int data; int secret; struct Lnode* next; }*p,*q,*t,h,*head,*linklist;//p为当前指针,head为头指针,q为跟随指针,h 为头节点 2. 主函数的算法 void main() { cout<<"请输入人数n,报数上限值m和这n个人的密码:"< int m,n,i; string s;vector getline(cin,s); istringstream sin(s); for(int b;sin>>b;a.push_back(b)); cout<<"您输入这n个人的密码是:";