i
i
“Zerovnik-generator” — 2010/5/31 — 14:49 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 15 (1987/1988)
Številka 3
Strani 188–192
Janez Žerovnik:
TRI NALOGE ZA GENERATOR SLUČAJNIH ŠTE-
VIL
Ključne besede: matematika, računalništvo, generator slučajnih šte-
vil, število π , Galtonova plošča, volilna igra, protivolilna igra.
Elektronska verzija: http://www.presek.si/15/884-Zerovnik.pdf
c© 1988 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
-~ -' LI II", ,- - ,,_ _, I ~ _
TRI NALOGE ZA GENERATOR SLUCAJNIH STEVIL
Kako lahko top uporabimo za računanje površin
Recimo, da želimo izmeriti površino nekega kompliciranega krivočrtnega lika,
na primer takega na sliki 1. Naš lik najprej pokrijmo s kakšnim likom, ki mu
lahko določimo ploščino, na primer spravokotnikom. Ustrelirno s topom ve-
likokrat v različnih smereh na označeno polje. Sklepamo, da je razmerje med
ploščino lika in ploščino pravokotnika približno enako razmerju med številom
zadetkov in številom vseh strelov. Torej lahko iskano ploščino ocenimo takole:
ploščina lika je približno enaka številu zadetkov lika, pomnoženemu s površi-
no pravokotnika in deljenemu s številom vseh strelov.
Seveda ne predlagamo, da vam starši kupijo top in poskusite streljati na
sosedov vrt! Manj nevarno, pa prav tako ali pa šebolj učinkovito, lahko takšne
poskuse delamo na računalniku. Vse, kar potrebujemo, je generator slučajnih I
števil, ki ga večina računalnikov ima. Predpostavimo, da na našem računalniku
obstaja funkcija RANDOM, ki nam vrne slučajno število med O in 1.
V nadaljevanju si bomo ogledali tri primere uporabe generatorja slučajnih
števil.
Slika 1
Računanje števila 1T
Slika 2
Redni bralci Preseka se bodo spomnili članka v Preseku XII /4, v katerem je
opisano, kako lahko izračunamo približek števila 1T s simulacijo metanja Buffo-
188
nove igle, imenovane po francoskem naravoslovcu in matematiku grofu Lou isu
de Buffonu . Še preprosteje izračunamo pribl ižek števila n z idejo streljanja s
topom. Vzemimo za lik krog in mu očrtajmo kvadrat. Ker obe ploš čini znamo
izračunati, vemo, da je njuno razmerje enako (n r 2) : (2 r) 2 = n/4. Če vzame-
mo samo četrtino kroga in kvadrata, kot kaže slika 2, se razmerje ploščin
oč itno ne spremeni. Razmerje med ploščinama lahko ocenimo tudi s strelja-
njem s topom, kot je opisano v začetku . 'Približek za tt je torej 4 * zadetk i/vsi
strel i.
Simul ac ijo naredimo s prep rost im programom. Zarad i preprostosti progra-
ma naj imata stran ica kvad rata in polmer kroga dolžino 1. St rel v kvad rat simu -
liramo z dvak ratnim klicem generatorja slučaj nih šte vil:
x := RANDOM;
y := RANDOM;
ki nam da toč ko s koord inatama v kvadratu [0,1) x [0,1 ). Ali smo zade li no-
t ran jost kroga? Izračunati moramo samo razdaljo to čke od i zhod išča . Spomni-
mo po zabljivce , da razdaljo točke od izhodišča izračunamo preprosto z upora-
bo Pitago rovega izreka: d = V x 2 + y 2 . Če je ta manjša od 1, točka leži v
krogu .
Strel večkrat po novimo in štejemo zadetke. Pri dovolj velikem šte vilu
poskusov bi moralo biti razmerje zadetkov in strelov blizu n/ 4 . Poskusite s
pro gramom simul irati na pr imer 1000 strelov in nam sporočite rezultate. Ob
rezu ltat u navedite tudi računalni k in generator slučajnih števil , k i ste ju upora-
bili. Če se razmerje nikakor ne bo hotelo ustaliti pri n/4,je mogoče, da upo-
rab ljeni gene rator slučajnih števil ni najboljši. O testiranju slučajnih genera-
torjev je Presek že pisal v četrti številki letnika XII.
Slika 3
189
Galtonova plošča
je dobila ime po enem prvih statistikov viktorijanske Anglije, plemiču Francisu
Galtonu. Na sliki 4 vidimo nagnjeno ploščo, na kateri je trikotni gozd č apkov,
na dnu plošče pa nekaj predalov. Kroglo postavimo na vrhnji čepek in jo spusti-
mo. Odbijala se bo od čepkov zdaj levo, zdaj desno in končala venem od pre-
dalov . Če to ponovimo z več kroglami, se nam v predalih pokaže značilna po-
razdelitev . Poglejmo, kako bi Galtonovo ploščo simulirali z računalniškim
programom.
Slika 4
Spremembo smeri kroglice ob trku s čepkom simuliramo s klicem genera-
to rja slučajnih števil. Če je dobljeno število manjše od 0.5 , kroglica nadaljuje v
levo, sicer v desno. Kateri čepek je zadela kroglica in h kateremu nadaljuje? Ni
pomembno! Vemo, da se bo vsaka kroglica odbila od natanko n čepkov, kjer
je n višina (in hkrati širina) gozda čepkov. Hitro vidimo tudi , da je predal, v
katerem kroglica konča, kar enak številu trkov, pri katerih se je kroglica odbila
v desno. To pa pomeni, da v programu ne potrebujemo nobenega polja spre-
menljivk, ki bi ustrezale čepkom na plošči. Potrebno je samo simulirati n trkov
in seveda šteti število odbojev v desno . Nauk zgodbe: Malo analize problema
pred proqrarniranjern nam lahko prihrani veliko truda pri njem!
Opisano zanko vložimo v večjo, ki bo določala število krogel, spuščenih
po plošči. Vsakič, ko se notranja zanka izvede, ne pozabimo povečati števila
kroglic v pravkar zadetem predalu. Če programu dodamo nekaj grafičnih uka-
zov, bomo lahko na zaslonu sproti opazovali nastanek hribčka, značilnega za
binomsko porazdelitev.
190
I
Volilna in protivoliina igra
Naslednji primer je simulacija dveh iger, ki sta ju nedavno študirala profesorja
Peter Donnely in Dominic Welsh. Kvadratke pravokotne šahovnice na začetku
poljubno pobarvajmo s črno in belo barvo. Ali, če želite opravičiti ime igre, na
vsak kvadratek postavimo volilca, barva pa naj predstavlja stranko, ki jo name-
rava voliti na naslednjih volitvah. Ob vsakem udarcu ure (slučajno) izberemo
enega od volilcev, ki bo morda zamenjal stranko. V ta namen (spet slučajno)
izberemo še enega od osmih sosedov. V igri velja pravilo, da se prvi izbrani
volilec vedno pusti prepričati izbranemu sosedu. Barva izbranega voliIca posta-
ne enaka sosedovi, ne glede na prejšnjo barvo.
Da bodo imeli vsi volilci osem sosedov, se dogovorimo, da šahovnico zle-
pimo po robovih takole: volilec na robu naj ima tri sosede na nasprotni strani
šahovnice. Na slik i 5 so narisane soseščine nekaterih značilnih kvadratkov ša-
hovnice . Mimogrede: premislite, kakšno ploskev v prostoru dobimo, če na
opisani način zares zlepimo nasprotne stranice pravokotnika . Če premislek ne
gre , poskusite s papirjem in lepilnim trakom.
,..-- -- --,
I I
r -
I X X
I
I
X XI
I
I X X
L_
r -
I
I
I
I
I I
I IL., ~
Slika 5
x
x
x
3 2 1
4MO
567
Slika 6
Ko opisani preprosti model dvostrankarskega volilnega sistema zaživi, se
začno dogajati zanimive stvari. Najprej se namesto razpršenih belih in črnih
polj pojavijo večja področja, pobarvana z isto barvo. Potem se enobarvna po -
dročja nekaj časa premikajo po šahovnici in se borijo za prevlado. Na koncu
ena barva preplavi vso šahovnico.
Volilno igro simuliramo s preprostim programom. V dvodimenzionalno
polje, ki nam predstavlja šahovnico, vnesemo začetne barve polj. Če ne druga-
če, jih določimo slučajno. Z dvema klicema generatorja slučajnih števil izbere-
191
mo polje, ki mu bomo v naslednjem koraku spreminjali barvo. Slučajno celo
število, ki z enako verjetnostjo zavzame vrednosti O, 1, 2, ..., n - 1, dobimo
takole:
s := INT (n * RANDOM); kjer je INT f unkcija celi del. Celi del realnega
števila x je največje celo število, ki ni večje od števila x . (Na primer : INT(O.5) =
= O, INT(3.14) = 3, INT(-4.5) =-5.) En korak igre sprogramiramo takole :
izberemo celi slučajni števili i med O in n - 1 ter j med O in m, kjer smo z min
n označili širino in dolžino šahovnice. Par števil il, il nam podaja koordinate
nekega polja s šahovnice. Potem izberemo še eno celo slučajno število k med O
in 7, ki nam določi soseda, na primer tako, kot je narisano na sliki 6. Popravi -
mo barvo polja (j,j) in en korak igre je zaključen.
Program bo zanimivejši, če bo stanje sproti risal na zaslon. Že z uporabo
dveh kontrastnih znakov, na primer zvezdice in pike, dosežemo dober učinek.
Druga igra, ki je model nekoliko bolj pluralistične družbe, je protivoliina
igra. V tej igri se izbrani volilec ne pusti prepričati sosedu, pač pa vedno zavza-
me stališče, nasprotno sosedovemu. Kako pa se model obnaša v tem primeru?
~~~~~ ~~ ~ ~~~~~~
I~~ ~ ~~I~ ~I~ ~ ~~~~~
~~~~~~~~~ ~~~~~
~~~~~~~~~~ ~~~19'lIm
~~~I~I~ ~ ~ ~~ ~ ~~~~
~~I~I~j~j~ ~ ~ ~ ~~~~~
~~I~ I~ I~~~~~~ ~~ ~~
~~~ ~! iA?n~~~~ ~~~ ~~Iw!lru
:fill l~~ ~ ~~~~~I~~~~~
Slika 7
Janez Ž erovnik
192
' }