Úlohy na procvičení

Fibonacci

Napište funkci pro výpočet \(n\)-tého prvku Fibonacciho posloupnosti: \[ F_n= \begin{cases} 1 & \text{pro}\ n=1 \text{ a } n=2, \\ F_{n-1} + F_{n-2} & \text{jinak} \end{cases} \] Prvních několik prvků Fibonacciho posloupnosti je tedy \(1, 1, 2, 3, 5, 8, 13, \dots\)

Zkuste navrhnout dvě různá řešení:

  • rekurzivní,
  • iterativní (bez rekurze).

Společně si pak porovnáme jejich efektivitu.

🦉 Bonus: Cache pro mezivýsledky

U rekurzivního řešení si ukládejte už spočítané hodnoty, abyste je nemuseli počítat znovu.

Generování permutací

Napište funkci, která dostane seznam a vygeneruje všechny permutace prvků v tomto seznamu. Předpokládejte, že v zadaném seznamu se prvky neopakují.

Například volání permutations([1, 2, 3]) vrátí 6 možných permutací: [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]. Je na vás, jestli funkce bude vracet seznam všech permutací (tedy seznam seznamů) nebo ji napíšete jako generátor.

Generování podmnožin

Napište funkci, která dostane seznam a vygeneruje všechny podmnožiny tohoto seznamu. Předpokládejte, že v zadaném seznamu se prvky neopakují.

Například volání subsets([0, 1]) vrátí 4 možné podmnožiny: [], [0], [1], [0, 1]. Je na vás, jestli funkce bude vracet seznam všech podmnožin (tedy seznam seznamů) nebo ji napíšete jako generátor.

Nápověda

Uvědomte si, že podmnožina vznikne tak, že do ní každý prvek z původní množiny buď dáme, nebo nedáme. Podmnožiny seznamu s \(n\) prvky tedy odpovídají všem \(n\)-prvkovým posloupnostem True a False, tedy i všem \(n\)-ciferným číslům ve dvojkové soustavě (nevadí nuly na začátku).

🦉 Bonus: Rostoucí posloupnosti

Rozmyslete si, jak se dá generování podmnožin využít pro generování všech rostoucích posloupností tvořených z čísel \(1, 2, \dots, N\).

Hanojské věže

Mějme tři věže a \(n\) kotoučů různých velikostí, které jsou na první věži naskládány na sebe od největšího (dole) po nejmenší (nahoře). Cílem je přemístit všechny kotouče z první věže na třetí věž podle následujících pravidel:

  • najednou lze přesunout pouze jeden kotouč (vždy ho beru z vrchu nějaké věže a položím ho na vrch jiné věže),
  • větší kotouč nesmí být nikdy položen na menší kotouč.

Pro řešení této úlohy se dá použít následující rekurzivní algoritmus:

def hanoj(pocet, odkud, kam, rezervni):
    """Přesune `pocet` kotoučů z věže `odkud` na věž `kam` (přitom lze odkládat na věž `rezervni`)."""
    if pocet == 1:
        print(f"Přesuň kotouč z věže {odkud} na věž {kam}")
    else:
        hanoj(pocet - 1, odkud, rezervni, kam)
        hanoj(1, odkud, kam, rezervni)
        hanoj(pocet - 1, rezervni, kam, odkud)

Rozmyslete si, že tento algoritmus funguje a vyřeší úlohu.

Následně spočítejte, kolik tahů potřebuje náš algoritmus na přemístění \(n\) kotoučů.

Dle legendy existuje v Asii chrám, v němž každý den v poledne mniši slavnostně přemístí jeden z 64 zlatých kotoučů. Jakmile bude přemístěna celá “věž”, nastane konec světa. Za jak dlouho k tomu může dojít?

Nápověda

Označte počet tahů pro \(n\) kotoučů třeba \(T(n)\). To odpovídá časové složitosti volání funkce hanoj(n, ...). Rozmyslete si, kolikrát rekurzivně voláte funkci hanoj a s jakým počtem kotoučů. Vztah pro \(T(n)\) se dá na základě toho vyjádřit jako součet několika hodnot \(T\) pro čísla menší než \(n\). Samozřejmě nesmíte zapomenout počítat hodnotu \(T(1)\) zvlášť (ukončení rekurze).

Pak můžete zkusit dopočítat hodnotu \(T(n)\) pro malá \(n\) a zkusit odhadnout, jak to vyjde obecně.