Algoritmy v BASICu¢N*hodn` v`b%r bez opakov*n)¢Radek ③t%rba, RASTER¢¢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¢¢Vysv%tlivky:¢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.¢¢Jak to funguje?¢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*.¢
