约瑟夫斯问题求解与停车场停车问题.docx
《约瑟夫斯问题求解与停车场停车问题.docx》由会员分享，可在线阅读，更多相关《约瑟夫斯问题求解与停车场停车问题.docx（37页珍藏版）》请在冰点文库上搜索。
约瑟夫斯问题求解与停车场停车问题
实验一：
约瑟夫斯问题求解
一、问题描述
1、实验题目
约瑟夫斯（Josephus）问题的一种描述是：
编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。
一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。
试设计一个程序，按出列顺序印出各人编号。
2、基本要求
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
3、测试数据
n=7，7个人的密码依次为：
3，1，7，2，4，8，4。
m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。
二、需求分析
1、本程序利用循环链表结构模拟出约瑟夫斯问题中在任意人数每人任意编号情况下，各编号的出列顺序
2、程序运行后显示提示信息，建立输入处理，输入n输入以及每个人的密码；m的初值。
控制输入的n、m及个人密码必为正整数。
3、建立一个输出函数，程序自动输出正确的序列。
三、概要设计
为实现上述功能，用单向循环链表存储结构模拟此过程，因此需要有单向循环链表这一数据结构。
1、定义一个结点类型来储存每个人编号及密码：
typedefintElemType;
typedefstructnode
{
ElemTypemima;
intbianhao;
structnode*next;
}SLNODE;
2、单向循环链表抽象数据类型定义：
ADT{
数据对象：
SLNODE类型
数据关系：
线性关系
基本操作：
SLNODE*initlist（）;//创建空链表
voidcreatefromRear（SLNODE*head,intn）;//尾插法输入循环链表；利用n来控制输入次数
voidDelLinkList（SLNODE*p）;/*删除p指针指向结点的后一个结点*/
voidxunhuan（SLNODE*head）;//循环链表
｝
3、主程序流程及其模块调用关系
1）主函数流程
输入起始m
调用输出函数，输出出列顺序编号
输入n个编号密码
输入编号总数n
2）模块调用关系
主程序模块
单向循环链表单元模块：
实现单向循环链表的抽象数据类型
单向循环链表单元模块
主函数模块
四、详细设计
1、单向循环链表结点类型
typedefintElemType;
typedefstructnode
{
ElemTypemima;
intbianhao;
structnode*next;
}SLNODE;
2、实现每个基本操作的伪码
//创建空链表
SLNODE*initlist（）
{
SLNODE*head;
head=（SLNODE*）malloc（sizeof（SLNODE））;
head->next=NULL;
returnhead;
}
//尾插法输入循环链表；
voidcreatefromRear（SLNODE*head,intn）//注意控制n>0;
{
SLNODE*r,*s;
ElemTypex;
inti=1;//利用i来控制输入次数
r=head;
cout<<"输入第"<cin>>x;
while（x>0&&i<=n）
{
s=（SLNODE*）malloc（sizeof（SLNODE））;
s->mima=x;
s->bianhao=i;
r->next=s;
r=s;/*r永远指向链表的最后一个结点*/
r->next=NULL;
i++;
if（i<=n）//控制输入提示语句出现个数
{
cout<<"输入第"<cin>>x;
}
}
}
//循环链表
voidxunhuan（SLNODE*head）
{
SLNODE*r;
r=head;
while（r->next!
=NULL）
{
r=r->next;
}
r->next=head;
}
//删除函数；
voidDelLinkList（SLNODE*p）/*删除p指针指向结点的后一个结点*/
{SLNODE*q;
if（p->next!
=NULL）
{q=p->next;/*q指向p的后继结点*/
p->next=q->next;/*修改p结点的指针域*/
free（q）;}/*删除并释放结点*/
}
3、主函数伪码
intmain（）
{
cout<<"实验名称：
实验一.约瑟夫斯求解问题"<cout<<"学号：
031120206"<cout<<"姓名：
李希文"<cout<<"程序运行开始，";
time_trawtime;
structtm*timeinfo;
time（&rawtime）;
timeinfo=localtime（&rawtime）;
printf（"Currentlocaltimeanddate:
%s",asctime（timeinfo））;
SLNODE*head=NULL;
head=initlist（）;
intn,m;
do//控制n>0;
{cout<<"输入编号总数n";
cin>>n;}while（n<=0）;
cout<<"输入编号密码"<createfromRear（head,n）;
xunhuan（head）;
do//控制m>0;
{cout<<"输入起始m";
cin>>m;}while（m<=0）;
cout<<"输出出列顺序编号";
shuchu（head,m）;
cout<cout<<"程序运行结束，";
printf（"Currentlocaltimeanddate:
%s",asctime（timeinfo））;
system（"PAUSE"）;
return0;
}
4、输出模块的伪码
//输出出列顺序编号函数；
voidshuchu（SLNODE*head,intm）
{
SLNODE*r=head;
intj=m,i;
while（j>0&&head->next!
=head）//控制不再空链表时操作
{
i=1;//重新计数
while（i{
if（r->next==head）//循环时略过头结点
r=r->next;
r=r->next;
i++;
}
if（r->next==head）//循环时略过头结点
r=r->next;
j=r->next->mima;
cout<next->bianhao<<"";
DelLinkList（r）;//删除第m个结点
}
}
4、函数调用关系图
SLNODE*initlist（）;//创建空链表函数
voidcreatefromRear（SLNODE*head,intn）;//尾插法输入循环链表；利用n来控制输入次数
createfromRear（SLNODE*head,intn）;//尾插法输入循环链表；利用n来控制输入次数
主函数
voidDelLinkList（SLNODE*p）;/*删除p指针指向结点的后一个结点*/
voidxunhuan（SLNODE*head）;//循环链表
voidshuchu（SLNODE*head,intm）//输出出列顺序编号函数；
五、调试分析
实验遇到的问题以及解决的办法
1）调试无问题，运行时出现了如图的问题
经检查：
在链表插入函数中插入了新结点后少了r->next=NULL;这一步，致使存储空间无法使用。
故无法运行。
再添加了该步骤后，以解决。
2）结果显示正确，但其后出现了一大串奇怪字符
经检查：
在输出函数中忘记控制空链表结束循环，致使该程序无止境循环。
加入控制空链表后问题解决。
六、使用说明
程序运行后用户根据提示输入编号总数n、n个编号密码以及起始m，如输入数字不合要求，程序会要求用户重复输出。
程序将自动调用输出函数，输出出列顺序编号。
七、调试结果
n=7，7个人的密码依次为：
3，1，7，2，4，8，4。
m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。
八、实验的收获
在该试验中不仅强化了链表知识，还进一步学习并尝试要运用了循环链表。
书本知识的学习与实际操作是截然不同的，有可能较熟的知识在编写程序时只因为一个符号而不能运行。
编写代码十分考验耐心与细心。
九、附录
源程序清单
#include
#include/*puts,printf*/
#include/*time_t,structtm,time,localtime*/
usingnamespacestd;
//链表的存储结构；
typedefintElemType;
typedefstructnode
{
ElemTypemima;
intbianhao;
structnode*next;
}SLNODE;
SLNODE*initlist（）;//创建空链表
voidcreatefromRear（SLNODE*head,intn）;//尾插法输入循环链表；利用n来控制输入次数
voidDelLinkList（SLNODE*p）;/*删除p指针指向结点的后一个结点*/
voidshuchu（SLNODE*head,intm）;//输出出列顺序编号；
voidxunhuan（SLNODE*head）;//循环链表
//头函数；
intmain（）
{
cout<<"实验名称：
实验一.约瑟夫斯求解问题"<cout<<"学号：
031120206"<cout<<"姓名：
李希文"<cout<<"程序运行开始，";
time_trawtime;
structtm*timeinfo;
time（&rawtime）;
timeinfo=localtime（&rawtime）;
printf（"Currentlocaltimeanddate:
%s",asctime（timeinfo））;
SLNODE*head=NULL;
head=initlist（）;
intn,m;
do//控制n>0;
{cout<<"输入编号总数n";
cin>>n;}while（n<=0）;
cout<<"输入编号密码"<createfromRear（head,n）;
xunhuan（head）;
do//控制m>0;
{cout<<"输入起始m";
cin>>m;}while（m<=0）;
cout<<"输出出列顺序编号";
shuchu（head,m）;
cout<cout<<"程序运行结束，";
printf（"Currentlocaltimeanddate:
%s",asctime（timeinfo））;
system（"PAUSE"）;
return0;
}
//输出出列顺序编号函数；
voidshuchu（SLNODE*head,intm）
{
SLNODE*r=head;
intj=m,i;
while（j>0&&head->next!
=head）//控制不再空链表时操作
{
i=1;//重新计数
while（i{
if（r->next==head）//循环时略过头结点
r=r->next;
r=r->next;
i++;
}
if（r->next==head）//循环时略过头结点
r=r->next;
j=r->next->mima;
cout<next->bianhao<<"";
DelLinkList（r）;//删除第m个结点
}
}
//创建空链表
SLNODE*initlist（）
{
SLNODE*head;
head=（SLNODE*）malloc（sizeof（SLNODE））;
head->next=NULL;
returnhead;
}
//尾插法输入循环链表；
voidcreatefromRear（SLNODE*head,intn）//注意控制n>0;
{
SLNODE*r,*s;
ElemTypex;
inti=1;//利用i来控制输入次数
r=head;
cout<<"输入第"<cin>>x;
while（x>0&&i<=n）
{
s=（SLNODE*）malloc（sizeof（SLNODE））;
s->mima=x;
s->bianhao=i;
r->next=s;
r=s;/*r永远指向链表的最后一个结点*/
r->next=NULL;
i++;
if（i<=n）//控制输入提示语句出现个数
{
cout<<"输入第"<cin>>x;
}
}
}
//循环链表
voidxunhuan（SLNODE*head）
{
SLNODE*r;
r=head;
while（r->next!
=NULL）
{
r=r->next;
}
r->next=head;
}
//删除函数；
voidDelLinkList（SLNODE*p）/*删除p指针指向结点的后一个结点*/
{SLNODE*q;
if（p->next!
=NULL）
{q=p->next;/*q指向p的后继结点*/
p->next=q->next;/*修改p结点的指针域*/
free（q）;}/*删除并释放结点*/
}
实验二、
一、问题描述
1、实验题目
设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端）。
若停车场内已经停满n辆车，那么后来的车只能在门外的便道上等候。
一旦有车开走，则排在便道上的第一辆车即可开入。
当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场。
每辆停放在车场的车在它离开停车场时必须按它停留的时间长短缴纳费用。
试为停车场编制按上述要求进行管理的模拟程序。
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），（‘E’，0，0）。
每一组输入数据包括三个数据项：
汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，‘A’表示到达；‘D’表示离去，‘E’表示输入结束。
其中：
（‘A’，1，5）表示1号牌照车在5这个时刻到达，而（‘D’，1，15）表示1号牌照车在15这个时刻离去。
二、需求分析
1、本程序模拟出车辆在停车场根据到达时间决定停车位置，对空车位动态补充，车辆离去时计算出在停车场停留的时间和应缴纳的费用。
2、输入数据：
程序接受5个命令，分别是：
到达（‘A’,车牌号,时间）；离去（‘D’,车牌号,时间）；停车场（‘P’,0,0）显示停车场的车数；候车场（‘W’,0,0）显示候车场的车数；退出（‘E’,0,0）退出程序。
3、输出数据：
对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。
3、概要设计
为了实现上述功能，应以两个顺序栈来分别表示停车场（A）与临时停放点（B），以链式队列（C）来表示便道。
故此需要顺序栈与链式队列两个抽象数据类型。
1、定义ElemType类型
typedefstructData//每辆车的信息结构体
{
intlicense;//车牌号码
intarrivetime;//到达时间
}ElemType;
2、顺序栈抽象数据类型
ADTSeqStack{
数据对象：
ElemType类型
数据关系：
线性关系
基本操作：
SeqStack*Init_SeqStack（）;//置空栈
boolpush（SeqStack*s,ElemTypex,intn）;//入栈1
boolPop（SeqStack*s,ElemType&x）;//出栈
｝
3、链式队列两个抽象数据类型
ADTLinkQueue{
数据对象：
ElemType类型
数据关系：
线性关系
基本操作：
LinkQueue*Init_LQueen（）;//创建空对；
voidIn_LQueen（LinkQueue*q,ElemType&x）;//入队
boolOut_LQueen（LinkQueue*q,ElemType&x）;//出对
intlength（LinkQueue*q）;//队的长度
｝
程序循环
4、主函数流程
输入命令：
到达（‘A’,车牌号,时间）；离去（‘D’,车牌号,时间）；（‘P’,0,0）显示停车场的车数；候车场（‘W’,0,0）；退出（‘E’,0,0）
结束程序
调用函数显示输出
根据提示输入n
5、模块调用关系
主程序模块
顺序栈单元模块：
实现顺序存储方式实现的栈的抽象数据类型
链式队列单元模块：
实现链式存储的队列的抽象数据类型
顺序栈单元模块
主程序模块
链式队列单元模块
四、详细设计
1、定义ElemType类型
typedefstructData//每辆车的信息结构体
{
intlicense;//车牌号码
intarrivetime;//到达时间
}ElemType;
2、实现顺序栈的每步基本操作
定义顺序栈；
#defineMaxSize1024
typedefstructstack
{
ElemTypedata[MaxSize];/*用一维数组存放自栈底到栈顶的Data类型*/
inttop;/*附设一个位置指针top*/
}SeqStack;
//置空栈
SeqStack*Init_SeqStack（）
{SeqStack*s;
s=（SeqStack*）malloc（sizeof（SeqStack））;
s->top=-1;
returns;
};
//入栈
boolpush（SeqStack*s,ElemTypex,intn）
{
if（s->top==n-1）returnfalse;
else
{
s->top++;
s->data[s->top]=x;
returntrue;
}
}
//出栈
boolPop（SeqStack*s,ElemType&x）
{
if（s->top==-1）returnfalse;
else
{
x=s->data[s->top];
s->top--;
returntrue;
}
}
3、实现链式队列的每步基本操作
//链式队列结点
TypedefstructNode
{ElemTypedata;
structNode*next;
}QNODE;
//创建空对；
LinkQueue*Init_LQueen（）
{
LinkQueue*q;
QNODE*p;
q=（LinkQueue*）malloc（sizeof（LinkQueue））;//申请头尾结点
p=（QNODE*）malloc（sizeof（QNODE））;//申请链队头结点
p->next=NULL;
q->front=q->rear=p;
returnq;
}
//入队
voidIn_LQueen（LinkQueue*q,ElemType&x）
{
QNODE*p;
p=（QNODE*）malloc（sizeof（QNODE））;//申请新结点
p->data=x;
p->next=NULL;
q->rear->next=p;
q->rear=p;
}
//出队
boolOut_LQueen（LinkQueue*q,ElemType&x）
{
QNODE*p;
if（q->front==q->rear）
{
cout<<"队空";
returnfalse;
}
else
{
p=q->front->next;
q->front->next=p->next;
x=p->data;
free（p）;
if（q->front->next==NULL）//只有一个元素时，出栈后队为空
q->front=q->rear;//此时还要修改队尾指针，因为其指向空
returntrue;
}
}
//队长
intlength（LinkQueue*q）
{
QNODE*p=q->front;
intm;
for（m=0;p!
=q->rear;m++）
{
p=p->next;
升级会员 