阮籍技术基础课设.docx

实验一：约瑟夫斯问题实验报告
一、 问题描述
约瑟夫斯（Josephus）问题的一种描述是：编号为 1，2，…，n 的 n 个人按顺时针方向 围坐一圈，每人持有一个密码（正整数） 。一开始任选一个正整数作为报数上限值 m，从第 一个人开始按顺时针方向自 1 开始报数，报到 m 时停止报数。报 m 的人出列，将他的密码作 为新的 m 值，从他在顺时针方向下一个人开始重新从 1 报数，如此下去，直至所有的人全部 出列为止。试设计一个程序，按出列顺序印出各人编号。 2）基本要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 3）测试数据 m 的初值为 20；n=7，7 个人的密码依次为：3，1，7，2，4，8，4。m 初值为 6（正确的 出列顺序应为 6，1，4，7，2，3，5） 。
二、 需求分析
1．该程序所能实现的功能：将 n 个数字按照某一特定序列输出，直至全部输出为止。
2．输入的形式及输入值范围 ：依次输入人数 n、每个人的密码及报数上限 m 值。
3．输出的形式：按照报数上限 m 及每个人的密码依次输出每个人的编号。
4．测试数据要求：m 的初值为 20；n=7，7 个人的密码依次为：3，1，7，2，4，8，4。 m 初值为 6（正确的出列顺序应为 6，1，4，7，2，3，5） 。
三、 概要设计
1. 主程序流程 获取每个人的密码，选定 m 的初值，调用函数，按照特定要求完成输出操作。
2.核心模块的算法伪码 主程序：
void main(void)
{ int m; people *s;
s=GetData();
cout<<"请输入 m 的初值："<>m; DealData(s,m); }
预编译代码：#include
四、 详细设计
1.实现每个操作的伪码，重点语句加注释
(1)建立“人”的结构体 struct people { int data; int num; people *next; };
(2)获取每个人的相关数据
people *GetData()
{ int n; people *p1,*p2,*head; head=NULL;
cout<<"请输入人数：";
cin>>n;
cout<<"请依次输入每个人的密码："<>p1->data;
p1->num=i+1;
if(head==NULL)
{ head=p2=p1; }
else { p2->next=p1;
p2=p1; //中间结点 //建立首结点 } }
if(head!=NULL) p2->next=head; return(head); }
2.函数调用关系图 //循环链表
Main()
void DealData(people *s,int m)
people *GetData()
五、调试分析
1. 设计与调试过程中遇到的问题分析、体会. 在调试过程中遇到了死循环的情况， 自己反复看了很久也未能查找到错误， 直到请同学 帮忙看，才终于发现原来是一个在循环条件中，写丢了一个条件。后来回想，觉得当初自己 检查的时候不够仔细， 大概也有些主观思想——认为不可能出错——掺杂其中， 导致有此结 果。以后写程序要更认真才行。
2. 主要算法的时间 主程序：循环算法。
六、使用说明 打开此程序，点击运行，按照屏幕输出显示依次输入所需数据即可—— 首先输入参与的人数；然后依次输入每个人手中的密码；最后输入 m 的初值，即可得到 输出结果。
七、测试结果
八、附录 源程序
#include
struct people { int data; int num; people *next; };
people *GetData() { int n; people *p1,*p2,*head;
head=NULL;
cout<<"请输入人数："; cin>>n;
cout<<"请依次输入每个人的密码："<>p1->data;
p1->num=i+1;
if(head==NULL) { head=p2=p1; }
else { p2->next=p1; p2=p1; } }
if(head!=NULL) p2->next=head;
return(head); } //循环链表 //中间结点 //建立首结点
void DealData(people *s,int m)
{ people *p1,*p2,*q; p1=s;
while(p1!=NULL)
{ for(int i=1;inext; }
if(p1!=p1->next) //重新获取 m 值并删除 已读取的结点
{ m=p1->data;
cout<num;
p2->next=p1->next;
q=p1; p1=p1->next;
delete q; }
else
{ cout<num;
delete p1;
p1=NULL; } } }
void main(void)
{ int m;
people *s;
s=GetData();
cout<<"请输入 m 的初值："<>m;
DealData(s,m);
cout<车开出大门外， 其他车辆再按原次序进入车场。 每辆停放在车场的车在它离开停车场时必须按它停留的 时间长短缴纳费用。试为停车场编制按上述要求进行管理的模拟程序。 2） 基本要求 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模 拟管理。 每一组输入数据包括三个数据项： 汽车的 “到达” （ ‘A’ 表示） “离去” 或 （ ‘D’ 表示）信息、汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操 作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置； 若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上停留的时间 不收费） 。栈以顺序结构实现，队列以链表结构实现。 3） 测试数据 设 n=2,输入数据为：‘A’ （ ，1，5）（ ，‘A’ ，2，10）（ ，‘D’ ，1，15）（ ，‘A’ ，3， 20） ， （ ‘A’ ，4，25）（ ，‘A’ ，5，30）（ ，‘D’ ，2，35）（ ，‘D’ ，4，40）（ ，0，0） ，‘E’ 。每一 组输入数据包括三个数据项：汽车 “到达”或“离去”信息、汽车牌照号码及到达或 离去的时刻，其中， ‘A’表示到达； ‘D’表示离去， ‘E’表示输入结束。其中：‘A’ （ ， 1，5）表示 1 号牌照车在 5 这个时刻到达，而（ ‘D’ ，1，15）表示 1 号牌照车在 15 这 个时刻离去。 二、需求分析 需求分析 1．程序所能达到的基本可能 可实现特定停车场车辆出入的管理功能，可以查询等车场、候车场使用情况。 2．输入的形式及输入值的范围 功能指令分为 5 种，分别是： A— 到达； D—离开； P—查询停车场使用情况； W—查询候车场使用情况； E—退出程序。 车牌号、到达时间、费用及停车场容量可为任意正整数； 3．输出的形式 依据所选功能指令不同，输出形式略有不同。 对于 A 指令，输出车牌号，车位号； D 指令，输出车牌号，计费时间段，应付费用； P 指令，输出停车场内车辆数目； W 指令，输出后车场内车辆数目； E 指令，输出退出提示。 4．测试数据要求 需另设一个栈， 临时停放为给要离去的汽车让路而从停车场退出来的汽车。 输入数 据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌 照号码和进入停车场的时刻。: 输入数据：程序接受 5 个命令，分别是：到达（‘A’,车牌号,时间)；离去(‘D’,车牌号, 时间)；停车场（‘P’, 0, 0）显示停车场的车数；候车场（‘W’, 0, 0）显示候车场的车数； 退出（‘E’, 0, 0）退出程序。 输出数据：对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车 辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费） 。 三、 概要设计 1． 主程序流程 首先设定停车场容量及停车场收费标准；选择功能指令，输入车牌号，到达时间； 根据指令调用不同的函数，完成指令功能。 2． 核心模块的算法伪码 //主程序 void { cout<<"请设定停车场的最大容量（大于零的整数）:"; cin>>Parkingroom; cout<<"请设置停车场收费标准(大于零的数字，单位：y/h):"; cin>>fee; cout<<"-----------------------------------------------"<n' <<"P-停车场使用情况"<<'\n' <<"W-候车便道情况"<<'\n' <<"E-退出程序"<能指令："; cin>>order; cin>>x.num; cin>>x.intime; switch(order) { case'A':parkingin(s1,p,x); break; case'D':parkingout(s1,s2,p,x); break; case'P':roomsituation(); break; case'W':roompave(); break; case'E':k=0;cout<<"程序即将退出!"<} 预编译代码：#include #include 四、 详细设计 1．实现每个操作的伪码，重点语句加注释 //车辆信息 struct car { int num; int intime; }; //停车场信息 struct parking { car N[10000]; int top; int size; }; //便道上车辆信息 struct pavecar { pavecar *next; int pavenum; int posnum; }; //便车道信息 struct pave { pavecar *front; pavecar *rear; }; //初始化栈——停车场 void Init_parking(parking* s) { s->top=-1; } //初始化队列——便道 void Init_pave(pave *s) { s->front=new (pavecar); s->rear=s->front; s->front->next=NULL; s->front->posnum=0; } //便道上车辆进入 void pavein(pave *s,int num) { pavecar *p; p=new (pavecar); p->pavenum=num; p->posnum=s->rear->posnum+1 p->next=NULL; if(s->rear==s->front) { s->front->next=p; } s->rear->next=p; s->rear=p; ::carwait=::carwait+1; } //便道上车辆离开 int paveout(pave *s) { pavecar *p; int num; p=s->front->next; s->front->next=p->next; if(p->next==NULL) { s->rear=s->front; } num=p->pavenum; delete p; return num; ::carwait =::carwait -1; } //车辆进入停车场 int carin(parking *s,car x) { if(s->top==Parkingroom-1) { cout<<"停车场已满!"<top++; s->N[s->top]=x; ::carroom=::carroom+1; return (1); } } void parkingin(parking *s,pave *p,car x) { int k; k=carin(s,x); if(k==0) { cout<<"----------------------------"<<'\n' <<"停车场已满，请到便道上排队等候。"<top<<'\n' <<"-----------"<top<0) { p.num=NULL; p.intime=NULL; return (p); } else { s->top--; ::carroom=::carroom-1; return (s->N[s->top+1]); } } void parkingout(parking *s1,parking *s2,pave *p,car x) { car y; int num,k=0; while((s1->top>-1)&&(k==0)) { y=carout(s1); if(y.num!=x.num) { k=carin(s2,y); } else k=1; } if(y.num==x.num) { cout<<"------------------------------------------"<<'\n' <<"车辆离开停车场。"<<'\n' <<"车牌号："<"<top>=0) { y=carout(s2); carin(s1,y); } num=paveout(p); if(num!=0) { y.num=num; y.intime=x.intime; carin(s1,y); cout<<"便道上等候车辆进入停车场。"<<'\n' <<"车牌号："<top+1<<'\n' <<"------------------------------------------"<e { while(s2->top>-1) { y=carout(s2); k=carin(s1,y); } cout<<"所查车辆不在停车场中"<ave() { cout<<"-------------------------------------------------"<<'\n' <<"停车场内已有车辆数:"<<::carwait<<"台。"<<'\n' <<"-------------------------------------------------"<编译却总是有问题出现，而且很多，更麻烦的是，看不明白程序 纠错里给出的提示，这一度让我有些头痛，于是只能一遍又一遍地看程序。偶然间，想 到，我编写的程序里面全部用的“->”这个符号，却没深究那些到底是不是指针类型的 结构体， 于是， 又重新修改， 弄了一个晚上才终于把这个程序调好。 看到小黑屏跳出来， 心里真的很开心呀！吸取教训，以后写程序不能“想当然” ，要严格按照既定的规则按 部就班地书写，否则吃亏的，真的是自己！ 2．主要算法的时间和空间复杂度 六、使用说明 运行程序，输入功能指令+车牌号+车辆到达时间即可。 七、测试结果 源代码） 八、附录 （源代码）
#includeream.h>
#include
int Parkingroom;
int fee;
int carroom=0;
int carwait=0;
//车辆信息
struct car { int num; int intime; };
//停车场信息
struct parking { car N[10000]; int top; int size; };
//便道上车辆信息
struct pavecar { pavecar *next; int pavenum; int posnum; };
//便车道信息
struct pave { pavecar *front; pavecar *rear; };
//初始化栈--停车场
void Init_parking(parking* s) { s->top=-1; }
//初始化队列--便道
void Init_pave(pave *s)
{ s->front=new (pavecar); s->rear=s->front; s->front->next=NULL; s->front->posnum=0; }
//便道上车辆进入
void pavein(pave *s,int num) { pavecar *p; p=new (pavecar);
p->pavenum=num;
p->posnum=s->rear->posnum+1;
p->next=NULL;
if(s->rear==s->front) { s->front->next=p; } s->rear->next=p; s->rear=p; ::carwait=::carwait+1; }
//便道上车辆离开
int paveout(pave *s) { pavecar *p; int num; p=s->front->next;
s->front->next=p->next;
if(p->next==NULL) { s->rear=s->front; } num=p->pavenum;
delete p; return num; ::carwait =::carwait -1; }
//车辆进入停车场
int carin(parking *s,car x)
{ if(s->top==Parkingroom-1)
{ cout<<"停车场已满!"<top++; s->N[s->top]=x; ::carroom=::carroom+1; return (1); } }
void parkingin(parking *s,pave *pcar x)
{ int k; k=carin(s,x); if(k==0)
{ cout<<"------------------------------------------"<<'\n' <<"停车场已满，请到便道上排队等候。"<\n' <<"车辆已停入停车场。"<<'\n' <<"车牌号："<top<<'\n' <<"------------------------------------------"<top<0) { p.num=NULL; p.intime=NULL; return (p); }
else { s->top--; ::carroom=::carroom-1; return (s->N[s->top+1]); } }
void parkingout(parking *s1,parking *s2,pave *p,car x)
{car y; int num,k=0; while((s1->top>-1)&&(k==0))
{y=carout(s1);
if(y.num!=x.num)
{ k=carin(s2,y); } else k=1; }
f(y.num==x.num) ;
{ cout<<"------------------------------------------"<<'\n' <<"车辆离开停车场。"<<'\n' <<"车牌号："<"计费时间段："<top>=0) { y=carout(s2); carin(s1,y); }
num=paveout(p);
if(num!=0) { y.num=num; y.intime=x.intime; carin(s1,y);
cout<<"便道上等候车辆进入停车场。"<<'\n' <<"车牌号："<top+1<<'\n' <<"------------------------------------------"<top>-1) { y=carout(s2); k=carin(s1,y); } cout<<"所查车辆不在停车场中"<场内已有车辆数:"<<::carroom<<"台。"<<'\n' <<"-------------------------------------------------"<序
void { cout<<"请设定停车场的最大容量（大于零的整数）:"; cin>>Parkingroom; cout<<"请设置停车场收费标准(大于零的数字，单位：y/h):";
cin>>fee; cout<<"-----------------------------------------------"<"<>order; cin>>x.num; cin>>x.intime; switch(order) { case'A':parkingin(s1,p,x);
break;
case'D':parkingout(s1,s2,p,x);
break; case'P':
roomsituation();
break;
case'W':roompave();
break;
case'E':k=0;
cout<<"程序即将退出!"<