Table of Contents

Vejce

Určete nejvyšší patro, z něhož můžete vejce ještě hodit, aby se nerozbilo!

Prerekvizity Základní znalost Pythonu
Náročnost přemýšlení Střední
Náročnost programování Střední

Úloha

Chceme vytvořit algoritmus pro určení pevnosti daného typu vajec. Všechna vejce mají stejnou pevnost. Pevnost vajec měříme tak, že je pouštíme z paneláku z různých pater. Pevnost vejce je definována jako číslo nejvyššího patra, z něhož můžete vejce pustit, aby se ještě nerozbilo. Pokud je P pevnost vejce, pak pustíte-li ho z patra číslo P nebo nižšího, vejce se nerozbije (a můžete ho použít pro další test); pustíte-li ho z patra P+1 nebo vyššího, vejce se rozbije (a znovu ho už použít nemůžete). Pokud se vejce rozbije už při pádu z prvního patra, je P = 0. Pokud má panelák N pater, je nejvyšší možná pevnost vajec P = N.

Vstupem algoritmu by měla být výška paneláku (tj. největší pevnost vejce, kterou můžete “změřit”) a počet vajec, která máte k dispozici pro experimenty (a nevadí nám, že se při experimentech rozbijí). S daným počtem vajec by měl algoritmus určit pevnost vajec co nejrychleji, tj. s co nejmenším počtem hodů vejce z paneláku.

Zkuste si rozmyslet:

Specifikace

Vaším úkolem je naprogramovat strategii experimentu, tedy algoritmus, který bude postupně volit patra, z nichž chcete pouštět vejce, v závislosti na tom, zda vejce předchozí test “přežilo” nebo ne.

V modulu solver.py vytvořte funkci determine_egg_strength(), s následujícími vstupy a výstupy:

Vstupy n_floors Celé kladné číslo. Výška (počet pater) paneláku neboli maximální měřitelná pevnost vejce.
n_eggs Celé kladné číslo. Počet vajec, která máte k dispozici. Pokud se dostanete do situace, že pevnost vejce ještě neznáte a nemáte už žádné vejce, je to špatně.
egg_survives_floor Funkce. Simuluje jeden test, tedy upuštění vejce z nějakého patra. Vrací True, resp. False, pokud vejce pád z daného patra přežilo, resp. nepřežilo.
Výstupy strength Celé číslo. Pevnost vejce.

Příklad

Funkce egg_survives_floor() simuluje upuštění vejce z jistého patra. Může být definována např. takto: 

def egg_survives_floor(floor):
    return floor <= 18

Tato funkce odpovídá tomu, že pevnost vejce je 18. Váš algoritmus samozřejmě toto číslo nebude znát, může jen volat funkci egg_survives_floor a zjišťovat tak, zda vejce pád přežilo nebo ne.

Asi nejjednodušším algoritmem, který danou úlohu řeší, je postup, kdy budete postupovat od nejnižšího patra k nejvyššímu, dokud se vejce nerozbije. Takové řešení může vypadat třeba takto: 

def determine_egg_strength(n_floors, n_eggs, egg_survives_floor):
    for floor in range(n_floors):
        if not egg_survives_floor(floor+1):
            return floor
    return n_floors

Pokud tuto funkci zavoláme s výše definovanou funkcí egg_survives_floor(), dostaneme očekávaný výsledek: 

>>> determine_egg_strength(30, 10, egg_survives_floor)
18

Toto řešení je validní, vždy najde správnou pevnost vejce a potřebuje vždy jen jedno vejce. Zároveň ale tato strategie není nejlepší, protože nevyužila všechna vejce, které měla k dispozici pro experiment. Lze postupovat mnohem chytřeji!

Hodnocení

Příklad hodnocení triviálního algoritmu: