正文要求：对每一个题目，正文必须包括以下几个方面 知识点回顾： 实验要求：
实验过程：包括设计思路，算法描述，程序清单，调试等等； 实验小结：
注意：（1）正文中字体用小四号宋体，行间距1.25倍行距；
（2）页码居中；
（3）A4纸双面打印，在纸的左侧装订。
（4）上交的课程设计报告控制在10页以内。
2
齐鲁工业大学
理学院
信计11-1
郑桥
一、提示：对于单窗口的服务系统知识点回顾如下：
1、什么是负指数分布？
又称指数分布。泊松事件流的等待时间（相继两次出现之间的间隔）服从指数分布。用于描述非老化性元件的寿命（元件不老化，仅由于突然故障而毁坏）。常假定排队系统中服务器的服务时间和Petri网中变迁的实施速率符合指数分布。
2、用C语言如何产生随机序列？ double rd_MN1(double m,double n) { double r; if (m>n) {r=n;n=m;m=r;}; r = ((double)rand()/ ((double)(RAND_MAX)+(double)(1)) ); r = m+ r*(n-m); return r; }
3、用C语言如何产生负指数分布的时间序列？ double expntl(double x) { double z; 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仿真。
3 在排队系统中的每一个动态实体的状态可以有三个量来反映：与前一个实体到达的时间间隔，在排到自己服务前的等待时间以及服务时间。其中服务时间和到达时间间隔服从指数分布，不受别的因素的影响。开始服务前的等待时间则受到排在前面的动态实体的状态的影响。其更新算法如下：
即：如果某个实体到达以后，发现处在它前面的动态实体已经结束服务，所以这个实体就不用等待，直接接受服务；反之，处在它前面的动态实体如果没有结束服务（包括没有开始服务），则这个实体的等待时间就是它前一实体结束服务的时刻减去它到达的时刻。
5、如何得到每个顾客的到达时刻，服务时间，等待时间和离开时刻； 到达时间=前面各个到达时间之和； 服务时间就是负指数随机生成的时间；
等待时刻：如果前一个人的离开时间小于这个人的到达时间，等待时间=0；
如果不是，则等待时间=该人的离开时间-他的到达时间-服务时间
6、如何排队，排队的主要算法思想？ 排队就是来到的人数多于离开的人数；
如果下一个人到达时前一个人依旧在接受服务，则此人就要排队。
7、如何求队长？以及最大的队长？
假设以5分钟为一个时间段，则在第5分钟时用这5分钟内来到的人数减去这5分钟内离开的人数即是排队人数
8、如何求平均等待时间？
求平均等待时间首先要求出总的等待时间与接受服务的人数；
总的等待时间=每个人的等待时间之和；接受服务的人数由时间540分钟来控制，如果在540分钟之后才到达的人则不再算入接受服务的人数之内。
9、用C语言如何将得到的数据输出到文件？
在C语言中用fopen函数打开文件，然后把数据输出比如用fprintf函数，最后fclose。
利用ofstream fcout(“d:\\arr_time.txt”);语句来实现C++中的输出文件
10、如何用已学的数学语言程序（如：Mathematica, Matlab）把C语言得到的数据文件画出其相应的图像？
11、如果是两个窗口的服务系统，则该怎么修改程序？
12、如果到达时间间隔，服务时间服从泊松分布或者其他分布，该程序该如何改进？
二、数据结构课程设计题目
单窗口的排队模型的数值仿真（参考课本上第四章的离散事件模拟） 要求如下：
4 （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软件。）
五、总结
（1）求出各个时刻的队长（以五分钟为一时间单位，即求零时刻的队长，五分钟时的队长，十分钟时的队长，依次类推）；见程序清单中数据部分对长。 （2）求平均等待时间（顾客总等待时间除以总人数）；根据程序可得，平均等待时间为21.6分钟。
（3）画出顾客的到达，离开图像（横坐标是顾客图，纵坐标是到达时刻，和离开时刻）；
180160140120100806040200 0Arrive curveleave curve100200300400500600
（6）画出队长变换图像（横坐标是时刻图，纵坐标是队长个数）；
25Queue Length Curve 20151050 0100200300400500600
（7）求出一个工作日内的最大队长： 最大对长为16个人在排队。
六、程序清单：
求随机产生负指数 #include #include #include #include #include
#include using namespace std;
void main() { long int i,k; double m,n;//m,n控制时间间隔
double r; double a,s,sum;//arr为到达时间，ser为服务时间
double LAM=1.2;
//f(x)=LAM*exp(-LAM*x); double arr_time[200]; double ser_time[200]; ofstream fcout(\"d:\\arr_time.txt\"); ofstream fscout(\"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
arr_time[k]=a;
k++; }; if (k
// 产生200个指数分布随机数
for(i=0;i
fcout
//cout
if(i!=0 && i%5==0)
//cout
fcout
7 k=0; loop1: r=((double)rand()/((double)(RAND_MAX)+(double)(1)) );
s =-log(r)/LAM; if (s >= m && s
// 产生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
// 产生200个指数分布随机数
for(i=0;i
fscout
//cout
if(i!=0 && i%5==0)
//cout
fscout #include #include #include #include
#include using namespace std; void main() { //下面求离开时间、等待时间
8 int i; double lea_time[200];//离开时间
double sta_time[200];//等待时间
double arr_time[200];//随机生成到达时间
double ser_time[200];//随机生成服务时间
double arr_time1[200];//到达时间
ifstream fcin(\"d:\\arr_time.txt\"); ifstream fscin(\"d:\\ser_time.txt\"); ofstream fcout(\"d:\\arr_time1.txt\"); ofstream flcout(\"d:\\lea_time.txt\"); ofstream fscout(\"d:\\sta_time.txt\");
//求到达的时间
for(i=0;i
fcin>>arr_time[i];
arr_time1[i]=arr_time[i]; } double sum=0.0; for(i=0;i
sum+=arr_time1[i];
arr_time1[i]=sum; } for(i=0;i
fcout
if(i!=0 && i%5==0)
fcout
//求离开时间
fscin>>ser_time[0]; lea_time[0]=arr_time1[0]+ser_time[0]; for(i=1;i
fscin>>ser_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;i
flcout
if(i!=0 && i%5==0)
flcout
sta_time[i]=lea_time[i]-arr_time1[i]-ser_time[i];//
if(sta_time[i]
{
sta_time[i]=0;
} } for(i=0;i
fscout
if(i!=0 && i%5==0)
fscout
sta_sum+=sta_time[i]; }
//求平均等待时间
double ave; int peo_sum; for(i=0;i
if(lea_time[i]
peo_sum=i; } cout
求离开人数和到达人数 #include #include #include #include #include
#include using namespace std; void main() { //求离开人数和到达人数
int i,j;
int arr_num[200];//到达人数arr int lea_num[200];//lea离开人数
int arr_jian=0;//时间间隔
double arr_time1[200]; double lea_time[200]; int peo_sum; int count=0; int count1=0; ifstream fcin(\"d:\\arr_time1.txt\"); ifstream flcin(\"d:\\lea_time.txt\"); ofstream fcout(\"d:\\arr_num.txt\"); ofstream flcout(\"d:\\lea_num.txt\"); for(i=0;i
fcin>>arr_time1[i];
flcin>>lea_time[i]; } for(i=0;i
if(lea_time[i]
peo_sum=i; } while(arr_jian
for(i=0;i { if(arr_time1[i]>arr_jian) { arr_num[count]=i; count++; //cout break; } } for(j=0;j { if(lea_time[j]>arr_jian) { lea_num[count1]=j; count1++; break; } } arr_jian=arr_jian+5; } for(i=0;i fcout //cout if(i!=0 && i%5==0) //cout fcout for(i=0;i flcout //cout if(i!=0 && i%5==0) //cout flcout 求对长 #include #include using namespace std; int main() { int i; int max; int que[200]; int arr_num[200]; int lea_num[200]; ifstream fcin(\"d:\\arr_num.txt\"); ifstream flcin(\"d:\\lea_num.txt\"); ofstream fcout(\"d:\\que.txt\"); for(i=0;i fcin>>arr_num[i]; //cout flcin>>lea_num[i]; //cout for(i=0;i que[i]=arr_num[i]-lea_num[i]; //cout } for(i=0;i fcout if(i!=0 && i%5==0) { fcout } } max=que[0]; for(i=1;i { if(que[i]>max) { max=que[i]; //cout } } cout 画图: function[maxque,mwait_t,mstay_t,queue_l,use_rate]=MM1queue(mean_arr,mean_lea,peo_num) status=zeros(3,peo_num); %用一个3行矩阵表示每个顾客的状态; %到达时间间隔，服务时间，等待时间; status(1,:)=exprnd(mean_arr,1,peo_num); %按照指数分布随机生成各顾客的到达间隔; status(2,:)=exprnd(mean_lea,1,peo_num); %按照指数分布随机生成各顾客的服务时间; for i=2:peo_num if status(1,i) status(3,i)=status(2,i-1)+status(3,i-1)-status(1,i); else status(3,i)=0; end; %对状态进行更新； end; arr_time=cumsum(status(1,:)); status(1,:)=arr_time; lea_time=sum(status); stairs([0 arr_time],0:peo_num); %绘出各顾客的到达时间图; hold on; stairs([0 lea_time],0:peo_num,\'r\'); %绘出各顾客的离去时间图; legend(\'Arrive curve\',\'leave curve\',0) hold off figure; plot(1:peo_num,status(3,:),\'r:\',1:peo_num,status(2,:)+status(3,:),\'k-\'); %绘出每个顾客的等待时间和停留时间; legend(\'Wait Time\',\'Stay Time\',0); n1=1; n2=1; mstay_t=(sum(status(2,:))+sum(status(3,:)))/peo_num; mwait_t=mean(status(3,:)); %求平均停留时间和等待时间; queue_num=zeros(1,2*peo_num+1); queue_time=zeros(1,2*peo_num+1); 14 n3=1; %while循环求每个时间队列的长度; while n1 n3=n3+1; if arr_time(n1) queue_num(1,n3)=n1-n2+1; queue_time(1,n3)=arr_time(n1); n1=n1+1; else queue_num(1,n3)=n1-n2-1; queue_time(1,n3)=lea_time(n2); n2=n2+1; end; end; while n2 n3=n3+1; queue_num(1,n3)=peo_num-n2; queue_time(1,n3)=lea_time(n2); n2=n2+1; end; figure; stairs(queue_time,queue_num,\'k\'); %绘出队列长度的时间变化曲线, stairs 是Matlab的函数 legend(\'Queue Length Curve\',0); hold off; temp=diff(queue_time); overtime=max(queue_time); queue_l=sum(temp.*queue_num(2:(2*peo_num+1)))/overtime; use_rate=sum(temp(find(queue_num)))/overtime; maxque=max(queue_num); % 最大队长 在MATLAB中命令窗口中输入MM1queue(2.86,3.22,175) 数据结果： 随机到达时间arr_time 2.2218 2.91038 2.70151 3.20392 2.20729 2.23954 2.27037 2.12161 2.97105 2.59537 2.05195 2.33276 2.40885 2.54536 3.18395 4.34619 2.9621 4.03687 2.56005 4.3556 2.59767 2.6854 2.2156 2.35007 2.01546 3.16558 2.51725 2.4227 3.00499 2.68796 2.57445 2.29238 2.04275 3.56593 4.12181 3.14539 4.60806 2.85305 2.18215 4.15836 2.75386 2.45691 3.15095 3.84449 3.29556 2.35349 2.88082 2.96656 2.60517 3.09175 3.77562 2.12649 2.17347 2.28761 2.91709 2.59767 2.20084 3.64077 2.09167 2.30401 2.89137 2.78563 2.35564 2.60401 3.47721 2.31212 2.2892 2.26189 2.71001 3.23541 3.15543 4.04989 2.33905 2.60575 2.93069 2.63466 2.33025 2.67211 2.13304 2.46765 2.01119 2.66026 2.17867 4.26591 2.56115 2.84451 3.37485 2.22326 2.3109 3.08451 2.75872 15 3.02393 2.32155 2.37607 2.43489 3.70764 3.07631 2.56943 2.81941 2.81567 2.18215 3.78511 2.72393 2.02062 2.28013 2.03219 2.9324 4.02088 2.83606 2.01804 2.82241 2.23062 2.38448 2.15369 4.07996 2.02407 2.77847 2.93584 4.92381 4.07996 2.52143 2.10523 3.29291 2.34922 2.60807 2.83989 3.77091 2.4652 2.12096 2.36601 4.23257 2.29039 2.03278 3.42756 3.04233 2.80972 4.46149 2.04867 3.6673 2.04363 3.56409 4.8267 4.40435 3.60347 2.01375 4.41955 2.28406 2.49971 2.85853 2.11547 2.29079 2.2037 3.0078 2.43726 2.43963 3.82172 2.26189 3.14207 3.02297 2.39612 2.26381 3.59773 2.454 4.98197 3.60539 3.04233 3.21228 2.48553 2.16591 2.17244 2.25882 2.11773 3.77326 2.1113 3.15319 2.4011 2.66648 3.58261 3.36182 2.74012 2.16046 2.53464 2.21742 2.48754 2.86484 2.45837 2.4213 2.81047 4.02405 2.08667 2.24179 2.17971 3.1465 2.96925 2.07709 2.6139 3.48217 4.50565 3.25667 2.71528 随机服务时间ser_time 1.36266 1.25234 1.19953 1.81288 1.7025 1.49777 1.18475 1.2005 2.2218 2.91038 1.69353 1.06181 1.95277 1.86629 1.35603 1.36501 1.98628 1.05845 1.48635 2.70151 1.56285 1.7392 1.00964 1.69024 1.23548 1.68311 3.20392 2.20729 2.23954 1.0431 1.986 1.09644 2.27037 1.53367 2.12161 2.97105 1.68177 2.59537 2.05195 1.54594 1.24156 1.42946 2.33276 1.06994 2.40885 1.9069 2.54536 3.18395 4.34619 2.9621 1.09313 4.03687 2.56005 1.01332 1.97996 1.76143 1.26501 1.34689 1.66416 4.3556 1.6471 1.46631 2.59767 2.6854 1.92952 1.51985 1.85138 1.04044 2.2156 1.30726 1.1663 1.16661 5.21173 2.35007 1.3357 1.00973 2.01546 3.16558 2.51725 1.27905 2.4227 1.04284 1.69508 1.63761 1.13783 1.05052 1.94433 1.53127 3.00499 2.68796 2.57445 2.29238 1.40015 1.2112 1.64527 2.04275 1.29598 1.29286 3.56593 1.07538 3.20392 3.18395 4.34619 4.03687 4.3556 5.21173 3.16558 3.00499 3.56593 4.12181 3.14539 4.60806 4.15836 3.15095 3.84449 3.29556 5.29513 3.09175 3.77562 3.64077 3.47721 3.23541 3.15543 4.04989 4.26591 3.37485 3.08451 3.02393 3.70764 3.07631 3.78511 4.02088 4.07996 4.92381 4.07996 3.29291 3.77091 4.23257 3.42756 3.04233 4.46149 3.6673 3.56409 4.8267 4.40435 3.60347 4.41955 3.0078 3.82172 3.14207 3.02297 3.59773 4.98197 3.60539 3.04233 3.21228 3.77326 3.15319 3.58261 3.36182 5.0445 4.02405 3.1465 3.48217 4.50565 3.25667 4.85208 4.16211 4.13261 3.21952 3.46087 3.74548 4.5463 3.72969 3.29423 3.0804 3.08657 3.47556 4.09022 3.17586 5.29513 3.75694 3.74548 3.30222 3.01725 3.18627 3.40305 4.12539 3.49556 3.02777 3.87053 3.39703 3.51433 3.67983 3.27072 4.11115 4.22444 4.08337 3.37339 5.03375 到达时刻：arr_time1 2.2218 5.13218 7.83369 11.0376 13.2449 15.4844 17.7548 19.8764 22.8475 25.4428 27.4948 29.8276 32.2364 34.7818 37.9657 42.3119 45.274 49.3109 51.8709 56.2265 58.8242 61.5096 63.7252 66.0753 68.0907 71.2563 73.7736 76.1963 79.2012 81.8892 84.4637 86.756 88.7988 92.3647 96.4865 99.6319 104.24 107.093 109.275 113.434 116.187 118.644 121.795 125.64 128.935 131.289 134.17 137.136 139.741 142.833 146.609 148.735 150.909 153.196 16 156.113 158.711 160.912 164.553 166.644 168.948 171.84 174.625 176.981 179.585 183.062 185.374 187.664 189.925 192.635 195.871 199.026 203.076 205.415 208.021 210.952 213.586 215.917 218.589 220.722 223.189 225.201 227.861 230.039 234.305 236.867 239.711 243.086 245.309 247.62 250.705 253.463 256.487 258.809 261.185 263.62 267.327 270.404 272.973 275.793 278.608 280.79 284.575 287.299 289.32 291.6 293.632 296.565 300.586 303.422 305.44 308.262 310.493 312.877 315.031 319.111 321.135 323.913 326.849 331.773 335.853 338.374 340.48 343.773 346.122 348.73 351.57 355.341 357.806 359.927 362.293 366.525 368.816 370.849 374.276 377.318 380.128 384.59 386.638 390.306 392.349 395.913 400.74 405.144 408.748 410.762 415.181 417.465 419.965 422.823 424.939 427.23 429.433 432.441 434.878 437.318 441.14 443.402 446.544 449.567 451.963 454.227 457.824 460.278 465.26 468.866 471.908 475.12 477.606 479.772 481.944 484.203 486.321 490.094 492.205 495.359 497.76 500.426 504.009 507.371 510.111 512.271 514.806 517.023 519.511 522.376 524.834 527.255 530.066 534.09 536.176 538.418 540.598 543.744 546.714 548.791 551.405 554.887 559.393 562.649 565.364 离开时刻：lea_time 3.58446 6.38452 9.03322 12.8505 14.9474 16.9822 18.9396 21.0769 25.0693 28.3532 30.0467 31.1086 34.1892 36.6481 39.3217 43.6769 47.2603 50.3693 53.3573 58.928 60.4909 63.2488 64.7348 67.7655 69.3262 72.9394 76.9775 79.1848 81.4408 82.9323 86.4497 87.8525 91.0692 93.8984 98.6081 102.603 105.922 109.688 111.74 114.979 117.429 120.074 124.128 126.71 131.344 133.251 136.715 140.32 144.666 147.628 148.722 152.772 155.332 156.345 158.325 160.472 162.177 165.9 168.308 173.304 174.951 176.417 179.579 182.27 184.992 186.894 189.515 190.966 194.851 197.178 200.193 204.243 210.627 212.977 214.313 215.322 217.932 221.754 224.271 225.551 227.973 229.016 231.735 235.943 238.004 240.762 245.03 246.84 250.625 253.393 256.038 258.78 260.209 262.396 265.265 269.37 271.7 274.266 279.358 280.434 283.994 287.759 292.106 296.142 300.498 305.71 308.875 311.88 315.446 319.568 322.713 327.322 331.48 334.631 338.475 341.771 347.066 350.158 353.933 357.574 361.051 364.287 367.442 371.492 375.758 379.133 382.217 385.241 388.949 392.025 395.81 399.831 403.911 408.835 412.915 416.208 419.979 424.211 427.639 430.681 435.143 438.81 442.374 447.201 451.605 455.209 459.628 462.636 466.458 469.6 472.623 476.22 481.202 484.808 487.85 491.062 494.836 497.989 501.572 504.933 509.978 514.002 517.148 520.631 525.136 528.393 533.245 537.407 541.54 544.759 548.22 551.966 556.512 560.242 563.536 566.616 569.703 573.178 577.269 580.444 585.74 589.496 593.242 596.544 599.561 602.748 606.151 610.276 613.772 616.799 620.67 624.067 627.581 631.261 634.532 638.643 642.867 646.951 650.324 655.358 到达人数：peo_num 0 1 3 5 8 9 12 14 15 16 18 19 21 23 25 27 29 31 33 34 36 37 39 40 42 43 45 47 49 50 52 54 56 58 60 62 64 65 68 69 71 72 74 76 78 80 82 84 86 87 89 91 93 95 96 98 100 102 104 106 107 109 111 113 115 117 118 119 121 123 125 126 129 130 132 134 17 135 137 138 140 141 142 144 145 148 150 152 154 155 157 159 161 162 163 165 166 167 169 170 171 173174 175 177 离开人数：lea_num 0 1 3 5 7 8 10 13 15 16 17 19 20 23 25 26 28 30 32 34 35 36 38 40 41 43 44 46 47 49 51 52 55 57 59 61 63 65 67 69 70 72 72 75 77 79 82 83 85 86 88 90 92 94 96 98 99 101 102 103 104 105 107 108 110 111 112 114 115 116 117 119 120 122 123 124 126 127 129 130 132 133 134 135 137 138 139 140 142 143 144 145 147 148 150 151 152 154 155 157 158 160 161 162 队长que 0 0 0 0 1 1 2 1 0 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 0 1 1 2 1 1 2 1 1 1 1 1 0 1 0 1 0 2 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 2 3 3 4 4 5 5 6 6 5 6 7 8 7 9 8 9 10 0 10 9 10 9 9 10 10 11 12 13 14 13 14 15 16 15 15 15 15 0 0 0 0 0 0 0 0 70 605040302010Wait TimeStay Time204060801001201401601800 0
