您好,欢迎访问三七文档
当前位置:首页 > 机械/制造/汽车 > 汽车理论 > 数据结构课程设计报告
2正文要求:对每一个题目,正文必须包括以下几个方面知识点回顾:实验要求:实验过程:包括设计思路,算法描述,程序清单,调试等等;实验小结:注意:(1)正文中字体用小四号宋体,行间距1.25倍行距;(2)页码居中;(3)A4纸双面打印,在纸的左侧装订。(4)上交的课程设计报告控制在10页以内。齐鲁工业大学理学院信计11-1郑桥3一、提示:对于单窗口的服务系统知识点回顾如下:1、什么是负指数分布?又称指数分布。泊松事件流的等待时间(相继两次出现之间的间隔)服从指数分布。用于描述非老化性元件的寿命(元件不老化,仅由于突然故障而毁坏)。常假定排队系统中服务器的服务时间和Petri网中变迁的实施速率符合指数分布。2、用C语言如何产生随机序列?doublerd_MN1(doublem,doublen){doubler;if(mn){r=n;n=m;m=r;};r=((double)rand()/((double)(RAND_MAX)+(double)(1)));r=m+r*(n-m);returnr;}3、用C语言如何产生负指数分布的时间序列?doubleexpntl(doublex){doublez;do{z=((double)rand()/RAND_MAX);}while((z==0)||(z==1));return(-x*log(z));//z相当于1-x,而x相当于1/lamda。}其中的x相当于1/λ4、排队论简单叙述;排队系统主要有:X/Y/Z,其中X表示到达时间间隔的分布,Y表示服务时间的分布,Z表示并列的服务设备的数目。表示相继到达的时间间隔或服务时间的分布的符号是:M——负指数分布,D——确定性,Ek——k阶Erlang,GI——相互独立的一般随机分布,G——一般的随机分布。例如:M/M/1表示达到时间间隔为负指数分布,服务时间为负指数分布,单服务设备的排队系统。这里我们用静态仿真的思想来实现M/M/1仿真。4在排队系统中的每一个动态实体的状态可以有三个量来反映:与前一个实体到达的时间间隔,在排到自己服务前的等待时间以及服务时间。其中服务时间和到达时间间隔服从指数分布,不受别的因素的影响。开始服务前的等待时间则受到排在前面的动态实体的状态的影响。其更新算法如下:即:如果某个实体到达以后,发现处在它前面的动态实体已经结束服务,所以这个实体就不用等待,直接接受服务;反之,处在它前面的动态实体如果没有结束服务(包括没有开始服务),则这个实体的等待时间就是它前一实体结束服务的时刻减去它到达的时刻。5、如何得到每个顾客的到达时刻,服务时间,等待时间和离开时刻;到达时间=前面各个到达时间之和;服务时间就是负指数随机生成的时间;等待时刻:如果前一个人的离开时间小于这个人的到达时间,等待时间=0;如果不是,则等待时间=该人的离开时间-他的到达时间-服务时间6、如何排队,排队的主要算法思想?排队就是来到的人数多于离开的人数;如果下一个人到达时前一个人依旧在接受服务,则此人就要排队。7、如何求队长?以及最大的队长?假设以5分钟为一个时间段,则在第5分钟时用这5分钟内来到的人数减去这5分钟内离开的人数即是排队人数8、如何求平均等待时间?求平均等待时间首先要求出总的等待时间与接受服务的人数;总的等待时间=每个人的等待时间之和;接受服务的人数由时间540分钟来控制,如果在540分钟之后才到达的人则不再算入接受服务的人数之内。9、用C语言如何将得到的数据输出到文件?在C语言中用fopen函数打开文件,然后把数据输出比如用fprintf函数,最后fclose。利用ofstreamfcout(“d:\\arr_time.txt”);语句来实现C++中的输出文件10、如何用已学的数学语言程序(如:Mathematica,Matlab)把C语言得到的数据文件画出其相应的图像?11、如果是两个窗口的服务系统,则该怎么修改程序?12、如果到达时间间隔,服务时间服从泊松分布或者其他分布,该程序该如何改进?二、数据结构课程设计题目单窗口的排队模型的数值仿真(参考课本上第四章的离散事件模拟)要求如下:5(1)要求相邻两个顾客的到达时间间隔服从负指数分布;且每个顾客接受服务的时间也服从负指数分布;(2)求出各个时刻的队长(以五分钟为一时间单位,即求零时刻的队长,五分钟时的队长,十分钟时的队长,依次类推);(3)一个工作日内的顾客总数,约定8:30上班,17:30下班,中午不休息;(4)求平均等待时间(顾客总等待时间除以总人数);(5)画出顾客的到达,离开图像(横坐标是顾客图,纵坐标是到达时刻,和离开时刻);(6)画出队长变换图像(横坐标是时刻图,纵坐标是队长个数);(7)求出一个工作日内的最大队长;三、设计思路:1)把8::30记做第0分钟,17:30记做第540分钟。2)首先利用C++随机生成200个服从负指数分布的到达时间与200个服务时间然后根据随机生成的数计算到达的时刻,即到达时间的逐步加和,然后计算离开的时刻;3)根据到达时刻与离开时刻来计算等待时刻,于是便可得到平均等待时间;同时根据这两个时刻求出每5分钟到达人数与离开的人数,于是便得出每5分钟的队长,同时也可求出最大队长。4)再利用MATLAB画出相应的图像。四、算法描述:1)首先将8:30这个时刻化为0时刻,17:30化为第540分钟这个时刻,全体单位为分钟。2)定义到达时间间隔arr_time[200],服务时间ser_time[200],到达时刻arr_time1[200],离开时间lea_time[200],等待时间sta_time[200],离开人数lea_num[200],到达人数arr_num[200]等变量。3)根据负指数函数来利用C++程序生成随机到达时间间隔与服务时间。4)利用到达时刻与离开时刻之间的关系来求出等待时间。同时将这540分钟划分为5分钟间隔的108个时间段来求出在每个时间段到达人数与离开人数,再求出队长。5)利用已知的服务人数,平均到达时间与平均离开时间来做出图像。(借助MATLAB软件。)6五、总结(1)求出各个时刻的队长(以五分钟为一时间单位,即求零时刻的队长,五分钟时的队长,十分钟时的队长,依次类推);见程序清单中数据部分对长。(2)求平均等待时间(顾客总等待时间除以总人数);根据程序可得,平均等待时间为21.6分钟。(3)画出顾客的到达,离开图像(横坐标是顾客图,纵坐标是到达时刻,和离开时刻);0100200300400500600020406080100120140160180Arrivecurveleavecurve(6)画出队长变换图像(横坐标是时刻图,纵坐标是队长个数);01002003004005006000510152025QueueLengthCurve(7)求出一个工作日内的最大队长:最大对长为16个人在排队。7六、程序清单:求随机产生负指数#includestdio.h#includeiostream#includestdlib.h#includetime.h#includemath.h#includefstreamusingnamespacestd;voidmain(){longinti,k;doublem,n;//m,n控制时间间隔doubler;doublea,s,sum;//arr为到达时间,ser为服务时间doubleLAM=1.2;//f(x)=LAM*exp(-LAM*x);doublearr_time[200];doubleser_time[200];ofstreamfcout(d:\\arr_time.txt);ofstreamfscout(d:\\ser_time.txt);m=2.0;n=5.0;srand((unsigned)time(NULL));k=0;loop:r=((double)rand()/((double)(RAND_MAX)+(double)(1)));a=-log(r)/LAM;if(a=m&&a=n){arr_time[k]=a;k++;};if(k200)gotoloop;//产生200个指数分布随机数for(i=0;i200;i++){fcoutarr_time[i];//coutl[i];if(i!=0&&i%5==0)//coutendl;fcoutendl;}m=1.0;n=5.5;srand((unsigned)time(NULL));8k=0;loop1:r=((double)rand()/((double)(RAND_MAX)+(double)(1)));s=-log(r)/LAM;if(s=m&&s=n){ser_time[k]=s;k++;};if(k100)gotoloop1;//产生200个指数分布随机数m=3.0;n=5.5;srand((unsigned)time(NULL));k=100;loop2:r=((double)rand()/((double)(RAND_MAX)+(double)(1)));s=-log(r)/LAM;if(s=m&&s=n){ser_time[k]=s;k++;};if(k200)gotoloop2;//产生200个指数分布随机数for(i=0;i200;i++){fscoutser_time[i];//coutl[i];if(i!=0&&i%5==0)//coutendl;fscoutendl;}}求等待时间和平均等待时间#includestdio.h#includeiostream#includestdlib.h#includetime.h#includemath.h#includefstreamusingnamespacestd;voidmain(){//下面求离开时间、等待时间9inti;doublelea_time[200];//离开时间doublesta_time[200];//等待时间doublearr_time[200];//随机生成到达时间doubleser_time[200];//随机生成服务时间doublearr_time1[200];//到达时间ifstreamfcin(d:\\arr_time.txt);ifstreamfscin(d:\\ser_time.txt);ofstreamfcout(d:\\arr_time1.txt);ofstreamflcout(d:\\lea_time.txt);ofstreamfscout(d:\\sta_time.txt);//求到达的时间for(i=0;i200;i++){fcinarr_time[i];arr_time1[i]=arr_time[i];}doublesum=0.0;for(i=0;i200;i++){sum+=arr_time1[i];arr_time1[i]=sum;}for(i=0;i200;i++){fcoutarr_time1[i];if(i!=0&&i%5==0)fcoutendl;}//求离开时间fscinser_time[0];lea_time[0]=arr_time1[0]+ser_time[0];for(i=1;i200;i++){fscinser_time[i];if(lea_time[i-1]arr_time1[i]){lea_time[i]=lea_time[i-1]+ser_time[i];}else{lea_time[i]=arr_time1[i]+ser_time[i];}}for(i=0;i200;i++){10flcoutlea_time[i];if(i!=0&&i%5==0)flcoutendl;}//等待时间stasta_time[0]=0;for(i=1;i200;i++){sta_time[i]=lea_time[i]-arr_time1
本文标题:数据结构课程设计报告
链接地址:https://www.777doc.com/doc-3421184 .html