Jistě jste se už mnohokrát setkali s náhodným číslem. Dá se použít v mnoha různých programech - já bych se zde však rád věnoval jednomu speciálnímu případu, kdy potřebujete zajistit náhodný výběr z určité množiny čísel bez opakování.
Nejnázornějším příkladem je program na náhodný tip pro číselné loterie. Většina z Vás si už nějaký takový prográmek určitě zkusila udělat. Algoritmus (způsob řešení) v tomto programu musel zajišťovat, aby se každé náhodně vybrané číslo vyskytovalo jen jednou. Předpokládám, že jste to měli udělané tím způsobem, že každé vybrané číslo jste si uložili do pole a při dalším výběru porovnali, jestli již v tomto poli není (a tedy jestli již nebylo vylosované). To je jistě správný způsob, ale zdaleka není nejefektivnější.
Problém je v tom, že se vždy vybírá ze všech čísel a pak se ověřuje, zda již dříve toto číslo nebylo. Tím pádem nemáte nijak zaručeno, jak dlouho takový výběr bude trvat. Může se stát, že bude mnohokrát vybráno již dříve vybrané číslo a tedy se výběr bude muset vícekrát opakovat. A teď si představte, že byste potřebovali vybírat stále dál a do vyčerpání všech čísel. Tento jednoduchý algoritmus by měl velké potíže, protože s rostoucím počtem vybraných čísel roste pravděpodobnost, že se "trefíte" právě do některého z již vylosovaných. Pokud budete chtít vybrat postupně 100 čísel ze 100, bude to trvat velmi dlouho. Podívejme se třeba na okamžik, kdy vybíráte 91.číslo. Jednak ho budete muset porovnat s 90-ti čísly v poli (to jsou ta, co již byla vytažena) a je 90-procentní pravděpodobnost, že tam již bude. No prostě - pěkně se načekáte..
Ale jde to i jinak.
Zkusme to řešit obdobně, jako to funguje v praxi při vybírání míčků s čísly z losovacího bubnu. Tam je totiž automaticky zajištěno, že nebude vybrán některý z již vybraných míčků, protože tam již není. A my to uděláme obdobně:
10 MICKU=100: TAH=100 20 DIM POLE(MICKU) 30 FOR X=1 TO MICKU: POLE(X)=X: NEXT X 40 FOR X=1 TO TAH 50 POCET=MICKU+1-X 60 A=INT(RND(0)*POCET)+1 70 LOS=POLE(A) 80 POLE(A)=POLE(POCET) 90 PRINT LOS;" "; 100 NEXT X
10: Proměnná MICKU se nastaví na počet míčků v osudí, TAH označuje, kolik míčků budeme vybírat. (TAH musí být menší nebo roven MICKU.)
20: Deklarace pole o velikosti počtu míčků - pro každý míček jedno místo v poli.
30: Inicializace pole. Každé místo v poli je naplněno číslem (jakoby číslo, které je napsáno na míčku).
40: Cyklus pro X od 1 do počtu losovaných míčků.
50: POCET se nastaví na hodnotu, kolik míčků ještě zbývá v osudí.
60: Náhodně nastavená proměnná A v rozmezí 1 až POCET (včetně 1 a POCET). Vyjadřuje index - pořadí míčku, který bude vybrán.
70: Proměnná LOS je nastavena na číslo, které je na tomto míčku napsané.
80: Na místo míčku, který jsme vybrali, dáme míček z místa POCET.
90: Vytiskneme číslo, které je na vylosovaném míčku.
100: Pokračování v cyklu.
Místa v poli nám představují jednotlivé míčky. Náhodně vždy vybíráme index v poli - vylosovaný míček. Na jeho místo pak dáme poslední míček v poli, aby zaplnil mezeru. Každý další výběr indexu bude proveden z rozmezí shora o 1 menšího.
Tento princip funguje spolehlivě a podstatně rychleji než princip prvně popsaný. Navíc se dá přesně změřit doba, za kterou daný počet čísel bude náhodně vybrán a tato doba bude vždy stejná.