Dnes je tu pre vas pripraveny jeden program, ktoreho ulohou je vypocet
faktorial. Faktorialy maju v matematike pomerne siroke vyuzitie pri vypoctoch
variacii, permutacii, kombinacii, ale tiez aj pri vypocte roznych
pravdepodobnosti.
Pre tych z vas, ktorym nie je celkom jasne co su to vlastne faktorialy je
venovane nasledujuce male vysvetlenie. Faktorial cisla N (skratene to
zapisujeme "N!") vypocitame tak, ze vynasobime vsetky cele kladne cisla od 1
do N. Pre N=0 sa definuje N!=1. Cize inymi slovami
N! = 1 * 2 * 3 * .... * (N-1) * N.
Urcite vas prave napadlo, ze by sa tento vypocet dal realizovat v basicu
takouto jednoduchou sluckou:
10
LET faktorial = 1
20
FOR i=1 TO N: LET faktorial=faktorial*i: NEXT i
Lenze takto napisany program ma jednu malicku nevyhodu - vie pocitat hodnotu
faktorialov iba v tom rozsahu maximalne zobrazitelneho cisla. Maximalne
zobrazitelne cislo je pre vecsinu basicov okolo 1.7*10^38 co umoznuje pocitat
faktorial iba pre N mensie alebo rovne 33. A to je dost malo.
Istym riesenim by bolo pocitat faktorial tak, ze si v jednej premennej
uchovavame mantisu a v druhej exponent hodnoty "faktorial" v nasej slucke.
Na zaciatku nastavime do mantisy jednotku, do exponentu nulu a v slucke
budeme normalne nasobit parametrom i mantisu, pricom akonahle bude mantisa
vecsia ako 10 tak ju vydelime desiatimi a k exponentu pripocitame jednotku.
Odborne povedane - budeme mantisu udrzovat v normalizovanom tvare. Vysledna
hodnota faktorialu potom bude mantisa*10^exponent. Tym padom mozeme velmi
lahko dosiahnut aby exponent mohol byt vecsi ako 38 (alebo hodnota, ktoru
povoluje dany interpret basicu).
Ale aj toto riesenie ma jeden "maly" hacik. Predstavte si ze chcete vypocitat
faktorial milionu. Vtedy musi nasa slucka prebehnut milion-krat - treba
spravit milion nasobeni, milion priradeni a to este nehovorim o tom, ze bude
treba stale strazit aby mantisa nebola vecsia ako 10 ! Iste uznate, ze doba
vypoctu by nebola zrovna zanedbatelna. A teraz si predstavte, ze by ste
chceli pocitat nie milionty, ale napr. stomilionty, alebo este daleko vyssi
faktorial... To by bolo trochu moc uz aj na najvykonnejsie pocitace sveta.
Preto musime tento problem zacat riesit z uplne ineho konca.
Obidva tieto problemy su vyriesne v nasledujucom programe. Ked si tento
program spustite, skuste si len tak pre zaujimavost pomocou neho vypocitat
hodnotu toto stomilionteho faktorialu. Ked si stopkami odmeriate dobu
vypoctu, pochopite, preco je tento program tu, v rubrike Zazraky v basicu.
Tento sposob vypoctu faktorial je pouzity aj v programe
Matematika 28.
Avsak existuje este jeden dovod, preco je program v tejto rubrike. Tento
program dokaze vypocitat faktorial nielen pre cele cisla, ale aj pre
cisla desatinne.
10
CLS : PRINT BRIGHT 1;"Busy soft: Vypocet faktorial",''
20
INPUT "n=";n: IF n<0 OR n>1e36 THEN GO TO 20
30
IF n<33 THEN LET m=1: FOR c=1 TO n: LET m=m*c: NEXT c:
PRINT INK RND*3;n;"!";TAB 7;"= ";m+(m*INT n)*(n-INT n)*(n-INT n): GO TO 20
40
LET c=(n*LN n-n+LN (2*PI*n)/2+LN (1+0.08344/n))/LN 10:
PRINT INK RND*3;n;"!";TAB 7;"= ";10^(c-INT c);"E+";INT c: GO TO 20
Tento program bol napisany pre ZX Spektrum a vsetky ostatne pocitace a emulatory, ktore su so ZX Spektrom kompatibilne na urovni basicu. Program neobsahuje ziadne zakerne basicove specialitky takze prenos na ine pocitace urcite nebude nikomu robit ziadny problem. Cislo 2e36 na riadku 20 predstavuje priblizne 1/100 z maximalne zobrazitelneho hodnoty. Tato kontola je tu preto, aby pri vypocte roznych medzivysledkov nedoslo k preteceniu. Cleny M*INT N na riadku 30 aproximuju vypocet faktorial pre desatinne cisla mensie ako 33. Vzhladom na obmedzenu presnost cislel (8 platnych cislic) je pre velmi vysoke N vyraz C-INT C na riadku 40 rovny nule. Z toho vyplyva, ze mantisa takehoto faktorialu sa pocita s presnostou na nula platnych cislic a teda jedninym zaujimavym vysledkom je exponent tohto faktorialu - aspon vieme, kolko miest ma tento faktorial.