8. Posuvný register

8.2 Problém - Hod kockou

  Vytvorte program umožňujúci zrealizovať náhodný pokus, pri ktorom sa hádže hracou kockou s cieľom zistiť, koľkokrát padne stena s jednou, dvomi, tromi, štyrmi, piatim resp. šiestimi bodkami (relatívne početnosti týchto náhodných udalostí). Počet pokusov načítajte zo vstupu. V programe však nesmie byť na generovanie náhodných čísel použitá funkcia rand, s využitím posuvného registra vytvorte vlastný generátor pseudonáhodných čísel!

Riešenie

Zrealizovať náhodný pokus - hod kockou - znamená náhodne vygenerovať číslo z množiny {1, 2, 3, 4, 5, 6}. S použitím generátora pseudonáhodných čísel, ktorý je v C k dispozícii, by to skutočne nebol žiadny probém:

#include <stdlib.h>
#include <time.h>
...

randomize();
for (int i = 1; i <= PocetPokusov; i++)
   printf("Padlo cislo %d\n", (rand() % 6) + 1);

  Operátor % (mod, modulo) znamená zvyšok po celočíselnom delení, pri delení číslom 6 máme zvyšky 0, 1, 2, 3, 4, 5.

Vlastný generátor pseudonáhodných čísel môžeme vytvoriť na základe vhodného rekurentného vzťahu:

xn+1 = f( xn-k, ..., xn-1, xn) ,   0<= k <= n

Podľa tohto vzťahu každý ďalší člen v generovanej postupnosti čísel určíme na základe hodnôt predchádzajúcich členov postupnosti. Na rovnakom princípe funguje v podstate väčšina počítačom používaných generátorov pseudonáhodných číselných postupností.

Veľkú skupinu metód generovania tvoria tzv. kongruenčné metódy, pri ktorých majú príslušné rekurentné vzťahy väčšinou jeden z tvarov:

xn+1 = (xn-k+ xn) mod M,    xn+1 = (A·xn) mod M,    xn+1 = (A·xn + C) mod M

V postupnosti čísel generovanej podľa kongruenčných metód sa objavujú "len" čísla 0, 1, ..., M-1 (zvyšky). Aby sme takto získali "dobrú" postupnosť čísel, t.j. takú, v ktorej sa budú všetky čísla objavovať s rovnakou pravdepodobnosťou, musíme nájsť nielen vhodný rekurentný vzťah, ale i vhodné "štartovacie" hodnoty - prvé členy postupnosti, na základe ktorých sa začne výpočet ďalších.

V našom programe využijeme generátor založený na tomto rekurentnom vzťahu:

xn+1 = f(xn-3, xn-2, xn-1, xn)

Ďalší člen teda vždy vypočítame z hodnôt štyroch predchádzajúcich. Pre konkrétnosť uvažujme vzťah v tvare:

xn+1 = ((7·xn-3 + xn + 991) mod 6) + 1

Potrebujeme teda 4 počiatočné hodnoty. Nech napr. x0 = 3, x1 = 5, x2 = 6, x3 = 2

Vytvoríme 5 prvkový posuvný register (ako lineárny zoznam), štyri počiatočné hodnoty načítame zo vstupu:

Vypočítame ďalší člen:
x4 = ((7·x0 + x3 + 991) mod 6) + 1 = 1

Posunieme prvky v registri doľava odobratím prvku zo začiatku a pridaním nového prvku na koniec.

Vypočítame ďalší člen:
x5 = ((7·x1 + x4 + 991) mod 6) + 1 = 2

Posunieme prvky v registri doľava a vypočítame ďalší člen atď.

  Ak potrebujeme kvôli výpočtu nasledujúcej hodnoty uchovávať menší počet predchádzajúcich hodnôt, vystačíme aj s "obyčajnými" premennými príslušného typu (napr. int či float). Pri zložitejších numerických metódach založených na rekurentných vzťahoch však použitie posuvného registra môže výpočet významne zjednodušiť už tým, že sa vyhneme "postupnému" posúvaniu hodnôt:   x0 = x1;  x1 = x2;  x2 = x3;  x3 = x4;  atď.

[Program]