【正确答案】(1)分析
在模拟中，我们希望所实现的行为过程与真实事物的情况尽可能相似。因此，就需要决定一些问题。比如，这个店要多大，需要多少座位等。假设通过调查，我们已经得到了一些有关顾客来店频率的数据。例如，顾客以群为单位到达冰淇淋店，一群顾客的人数从一人到五人不等，二人一组或三人一组的最多，一人一组和多于三人的相对少一些。再假定顾客群以1～10分钟的间隔光临冰淇淋店，模拟过程中可以在这个范围里取一个随机值。另一方面，顾客到达后可能坐下来点食品，或者因为找不到座位而离去。如果坐下，他们将用2～10分钟点冰淇淋，随后将会在店里用餐15～35分钟。我们还知道，每个顾客将点1～3份冰淇淋，商店在每份冰淇淋上赚2.5元，等等。
如何做出正确的选择呢?一种办法就是做一次模拟。在实现这种技术的程序里，优先队列常常被用做存储需要模拟的事件的基本数据结构。通常需要把事件按照其发生的先后顺序存入优先队列。由于优先队列的性质，其中最小元素将总是下一个要发生的事件。一个事件的发生又可能衍生出一些其他事件，这些事件也加入到优先队列中去。这样处理下去，直到所有事件都已发生，或是超过了预定的模拟时间，模拟过程结束。
(2)实现
1)数据结构
顾客到达、顾客点食品、顾客离开等事件用Event结构体表示，它的成员包括事件类型(以上3种事件中的哪一种)、发生时间、此事件的顾客人数。
typeclef struct {
int type;
int time;
int customers;
}Event;
冰淇淋店也用Store结构体来表示,它的成员包括利润数和剩余的座位数。
typedef struct {
float profits;
int freeChairs;
}Store;
用下面的堆(HeapPriorityQueue)来存储按发生时间为序的事件。
typedef Event DataType;
typedef struct{
DataType element{MAXNUM];
int n; /*n＜=MAXNUM,为优先队列中元素的个数*/
}HeapPriorityQueue;
typedef HeapPriorityQueue* PHeapPrio rityQueue;
2)算法
首先随机地构造一系列顾客到达事件，并把这些事件插入到堆里，然后启动run实现模拟过程。为了确定较合适的座位数，需要调整座位数，并对其进行多次模拟，最后确定使利润比较高同时资源(座位)利用率也比较高的方案。
main(){
int time,i,j,count[30];
float pro[30];
Event ae;
int customersize;
Store store;
HeapPriorityQueue eventHeap;
eventHeap.n=0;
for(i=0;i＜30;i++){COunt[i]=0;pro[i]=0;}
for(j=0;j＜30;j++){ /*模拟30次*/
store.freeChairs=j+35:
for(i=0;i＜40. i++){
limited=0;
store.profits=0;
for(time=0;time＜480;time+=randombetween(2,5)){
/*建立模拟初试数据*/
customersize=randombetween(1,5);
ae.type=1:
ae.time=time;
ae.customers=customersize;
add Heap(&eventHeap,ae);
}
run(&store.&eventHeap); /*执行模拟*/
pro[j]+=store.profits;
if(limited)count[j]+=limited;
}
}
for(j=0;j＜30;j++){ /*输出结果*/
pro[j]==pro[j]/40;
printf("\n sits:/%d profits:/%f',j+35,pro[j]);
printf("limited:/%d".count[j]);
}
}
其中,randombetween是用下面的函数生成需要的随机数:
int randombetween(int low,int high){
randomize();
return low+random(high-10w+1);
}
run的功能是依次从堆中取出发生时间最小的事件，该时间发生时又产生其他事件(顾客到达后会点食品，点食品后过一段时间顾客吃完了就会离开)，把它产生的事件加入到堆中。最后直到堆为空。
void run(Store*store,HeapPriorityQueue*eventHeap){
Event nextEvent;
while(!isEmpty_Heap(eventHeap)){
nextEvent.type=min_Heap(eventHeap).type;
nextEvent.time=min_Heap(eventHeap).time;
nextEvent.customers=min_Heap(eventHeap).customers;
removeMin_Heap(eventHeap);
processEvent(store,nextEvent,eventHeap);
}
}
其中,processEvent(store,nextEvent,evemHe印)完成对于优先队列中事件的处理:
void processEVent(Store*store,Event nextEvent,HeapPriorityQueue
*eventHeap){
Event oe;
int orderSize,i;
if(nextEvent.type==1){ /*处理arrive*/
printf("\n customer group of size/%d arrive at time/%d",nextEvent.customers.nextEvent.time);
if(nextEvent.custonlers＜store-＞freeChairs){
store-＞freeChairs-=nextEvent.customers;
oe.time=nextEvent.time+randombetween(2,10);
oe.customers=nextEvent.customers;
oe.type=2;
add_Heap(eventHeap,oe);
}
else{printf("\n no space:group leaves");limited++;}
}
if(nextEvent.type==2){ /*处理order*/
for(orderSize=0,i=0;i＜nextEvent.customers;i++)
orderSize+=randombetween(1,3);
printf("\ncustomer group of size/%d order/%d scoops of ice cream at time/%d",nextEvent.customers,orderSize,nextEvent.time);
order(store,orderSize);
oe.type=3;
oe.time=nextEvent.time+randombetween(15,35);
oe.customers=nextEvent.customers;
add_Heap(eventHeap,oe);
}
if(nextEvent.type==3){ /*处理leave*/
printf("\ncustomer group of size/%d leave at time/%d",nextEvent.customers.nextEvent.time);
store-＞freeChairs+=nextEvent.customers;
}
}
剩下的order(store,orderSize)可以如下定义:
void order(Store*store,int orderSize)
{store-＞profits+=orderSize*2.5;}
3)结果
以下是程序的某次执行的结果，这3栏分别对应座位数、利润、座位不足的次数。这些数据表明：座位教为50～60时，座位的利用率较高，并且利润也比较高。
sits:35 profits:1539.4375000 limited:881
sits:36 profits:1882.3125000 limited:653
sits:37 profits:2036.8750000 limited:926
sits:38 profits:1738.3125000 limited:816
sits:39 profits:1728.1875000 limited:612
sits:40 profits:1777.9375000 limited:737
sits:41 profits:1895.0625000 limited:341
sits:42 profits:1853.1250000 1imited:362
sits:43 profits:1862.3750000 limited:542
sits:44 profits:1785.9375000 limited:668
sits:45 profits:1658.3750000 limited:494
sits:46 profits:2135.3750000 limited:311
sits:47 profits:1851.5000000 limited:368
sits:48 profits:2153.5625000 limited:286
sits:49 profits:1901.7500000 limited:297
sits:50 profits:2131.9375000 limited:433
sits:51 profits:2036.6875000 limited:463
sits:52 profits:2000.6875000 limited:244
sits:53 profits:2061.8750000 1imited:277
sits:54 profits:1888.1875000 limited:154
sits:55 profits:2105.7500000 limited:258
sits:56 profits:2275.9375000 1imited:291
sits:57 profits:1956.3750000 limited:163
sits:58 profits:2068.0625000 1imited:132
sits:59 profits:1792.5625000 limited:92
sits:60 profits:2262.5625000 limited:329
sits:61 profits:2189.5000000 limited:149
sits:62 profits:2247.7500000 limited:196
sits:63 profits:2308.3125000 limited:332
sits:64 profits:2492.4375000 limited:227
【答案解析】