Úlohy na procvičení

Fibonacci

Napište funkci pro výpočet \(n\)-tého prvku Fibonacciho posloupnosti (definici si můžete připomenout na Wikipedii):

Zkuste navrhnou 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.

Hanojské věže

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. Spočítejte, za jak dlouho k tomu může dojít.

Jinými slovy, spočítejte kolik tahů potřebuje náš (rekurzivní) algoritmus na přemístění \(n\) kotoučů?

Algoritmus z přednášky:

def hanoj(pocet, odkud, kam, rezervni):
    if pocet == 1:
        print(f"Presuň 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)

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ě.

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\).