4. Náhodná čísla

V této kapitole se budeme věnovat (pseudo)náhodným číslům, která se při různých programátorských úkolech hodí, protože ne vždy chceme, aby počítač prováděl náš program pořád stejně dokola, ale aby do něj vnesl nějakou náhodu. Například kdyby počítač měl simulovat hru člověče, chceme, aby dvě hry za sebou nebyly stejné (tzn. neměly stejné hody, respektive, aby to bylo málo pravděpodobné).

Příklady této kapitoly se budou zabývat generováním těchto pseudonáhodných čísel, zjišťování statistik o těchto číslech a simulací různých problémů.

Co je to náhodné číslo

Je taková devítka náhodné číslo? O konkrétním čísle to už nelze říct. Náhodné číslo je pojem označující číslo/prvek z nějakého ohraničeného intervalu/množiny, které není možné předem předvídat na základě hodnot vygenerovaných dříve. Jednoduše pochopitelným příkladem je férová (neupravená) šestistěnná kostka, u níž nevíte co vám při následujícím hodu padne za číslo. Víte jen, že to bude číslo z intervalu [1,6] a že každé číslo padá stejně často, tedy rozložení čísel je uniformní (rovnoměrné). Existují i další rozložení, ale v této kapitole je potřebovat nebudeme.

_images/random_number.png

(zdroj: XKCD)

Pseudonáhodná čísla

„Kdokoliv, kdo zvažuje získávání náhodných čísel pomocí aritmetických metod se nachází ve stavu hříchu.“. V této slavné větě se vyjadřuje John von Neumann k tomu, že počítače jsou konstrukcí deterministické a s generováním opravdu náhodných čísel mají poměrně problém. Generování opravdu náhodných čísel typicky závisí na externích zařízení jako jsou rozpady radioktivních látek atp. Pro velkou část vstupů se ale obejdeme s pseudonáhodnými čísly, která vykazují jen některé náhodnostní rysy. Pro účely tohoto předmětu nám tyto pseudonáhodná čísla stačí. Zmíníme-li někdy náhodná, máme namysli pseudonáhodná.

Jak je používat v Pythonu

Funkce pro práci s náhodnými čísly se nacházejí v samostatném modulu random a jsou to randint(nejnizsi, nejvyssi), která vygeneruje číslo v intervalu [nejnizsi, nejvyssi] a random(), která vygeneruje číslo v intervalu [0.0,1):

Python generuje čísla deterministicky

Python (a další programovací jazyky) generují pseudonáhodná čísla z takzvaného semínka (seedu) za pomoci deterministických metod. Proto dvě spuštění následujícího kódu vygenerují stejné náhodné číslo.

4.1. Hrátky s náhodností

4.1.1. Šestiboká kostka

Napište funkci, která bude vracet nově vygenerované náhodné číslo simulující šestistěnnou kostku s čísly 1–6.

from random import randint

def dice():
    pass

print(dice(), dice(), dice())

4.1.2. Dokud padá sudé číslo

Napište funkci, která bude provádět házení obyčejnou šestistěnnou kostkou tak dlouho dokud nepadne liché číslo. Poté funkce vrátí celkový součet všech hozených hodů.

from random import randint

def turn():
    pass

print(turn(), turn(), turn())

4.1.3. Statistiky

Napište funkci, která vygeneruje a vypíše count náhodných čísel v intervalu [lower, upper] a následně vypíše nejmenší, největší číslo. Vypište také aritmetický průměr ze všech vygenerovnaých čísel.

from random import randint

def statistics(count, lower, upper):
    pass

statistics(10, 1, 100)

4.1.4. Frekvence kostky

Napište funkci, která provede count hodů obyčejnou šestibokou kostkou a následně vypíše kolikrát které číslo padlo. Tip: pro ukládání frekvencí se mohou hodit seznamy z následující kapitoly či nějaká jiná datová struktura.

from random import randint

def dice_freq(count):
    pass

dice_freq(1000)

4.1.5. Frekvence součtu hodů dvou kostek

Napište funkci, která provede count hodů dvěma šestibokými kostkami, následně vypíše kolikrát daný součet (2 až 12) padl. Tip: pro ukládání frekvencí se mohou hodit seznamy z následující kapitoly či nějaká jiná datová struktura.

from random import randint

def two_dice_freq(count):
    pass

two_dice_freq(1000)

4.1.6. Falešná mince

Napište funkci, která bude simulovat falešnou minci (hlava je True a orel je False). Hlava padá s pravděpodobností 85 % a orel s pravděpodobností 15 %.

from random import randint, random

def coin_flip():
    pass

print(coin_flip())

4.2. Simulace a analýzy

4.2.1. Opilec na cestě domů

Opilec je na půli cesty mezi domovem a hospodou, každý krok udělá náhodně jedním směrem. Napište funkci, která bude simulovat opilcův pohyb. Jejími parametry budou vzdálenost mezi domovem a hospodou a počet kroků do opilcova usnutí (tj. maximální délka simulace). Simulace skončí buď tehdy, když opilec dojede domů nebo do hospody, případně po vyčerpání počtu kroků.

Ukázkový výstup:

>>> drunkman_simulator(10, 100)

home . . . . . * . . . . pub
home . . . . * . . . . . pub
home . . . * . . . . . . pub
home . . . . * . . . . . pub
home . . . * . . . . . . pub
home . . . . * . . . . . pub
home . . . * . . . . . . pub
home . . * . . . . . . . pub
home . * . . . . . . . . pub
home . . * . . . . . . . pub
home . . . * . . . . . . pub
home . . * . . . . . . . pub
home . . . * . . . . . . pub
home . . * . . . . . . . pub
home . . . * . . . . . . pub
home . . . . * . . . . . pub
home . . . . . * . . . . pub
home . . . . * . . . . . pub
home . . . . . * . . . . pub
home . . . . * . . . . . pub
home . . . . . * . . . . pub
home . . . . . . * . . . pub
home . . . . . * . . . . pub
home . . . . . . * . . . pub
home . . . . . . . * . . pub
home . . . . . . . . * . pub
home . . . . . . . . . * pub
home . . . . . . . . * . pub
home . . . . . . . . . * pub
home . . . . . . . . . . pub
Ended in the pub again!

from random import randint, random

def drunkman_simulator(size, steps):
    pass

drunkman_simulator(10, 100)

Vyzkoušejte různé kombinace parametrů? Při jaké konfigurace dochází domů už celkem pravidelně?

4.2.2. Analýza opilce

Pokud jste se zabývali otázkami položenými v předchozím příkladu, zjistili jste, že to není až tak jednoduché zjistit. V tomto příkladu tedy použijeme předchozí program pro jednoduchou analýzu, jak to dopadne, když to zkusíme zopakovat vícekrát za sebou.

Nejprve upravte funkci z předchozí příkladu tak, aby nevypisovala stav opilce (například přidáním volitelného parametru output a zapodmínkováním výpisu) a aby vracela True dojde-li opilec domů a False pokud ne.

Následně napište funkci, která provede simulaci opilce count krát a vypíše procentuální úspěšnost dojití domů.

from random import randint, random

def drunkman_simulator(size, steps, output=False):
    pass

def drunkman_analysis(size, steps, count):
    pass

drunkman_analysis(10, 100, 100)
# Arriving home in 45.0 % of cases

4.2.3. Hledač pokladů

Máme hledače pokladů, který hledá právě jeden ukrytý poklad ve čtverci o hraně width polí. Hledač začíná na pozici [0,0] (vlevo nahoře) a v každém kroku se pohne jedním ze 4 směrů se stejnou pravděpodobností. Pokud by měl vyjít ze čtverce, zůstává stát (a jeho neúspěšný krok se započítá).

Napište funkci, která pro zadanou šířku width zjistí, zdali v steps krocích hledač najde poklad.

Následně napište funkci, která provede předchozí funkci pro zadaný parametr count krát a vypíše, jaká je pravděpodobnost nalezení pokladu.

Poklad na začátku umístěte na náhodnou pozici.

from random import randint, random

def treasure_hunter(width, steps):
    pass

def treasure_hunter_analysis(width, steps, count):
    pass

treasure_hunter_analysis(10, 100, 100)
#Treasure found in 33.0 % of cases

4.2.4. Čekání na tramvaj

Chcete vědět, jak dlouho budete čekat na zastávce šaliny. Šalina jezdí každých n minut. Nasimulujte count náhodných příchodů na zastávku (v náhodné časy). Vytiskněte, v kolika procentech případů budete čekat déle než w minut.

from random import randint

def tramway_waiting_more_than(w, n, count):
    pass

tramway_waiting_more_than(4, 5, 100)

Srovnejte nasimulovanou pravděpodobnost s vypočítanou pravděpodobností (pomocí geometrické pravděpodobnosti).

4.2.5. Průměrná vzdálenost dvou bodů ve čtverci

Napište funkci, která náhodně zvolí dva body ze čtverce o velikosti size a vrátí jejich vzdálenost. Následně napište funkci, která tento výběr bude opakovat count krát a vypíše průměrnou vzdálenost.

from random import randint, random

def random_points_distance(size):
    pass

def average_points_distance(count, size):
    pass

print(average_points_distance(100, 5))

4.2.6. Tipující student

Napište funkci, která experimentálně zjistí (pro count pokusů) jaká je pravděpodobnost, že student natipuje alespoň polovinu n otázkového testu, ve kterém každá otázka má právě 4 možnosti a právě jedna z nich je správně.

from random import randint

def random_student(n, count):
    pass

random_student(10, 100)

Srovnejte experimentálně zjištěnou hodnotu s teoreticky odvozenou hodnotou.

4.2.7. Odhad čísla PI

Naprogramujte funkci využívající náhodná čísla pro odhad čísla PI za použití metody Monte Carlo, podrobnější popis viz http://mathfaculty.fullerton.edu/mathews//n2003/montecarlopimod.html

Shrnutí algoritmu:

  • Potřebujete n náhodných bodů ve čtverci o hraně a

  • Z n vygenerovaných bodů leží nějaký počet m v kruhu vepsanému tomuto čtverci

  • Obsah čtverce je S2 = a^2

  • Obsah kruhu je S1 = PI * (a/2)^2

  • Odhad PI je PI = 4 * (m/n)

from random import randint, random

def guess_pi(count):
    pass

print(guess_pi(1000))

Jaký je vztah mezi počtem pokusů a výsledným odhadnutým číslem PI? Proč?

4.2.8. Náhodné pexeso

Naprogramujte funkci, která nasimuluje jednu hru pexesa na jednorozměrném hracím plánu o velikosti size a vrátí počet provedených tahů. Poté zjistěte průměrnou délku jedné hry, pro hrací pole různých délek.

Poznámky: v tomto příkladu využijete seznamy, nezapomeňte také, že velikost šachovnice podléhá jistým omezením, které správný programátor zkontroluje.

from random import randint, shuffle

def pexeso(size, output = False):
    pass

def average_pexeso_length(board_sizes = range(2, 20, 2), count = 100):
    pass

print(pexeso(10, True))
average_pexeso_length()
Next Section - 5. Řetězce a seznamy