6. Rad

6.2 Problém - Banka

  Do banky prichádzajú k okienku s platobnými kartami klienti v priemere každých 75 sekúnd. Obslúženie zákazníka trvá pracovníkovi banky priemerne 2 minúty. Ak je pri príchode zákazníka do banky okienko obsadené, postaví sa na koniec radu a čaká. Predbiehanie nie je dovolené, z priestorových dôvodov môže pred okienkom stáť v rade najviac 30 ľudí. Predpokladáme tiež, že zákazníci sú trpezliví a v priebehu čakania už nikto z radu neodchádza. Hneď ako je zákazník pri okienku vybavený, odíde a k okienku môže pristúpiť prvý v rade.

Vytvorte program, ktorý bude simulovať popísanú situáciu a po uplynutí "simulačného" času oznámi koľko zákazníkov bolo oblúžených, aká bola stredná dĺžka radu pred okienkom resp. koľko zákazník v priemere čakal v rade.

Riešenie

Zákazníci prichádzajúci do banky vytvárajú pred okienkom rad a zdá sa preto celkom prirodzené, že aj v programe bude tento rad reprezentovaný rovnakou dynamickou údajovou štruktúrou. O zákazníkoch prichádzajúcich do banky však nemáme k dispozícii žiadne informácie, ktoré by bolo potrebné uchovávať, zaujímajú nás len ich počty (celkový počet, počet ľudí v rade, počet obslúžených zákazníkov, ...). Na to nám postačia "obyčajné" celočíselné premenné. Dynamickú údajovú štruktúru front použijeme na reprezentáciu úplne iného radu!

Chceme simulovať dej prebiehajúci v čase. Zákazníci prichádzajú, čakajú v rade, sú obsluhovaní, odchádzajú. V istom časovom okamihu sa odohrá najviac jedna udalosť. Budeme sledovať dve udalosti: príchod zákazníka ("zákazník vošiel do banky" ) a koniec obsluhy ("zákazník je vybavený, odchádza od okienka").

Výskyt jednotlivých udalostí môžeme znázorniť na časovej osi:



t0 = 0 s je okamih začiatku simulácie. V čase t1, t2, t4 prichádza zákazník, v čase t3, t5 skončila obsluha zákazníka, ktorý bol práve pri okienku atď.

Na každú udalosť je potrebné správnym spôsobom zareagovať - obslúžiť ju. Aj podľa obrázku je zrejmé, že udalosti tvoria rad. Obslúžená bude vždy tá udalosť, ktorá je práve na začiatku radu t.j. je aktuálna. Časovú os tvorenú postupnosťou udalostí je preto vhodné implementovať v programe ako front. Jeho prvky budú typu TUdalost:

typedef struct udalost {
  double cas;
  TypUdalosti typ;        
  struct udalost *nasl;
} TUdalost;

TUdalost *Zac, *AktUdal;

Čas príchodu ďalšieho zákazníka (presnejšie dĺžku intervalu medzi dvoma príchodmi) ako aj dĺžku trvania obsluhy budeme generovať náhodne (využijeme generátor pseudonáhodných čísel rand). Každú novú udalosť zaradíme do frontu na správne miesto podľa času. Nepôjde teda o "klasický" front, do ktorého sa môžu prvky pridávať výlučne na koniec. Udalosti, ktoré majú nastať skôr, majú prednosť.

Najskôr vytvoríme prázdnu časovú os:

Zac = (TUdalost*)malloc(sizeof(TUdalost));
Zac->cas = 1.7E38;
Zac->nasl = Zac;

Prvok, na ktorý ukazuje Zac nie je udalosťou, poslúži len ako zarážka uľahčujúca vkladanie novej udalosti na správne miesto. Hodnotou položky cas v zarážke môže byť nejaké "dostatočne veľké" reálne číslo.

Naplánujeme príchod prvého zákazníka a vložíme novú udalosť do frontu:

Prvý zákazník príde napríklad v čase 20 s.

Údajový typ TypUdalosti bude definovaný takto:

typedef enum {
  PrichodZakaznika, KoniecObsluhy
} TypUdalosti;

Ak teda ide o príchod zákazníka, tak príslušná udalosť má v položke typ uloženú hodnotu 0, pre koniec obsluhy hodnotu 1.

Všimnite si, že na prvú udalosť vo fronte ukazuje Zac->nasl  !!!

Teraz už môžeme odštartovať simuláciu. Kým neuplynie zvolený simulačný čas (načítaný na vstupe), opakujeme v cykle uvedený postup:



Simuláciu ukončíme, keď uplynie simulačný čas - testujeme či nasledujúca udalosť, ktorá má byť vybratá z frontu nenastane až po uplynutí simulačného času.

  Aby sme mohli na výstupe oznámiť požadované výsledky, musíme počas simulácie počítať prichádzajúcich zákazníkov, koľko z nich po príchode čakalo, koľkí boli odmietnutí, koľko času strávili čakajúci spolu v rade, momentálnu dĺžku radu. Pre výpočet je tiež potrebné priebežne uchovávať čas aktuálnej a predchádzajúcej udalosti ako aj dĺžku časového intervalu od poslednej udalosti.

Výber aktuálnej udalosti zo začiatku frontu sa realizuje v dvoch krokoch:

AktUdal = Zac->nasl;




Zac->nasl = AktUdal->nasl;

Vloženie novej udalosti do frontu na správne miesto:



V cykle prechádzame zoznamom, hľadáme miesto, kam sa má nová udalosť zaradiť. Smerník p2 ukazuje na prvok, ZA ktorý vložíme novú udalosť.



Ak pri prehľadávaní zoznamu dosiahneme zarážku (p1 == Zac), nová udalosť bude vložená na koniec frontu!

[Program]