Rad

Banka

Program Spustiteľná verzia

Dĺžku intervalu medzi dvoma príchodmi a tiež dĺžku trvania obsluhy generujeme pri plánovaní nových udalostí náhodne. Pri tom je však potrebné poznať rozdelenie pravdepodobnosti príslušných náhodných veličín! Aj keď táto problematika patrí skôr na hodinu „modelovania a simulácie“ a vyžaduje tiež aspoň základné vedomosti z teórie pravdepodobnosti, aspoň naznačíme spôsob generovania náhodných číselných postupností v našom programe:

• Predpokladáme, že intervaly medzi príchodmi i dĺžka obsluhy majú tzv. exponenciálne rozdelenie so strednými hodnotami 75 a 120 sekúnd (zo zadania).
• Pomocou rand získame nejaké celé číslo z intervalu 0 až RAND_MAX
• My však potrebujeme náhodné číslo z intervalu ⟨0, 1). Preto použijeme makro real_rand
• Takto získané náhodné číslo je z tzv. rovnomerného rozdelenia na intervale ⟨0, 1). Musíme ho pomocou funkcie exp_rand transformovať na náhodné číslo z požadovaného rozdelenia
• Okrem toho tiež potrebujeme zabezpečiť nezávislosť dvoch náhodných číselných postupností. Na to využijeme štandardnú funkciu srand, ktorá umožňuje nastaviť počiatočnú hodnotu generátora. V premenných SeedPrich, SeedObsl si budeme pamätať pre každú postupnosť posledné vygenerované číslo, aby sme mohli pokračovať pri generovaní ďalšieho „tam kde sme skončili.“ V hlavnom programe voláme preto podľa potreby jednu z funkcií GenerujDalsiPrichod a GenerujDlzkuObsluhy

/* pripojenie potrebných hlavičkových súborov */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <time.h>
#include <math.h>

/* makro */
#define real_rand(cislo) ((double) (cislo)/(RAND_MAX + 1.0));

/* symbolické konštanty  – zo zadania */
#define StrPrich 75.0
#define StrObsl 120.0
#define MaxDlzkaRadu 30

/* definícia typov */
typedef enum {
	PrichodZakaznika, KoniecObsluhy
} TypUdalosti;

typedef enum {
	false, true
} boolean;

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

/* globálne premenné */
TUdalost *Zac;          /* ukazovateľ na začiatok osi */
TUdalost *AktUdal;      /* ukazovateľ na aktuálnu udalosť */
TypUdalosti TypAktUdal;
double SimulCas;

/* premenné a funkcie súvisiace s náhodným generovaním */
unsigned SeedObsl, SeedPrich;
double exp_rand(unsigned *Seed, double StrHodnota);
double GenerujDalsiPrichod();
double GenerujDlzkuObsluhy();

---------------------------------------------------------------------------------
void vloz(TUdalost *NovaUdal) /* vloženie novej udalosti na správne miesto */
{
	double CasNovej;
	TUdalost *p1, *p2;

	CasNovej = NovaUdal->cas;
	p1 = Zac->nasl;
	p2 = Zac;

	while (p1->cas <= CasNovej) {
		p2 = p1;
		p1 = p1->nasl;
	}

	p2->nasl = NovaUdal;
	NovaUdal->nasl = p1;
}
---------------------------------------------------------------------------------
void zrus_os() /* uvoľnenie pamäte po uplynutí simulačného času */
{
	TUdalost *p1, *p2;

	p1 = Zac->nasl;
	while (p1 != Zac) {
		p2 = p1;
		p1 = p1->nasl;
		free((void*)p2);
	}
	free((void*)Zac);
	Zac = NULL;
}
---------------------------------------------------------------------------------
void main()  /* hlavný program */
{
	int PocZak = 0;   /* počet všetkých zákazníkov */
	int PocCakZak = 0;   /* počet tých, ktorí museli po príchode čakať */
	int PocObslZak = 0;   /* počet obslúžených */
	int PocOdmietZak = 0; /* počet odmietnutých */
	int DlzkaRadu = 0;   /* počet ľudí v rade */

	double CasCakCelkom = 0.0;  /* celkový čas, ktorí museli čakať všetci zákazníci spolu */

	double PredchAktCas = 0.0;  /* čas predchádzajúcej udalosti */
	double AktCas;   /* čas aktuálnej udalosti */
	double DeltaCas; /* dĺžka časového intervalu od prechádzajúcej udalosti po aktuálnu */
	int ObsluhaVolna = true;

	/* vstup */
	clrscr();
	printf("Simulacny cas (v sekundach): ");
	scanf("%lf", &SimulCas);

	randomize(); SeedPrich = rand();
	randomize(); SeedObsl  = rand();

	/* konštrukcia prázdnej časovej osi */
	Zac = (TUdalost*)malloc(sizeof(TUdalost));
	Zac->cas = 1.7E38;
	Zac->nasl = Zac;

	/* naplánovanie príchodu prvého zákazníka */
	AktUdal = (TUdalost*)malloc(sizeof(TUdalost));
	AktUdal->typ = PrichodZakaznika;
	AktUdal->cas = GenerujDalsiPrichod();

	/* vloženie novej udalosti do frontu */
	vloz(AktUdal);

	/* simulácia */
	do {
		AktUdal = Zac->nasl;
		Zac->nasl = AktUdal->nasl;
		AktCas = AktUdal->cas;
		DeltaCas = AktCas - PredchAktCas;
		if (DlzkaRadu > 0) CasCakCelkom += DlzkaRadu * DeltaCas;
		TypAktUdal = AktUdal->typ;
		if (TypAktUdal == PrichodZakaznika) {
			if (DlzkaRadu < MaxDlzkaRadu) {
				PocZak++;
				if (ObsluhaVolna) {
					AktUdal->cas += GenerujDlzkuObsluhy();
					AktUdal-> typ = KoniecObsluhy;
					vloz(AktUdal);
					ObsluhaVolna = false;
					AktUdal = (TUdalost*)malloc(sizeof(TUdalost));
				}
				else {
					DlzkaRadu++;
					PocCakZak++;
				}
		}
		else PocOdmietZak++;

		AktUdal->cas = AktCas + GenerujDalsiPrichod();
		AktUdal->typ = PrichodZakaznika;
		vloz(AktUdal);
	}
	else {                /* koniec obsluhy */
		PocObslZak++;
		if (DlzkaRadu > 0) {
			AktUdal->cas += GenerujDlzkuObsluhy();
			AktUdal->typ = KoniecObsluhy;
			vloz(AktUdal);
			DlzkaRadu--;
		}
		else {
			free((void*)AktUdal);
			ObsluhaVolna = true;
		}
	}
	PredchAktCas = AktCas;

	} while (Zac->nasl->cas <= SimulCas);

	zrus_os();

	/* výstup */
	clrscr();
	printf(" \nV Y S L E D K Y \n\n");
	printf("Zakaznik cakal v rade priemerne: ");
	printf("%0.4lf s\n", (PocCakZak == 0) ? 0 : CasCakCelkom/PocCakZak);
	printf("Priemerna dlzka radu pred okienkom: %0.4lf\n", CasCakCelkom/SimulCas);
	printf("Celkovy pocet zakaznikov, ktori prisli do banky: %d\n", PocZak);
	printf("Pocet odmietnutych zakaznikov: %d\n", PocOdmietZak);
	printf("Pocet skutocne obsluzenych zakaznikov: %d\n", PocObslZak);
	getch();
}
---------------------------------------------------------------------------------
double exp_rand(unsigned *Seed, double StrHodnota)
{
	srand(*Seed);    /* nastavenie poslednej vygenerovanej hodnoty */
	*Seed = rand();  /* ďalšie náhodné číslo */
	double cislo = real_rand(*Seed);    /* číslo z <0, 1) */
	return (-StrHodnota * log(1 - cislo)); /* transformácia */
}

/* funkcie zabezpečujúce nezávislosť dvoch postupností náhodných čísel */
double GenerujDalsiPrichod()
{
	return (exp_rand(&SeedPrich, StrPrich));
}

double GenerujDlzkuObsluhy()
{
	return (exp_rand(&SeedObsl, StrObsl));
}