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:

  • Jak byste postupovali, kdybyste měli k dispozici jediné vejce?
  • Jak byste postupovali, kdybyste měli k dispozici vajec, kolik chcete?
  • Jak byste postupovali, kdybyste měli k dispozici 2, 3, … vejce?

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í

  • Váš algoritmus bude otestován na sadě testovacích případů.
  • Jeden testovací případ je dvojice hodnot n_floors, n_eggs.
  • Pokud dojde při kterémkoli testu k chybě, získáte 0 bodů.
  • Pro každý testovací případ bude váš algoritmus otestován pro všechny možné pevnosti vajec 0, …, n_floors, a zaznamená se dílčí skóre - nejvyšší počet testů, který jste potřebovali k určení pevnosti vejce.
  • Skóre vaší strategie je pak součet dílčích skóre přes všechny testovací případy.
  • Vaše skóre se pak porovná se skóre triviálního algoritmu výše a optimálního algoritmu a na základě toho bude určen poměrný počet bodů.

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

  • Předpokládejme, že sada testovacích případů je ( (5, 1), (10, 2), (20, 3) ).
  • Výše uvedený triviální algoritmus
    • pro testovací případ (5,1) a pro pevnost vejce 1 potřebuje 1 hod, pro pevnost vejce 2 potřebuje 2 hody, … pro pevnost vejce 5 potřebuje 5 hodů, takže jeho dílčí skóre je 5,
    • pro testovací případ (10, 2) a pro pevnost vejce 1 potřebuje 1 hod, … pro pevnost vejce 10 potřebuje 10 hodů, takže jeho dílčí skóre je 10,
    • pro testovací případ (20, 3) … má dílčí skóre 20.
  • Celkové skóre vašeho algoritmu tak je 20 + 10 + 5 = 35.
 
ulohy/vejce/start.txt · Last modified: 2022/08/15 11:47 by xposik