0 dní v řadě · 0 bodů

Rozhodování a cykly · 40 min

Mise: hra na hádání čísla

Postavíš hru na hádání čísla s limitem pokusů a kontrolou vstupu. Pak se role otočí a hádat bude počítač, půlením intervalu.

Hloubka
Úkoly
Lidsky řečeno

Znáš to z dětství: „Myslím si číslo.“ „Padesát?“ „Míň.“ „Dvacet pět?“ „Víc.“ Kamarád, který si číslo myslí, dělá tři věci pořád dokola: poslouchá, porovnává a odpovídá. Přesně tohle teď naučíš počítač. Nic nového k tomu nepotřebuješ, jen poskládáš podmínky a cykly z předchozích lekcí do jednoho programu.

Krok 1: tajné číslo a jeden tip

Počítač si musí něco „myslet“. Náhodná čísla umí modul random. Modul je sada hotových nástrojů, kterou si do programu přineseš příkazem import. Podrobně se k němu vrátíš v lekci random, math a statistics, teď stačí jediná funkce.

import random

random.seed(7)
tajne = random.randint(1, 100)
print("Myslím si číslo", tajne)
print("Další dvě losování:", random.randint(1, 100), random.randint(1, 100))
Výstup
Myslím si číslo 42
Další dvě losování: 20 51

random.randint(1, 100) vrátí celé číslo od 1 do 100 a obě krajní hodnoty se můžou trefit. Řádek random.seed(7) nastaví výchozí bod losování, takže ukázka dá pokaždé stejná čísla. V učebnici se to hodí, ve skutečné hře ho smažeš, jinak by si počítač myslel pořád totéž.

Kvíz

Která čísla může vrátit random.randint(1, 100)?

Teď jeden tip. Tajné číslo si zatím napevno určíme, ať se dá program snadno zkoušet. Hodnotu, kterou „napíše hráč“, najdeš v poli vstup nad výstupem a můžeš ji měnit.

tajne = 42
tip = int(input("Tvůj tip: "))

if tip < tajne:
    print(f"{tip} je málo.")
elif tip > tajne:
    print(f"{tip} je moc.")
else:
    print(f"{tip} je správně!")
Výstup
Tvůj tip: 30 je málo.

Ve výstupu se text z pole vstup neopakuje, proto věta navazuje rovnou na výzvu. V terminálu by hráčovo číslo stálo na řádku a odpověď pod ním.

print("42" == 42)
tip = input("Tvůj tip: ")
print(tip < 42)
Výstup
False
Tvůj tip:
Pod kapotou · co je random zač

Modul random používá generátor Mersenne Twister (MT19937). Je rychlý a má periodu 2^19937 - 1, ale je deterministický: z 624 po sobě jdoucích 32bitových výstupů jde dopočítat celý vnitřní stav a předpovědět všechno další. Na hádanku ideální, na tokeny a hesla nikdy, tam patří modul secrets.

randint(a, b) je alias pro randrange(a, b + 1). Uvnitř se bere getrandbits(k) a příliš velké hodnoty se zahazují, takže nevzniká zkreslení jako u x % n.

Dvě věci z praxe. Dokumentace (Notes on Reproducibility) garantuje stejnou posloupnost při stejném seedu jen pro random(), takže test přibitý na konkrétní výsledek randint může po upgradu Pythonu spadnout. A funkce modulu sdílejí jednu globální instanci: stačí, aby si cizí knihovna jednou losovala, a tvoje sekvence se posune. V testech proto používej vlastní random.Random(seed).

První úkol spojuje porovnání se známým for. Tři tipy pokryjí všechny tři větve.

Úkol

Tři tipy

Tajné číslo je 42. Program přečte tři tipy a po každém vypíše jediné slovo: málo, moc, nebo trefa. Vstup je předvyplněný: 10, 90, 42.

tajne = 42

for kolo in range(3):
    tip = int(input("Tip: "))
    # doplň porovnání a výpis
Výstup

Krok 2: hádej, dokud se netrefíš

Předem nevíš, kolik tipů hráč potřebuje. To je práce pro while: opakuj, dokud platí podmínka. Princip si ukážeme na hádání slova, číselnou verzi pak napíšeš sám.

tajne_zvire = "křeček"
tip = ""
pokusy = 0

while tip != tajne_zvire:
    tip = input("Jaké zvíře? ")
    pokusy += 1
    print(f"{pokusy}. pokus: {tip}")

print("Správně!")
Výstup
Jaké zvíře? 1. pokus: pes
Jaké zvíře? 2. pokus: kočka
Jaké zvíře? 3. pokus: křeček
Správně!

Projdi si ukázku tlačítkem krokovat a uvidíš, proč cyklus skončí přesně včas. Podmínka se testuje vždy na začátku kola.

KoloTest na začátkuHráč napíšepokusy po kole
1"" != "křeček" je Truepes1
2"pes" != "křeček" je Truekočka2
3"kočka" != "křeček" je Truekřeček3
konec"křeček" != "křeček" je Falsenic, cyklus skončil3

Řádek tip = "" vypadá zbytečně, ale bez něj by první test skončil chybou NameError, protože proměnná tip by ještě neexistovala. Hodnota musí být taková, aby se první kolo spustilo.

Kvíz

Program má tajne = 42 a v cyklu while tip != tajne: čte tip = input() bez int(). Hráč napíše 42. Co se stane?

Úkol

Hádej do trefy

Tajné číslo je 34. Čti tipy, dokud hráč netrefí. Po každém tipu vypiš málo, moc, nebo trefa. Do proměnné pokusy počítej tipy a nakonec vypiš například Pokusů: 3. Ve vstupu jsou i čísla navíc: po trefě už se nesmí číst.

tajne = 34
tip = 0
pokusy = 0

# doplň cyklus while
Výstup
Pod kapotou · input mimo terminál

input() zapisuje výzvu na standardní výstup a čte jeden řádek ze standardního vstupu. Z toho plynou dvě věci, které v konzoli nevidíš. Při python hra.py > log.txt skončí výzva v souboru a hráč kouká na prázdnou obrazovku. A když je vstup zavřený (cron, CI, kontejner bez -i, konec roury), vyletí EOFError. Stejná výjimka přijde po Ctrl+D na Linuxu nebo Ctrl+Z a Enter na Windows, Ctrl+C dá KeyboardInterrupt. Interaktivní smyčku v nástroji, který může běžet bez člověka, je potřeba na obojí připravit, viz výjimky.

Krok 3: omezený počet pokusů

Hra bez rizika nudí. Přidáme limit a s ním druhý způsob, jak hra skončí: prohrou. Potřebuješ poznat, jestli cyklus skončil trefou, nebo proto, že došly pokusy. Přesně na to je else u cyklu z lekce break, continue a else: provede se, když cyklus doběhl bez break.

Stejný vzor má bankomat, proto ho ukážeme na něm. Zkus do pole vstup dát na některý řádek správný PIN 4821.

pin = "4821"

for pokus in range(1, 4):
    zadany = input(f"PIN ({pokus}/3): ")
    if zadany == pin:
        print("odemčeno")
        break
    print("špatně")
else:
    print("karta zablokována")
Výstup
PIN (1/3): špatně
PIN (2/3): špatně
PIN (3/3): špatně
karta zablokována
pokuszadanyShoda?Co se stane
11111nevypíše špatně
22222nevypíše špatně
33333nevypíše špatně
konecrange došel bez break, běží else
Úkol

Tři pokusy a dost

Předělej hru tak, aby měl hráč nejvýš LIMIT pokusů. Při trefě vypiš trefa a Pokusů: N a skonči. Když pokusy dojdou, vypiš Prohra, bylo to 34. V proměnné pokusy má na konci být počet použitých pokusů. Vstup je nachystaný tak, že hráč prohraje a čtvrté číslo se už číst nesmí.

tajne = 34
LIMIT = 3
tip = 0
pokusy = 0

while tip != tajne:
    tip = int(input("Tip: "))
    pokusy += 1
    if tip < tajne:
        print("málo")
    elif tip > tajne:
        print("moc")
    else:
        print("trefa")

print(f"Pokusů: {pokusy}")
Výstup

LIMIT je velkými písmeny, protože jde o hodnotu, která se za běhu nemění. Python to nijak nehlídá, je to dohoda mezi lidmi, kteří kód čtou.

Pod kapotou · else u cyklu a prázdný range

Čti ho jako nobreak. Přeskočí ho i return nebo výjimka, nejen break. Past je v prázdném průchodu: při LIMIT = 0 se tělo for neprovede ani jednou, else ale ano, takže hráč prohraje bez jediného tipu. Proměnná pokusy navíc vůbec nevznikne a její pozdější čtení skončí NameError. Proměnná cyklu vzniká až prvním přiřazením a po cyklu zůstává v rozsahu funkce nebo modulu, for žádný vlastní blokový rozsah nevytváří. V revizích se for/else často nahrazuje vytažením do funkce s return, kde je záměr čitelnější i pro lidi z jiných jazyků.

Krok 4: hráč píše nesmysly

Hráč napíše ahoj a int("ahoj") celou hru shodí. Vstup od člověka je potřeba nejdřív prověřit. Metoda .strip() ořízne mezery kolem textu a .isdecimal() odpoví, jestli text není prázdný a obsahuje jen číslice. Než ukázku spustíš, tipni si všech šest odpovědí.

print("42".isdecimal())
print(" 42 ".isdecimal())
print(" 42 ".strip().isdecimal())
print("-5".isdecimal())
print("4.5".isdecimal())
print("".isdecimal())
Výstup
True
False
True
False
False
False

Záporná a desetinná čísla neprojdou, protože znaménko ani tečka nejsou číslice. Ve hře od 1 do 100 to nevadí. Spolu s continue vznikne vzor „ptej se, dokud nedostaneš rozumnou odpověď“. Každá kontrola při neúspěchu skočí na začátek cyklu a k break se program dostane, až když vstup projde všemi:

while True:
    text = input("Kolik ti je? ").strip()
    if not text.isdecimal():
        print("Napiš věk číslicemi.")
        continue
    vek = int(text)
    if vek > 130:
        print("Tolik ti být nemůže.")
        continue
    break

print(f"Za rok ti bude {vek + 1}.")
Výstup
Kolik ti je? Napiš věk číslicemi.
Kolik ti je? Napiš věk číslicemi.
Kolik ti je? Tolik ti být nemůže.
Kolik ti je? Za rok ti bude 28.
KolotextJen číslice?Do 130?Co se stane
1ahojnehláška, continue skočí nahoru
2-3nehláška, continue skočí nahoru
3200anonehláška, continue skočí nahoru
427anoanobreak, cyklus končí

Ve hře je jeden háček. for si kolo odečte vždycky, i když ho continue přeskočí. Překlep by hráče stál pokus. Proto se teď vyplatí while, kde počítadlo zvýšíš ručně a až u platného tipu.

Kvíz

Cyklus for pokus in range(3): obsahuje kontrolu vstupu s continue. Hráč třikrát napíše nesmysl. Kolik platných tipů ještě může zadat?

Úkol

Hra, která přežije překlep

Tajné číslo je 25, LIMIT je 3. Před převodem na číslo zkontroluj vstup:

  • když text není číslo, vypiš Zadej číslo.
  • když je mimo 1 až 100, vypiš Jen 1 až 100.
  • ani jedno nesmí spotřebovat pokus

Zbytek hry zůstává: málo, moc, trefa, Pokusů: N, případně Prohra, bylo to 25. V proměnné pokusy má na konci být počet platných tipů. Vstup obsahuje čtyři neplatné hodnoty (jedna je prázdný řádek), pak 50 a 25.

tajne = 25
LIMIT = 3

for pokusy in range(1, LIMIT + 1):
    tip = int(input("Tip: "))
    if tip < tajne:
        print("málo")
    elif tip > tajne:
        print("moc")
    else:
        print("trefa")
        print(f"Pokusů: {pokusy}")
        break
else:
    print(f"Prohra, bylo to {tajne}.")
Výstup

Tady je celá hra pohromadě. Zkopíruj si ji, smaž random.seed a můžeš hrát.

import random

random.seed(2026)  # ve své hře tento řádek smaž
tajne = random.randint(1, 100)
LIMIT = 7
pokusy = 0

print(f"Myslím si číslo od 1 do 100. Máš {LIMIT} pokusů.")

while pokusy < LIMIT:
    text = input(f"Pokus {pokusy + 1}: ").strip()
    if not text.isdecimal():
        print("To není celé kladné číslo.")
        continue
    tip = int(text)
    if not 1 <= tip <= 100:
        print("Jen čísla od 1 do 100.")
        continue

    pokusy += 1
    if tip < tajne:
        print(f"{tip} je málo.")
    elif tip > tajne:
        print(f"{tip} je moc.")
    else:
        print(f"{tip} je správně! Počet pokusů: {pokusy}.")
        break
else:
    print(f"Došly pokusy. Myslel jsem si {tajne}.")
Výstup
Myslím si číslo od 1 do 100. Máš 7 pokusů.
Pokus 1: To není celé kladné číslo.
Pokus 1: 50 je moc.
Pokus 2: 25 je moc.
Pokus 3: Jen čísla od 1 do 100.
Pokus 3: 12 je málo.
Pokus 4: 18 je moc.
Pokus 5: 15 je málo.
Pokus 6: 16 je správně! Počet pokusů: 6.
Pod kapotou · isdigit, isdecimal a co všechno bere int

Běžně vídaná kontrola .isdigit() je tu chyba: "²".isdigit() vrací True, ale int("²") vyhodí ValueError. isdecimal() pustí jen znaky, které jsou desítkovými číslicemi v Unicode, a ty int umí. Patří mezi ně i arabsko-indické ٤٢ nebo plnošířkové 12, takže hra je přijme jako 42 a 12.

python
"²".isdigit(), "²".isdecimal()     # (True, False)
"½".isnumeric(), "½".isdigit()     # (True, False)
int("٤٢"), int("12")              # (42, 12)
int(" 42\n"), int("+7"), int("1_000")  # (42, 7, 1000), isdecimal by je odmítl
int("9" * 5000)                    # ValueError: limit 4300 číslic

Poslední řádek je skutečná díra v naší hře: isdecimal projde a int spadne. Limit sys.get_int_max_str_digits() přibyl v Pythonu 3.11 a v opravných vydáních starších řad jako ochrana před DoS (CVE-2020-10735), převod dlouhého řetězce totiž trval kvadraticky dlouho. Python 3.12 má pro obří čísla rychlejší algoritmus v interním modulu _pylong, limit ale platí dál. Kontrola předem tak nikdy nepokryje vše, co pokrývá samotný převod. V produkci se proto píše try: int(text) s except ValueError (styl EAFP, „snazší je požádat o odpuštění“). K tomu se dostaneš v lekci o výjimkách.

Krok 5: role se otočí

Teď si číslo myslíš ty a hádá počítač. Mohl by zkoušet 1, 2, 3 a tak dál, ale to může trvat sto pokusů. Existuje mnohem lepší strategie.

Lidsky řečeno

Hledáš v tlusté knize stranu 412. Nezačneš listovat od první. Otevřeš ji zhruba uprostřed, podíváš se na číslo a půlku knihy rázem nemusíš řešit. Pak totéž se zbytkem. Tomu se říká půlení intervalu, anglicky binary search.

Počítač si drží dvě meze: dolni a horni. Tajné číslo je vždy někde mezi nimi. Tipne prostředek a podle odpovědi jednu polovinu zahodí. V ukázce odpovídá program sám sobě, abys viděl celý průběh.

tajne = 73
dolni = 1
horni = 100
pokusy = 0

while True:
    tip = (dolni + horni) // 2
    pokusy += 1
    print(f"Zkouším {tip}")
    if tip == tajne:
        break
    elif tip < tajne:
        dolni = tip + 1
    else:
        horni = tip - 1

print(f"Mám to na {pokusy}. pokus.")
Výstup
Zkouším 50
Zkouším 75
Zkouším 62
Zkouším 68
Zkouším 71
Zkouším 73
Mám to na 6. pokus.
PokusdolnihornitipOdpověďZměna
1110050málodolni = 51
25110075mochorni = 74
3517462málodolni = 63
4637468málodolni = 69
5697471málodolni = 72
6727473trefabreak

Operátor // je celočíselné dělení, takže tip zůstane celé číslo. Sleduj, jak se rozsah po každém řádku zmenšuje.

Stejné půlení na seřazeném seznamu a vedle něj procházení od začátku. Měň hledané číslo i délku seznamu a porovnej počet kroků.

Doplň

Doplň půlení

Doplň tři chybějící kousky, aby program našel tajné číslo a vypsal ho.

Úkol

Hádá počítač

Napiš verzi, kde odpovídá člověk. V každém kole spočítej tip = (dolni + horni) // 2, zvyš pokusy, vypiš Tipuji 50 (s aktuálním číslem) a přečti odpověď: v znamená „moje číslo je větší než tvůj tip“, m „menší“, t „trefil ses“. Po t skonči. Vstup odpovídá hráči, který si myslí 33.

dolni = 1
horni = 100
pokusy = 0

# doplň cyklus
Výstup
Kvíz

Hráč lže a na všechno odpovídá v. Co se časem stane s mezemi?

Krok 6: kolik pokusů je férových

V celé hře je LIMIT = 7. Není to náhoda. Místo dohadů vyzkoušej všech sto možných tajných čísel: vnější for je postupně nastavuje a vnitřní while každé uhádne.

MEZ = 100
nejhur = 0
soucet = 0
do_sesti = 0

for tajne in range(1, MEZ + 1):
    dolni = 1
    horni = MEZ
    pokusy = 0
    while True:
        tip = (dolni + horni) // 2
        pokusy += 1
        if tip == tajne:
            break
        elif tip < tajne:
            dolni = tip + 1
        else:
            horni = tip - 1
    soucet += pokusy
    if pokusy > nejhur:
        nejhur = pokusy
    if pokusy <= 6:
        do_sesti += 1

print("Nejhorší případ:", nejhur)
print("Průměr:", soucet / MEZ)
print("Do šesti pokusů:", do_sesti)
Výstup
Nejhorší případ: 7
Průměr: 5.8
Do šesti pokusů: 63

Půlením se tedy každé číslo najde nejvýš na sedmý pokus. Se sedmi pokusy má hráč, který půlí, výhru jistou, s šesti by i dokonalá strategie stačila jen na 63 čísel ze 100. Sedm je nejnižší limit, který je ještě spravedlivý. Tabulka ukazuje proč: špatný tip nechá v nejhorším případě zhruba polovinu kandidátů.

PokusKandidátů před tipem (nejvýš)
1100
250
325
412
56
63
71

Hezké je, jak pomalu počet pokusů roste. Dvojnásobný rozsah znamená jediný pokus navíc.

Kvíz

Hra se rozšíří na čísla od 1 do 200. Kolik pokusů potřebuje půlení v nejhorším případě?

Najdi chybu

Proč vyšlo 580?

Program má zjistit nejhorší počet pokusů pro čísla od 1 do 100, tedy 7. Vypíše ale 580. Který řádek je špatně?

Úkol

Kolik čísel je nejhorších

Uprav program pro čísla od 1 do 1000. V proměnné nejhur má být nejvyšší potřebný počet pokusů a v proměnné kolik počet tajných čísel, která přesně tolik pokusů vyžadují.

MEZ = 100
nejhur = 0

for tajne in range(1, MEZ + 1):
    dolni = 1
    horni = MEZ
    pokusy = 0
    while True:
        tip = (dolni + horni) // 2
        pokusy += 1
        if tip == tajne:
            break
        elif tip < tajne:
            dolni = tip + 1
        else:
            horni = tip - 1
    if pokusy > nejhur:
        nejhur = pokusy

print(nejhur)
Výstup
Pod kapotou · binary search bez iluzí

Nejhorší případ pro n kandidátů je floor(log2(n)) + 1, v Pythonu přesně a bez plovoucí čárky n.bit_length(): (100).bit_length() je 7, (1000).bit_length() je 10. Složitost je O(log n), více v lekci o rychlosti a volbě struktury. Každý tip je uzel binárního stromu, který má na hloubce d nejvýš 2^(d-1) uzlů. Proto do šesti pokusů vyjde nejvýš 63 čísel a součet 580 pokusů (průměr 5,8) je optimum: horní patra stromu jsou plná a pro rovnoměrně losované číslo nejde mít lepší strategii.

Správnost drží invariant: tajné číslo je vždy v [dolni, horni] a interval se v každém kole ostře zmenšuje. Většina chyb v binary search je porušení jedné z těchto dvou vět, typicky právě dolni = tip.

Výpočet (dolni + horni) // 2 je v Pythonu bezpečný, protože int nepřeteče. Ve Javě nebo C přetéct může, chybu tohoto typu měla i standardní knihovna Javy a Joshua Bloch o ní v roce 2006 napsal známý článek; odtud zápis low + (high - low) / 2. V Pythonu nepiš vlastní hledání v seřazených datech, použij modul bisect. Pozor, bisect_left(a, x) vrací místo pro vložení, ne nález, takže výsledek i ještě ověř: i < len(a) and a[i] == x. Od verze 3.10 bere i parametr key. Stejná myšlenka hledá commit, který zavedl chybu: git bisect.