Cheatsheet — Torens van Hanoi

Snelle referentie. Klap open wat je nodig hebt.

De drie regels

Wat mag wel en niet?

1. Eén schijf per keer verplaatsen.
2. Alleen de bovenste schijf van een paal.
3. Nooit een grotere schijf op een kleinere.

Doel: verplaats de hele stapel van de bron-paal naar de doel-paal.

De oplossing

De functie die de zetten teruggeeft

def hanoi(n, bron, doel, hulp):
    if n == 0:
        return []
    zetten = []
    zetten += hanoi(n - 1, bron, hulp, doel)   # n-1 naar de hulp-paal
    zetten.append((bron, doel))                 # grootste schijf naar doel
    zetten += hanoi(n - 1, hulp, doel, bron)   # n-1 op hun plek
    return zetten

Alleen het aantal zetten

def tel_zetten(n):
    if n == 0:
        return 0
    return 2 * tel_zetten(n - 1) + 1

Het recursieve recept

Drie stappen + basisgeval

Om n schijven van bron naar doel te verplaatsen:

1. verplaats n − 1 schijven van bron naar hulp;
2. verplaats de grootste schijf van bron naar doel;
3. verplaats n − 1 schijven van hulp naar doel.

Basisgeval: bij n == 0 is er niets te doen. Zonder basisgeval stopt de recursie nooit (RecursionError).

In stap 1 en 3 wisselen hulp en doel van plek in de recursieve aanroep.

Aantal zetten

Waarom 2ⁿ − 1?

Elke oplossing doet twee keer een kleiner probleem plus één losse zet:

T(n) = 2 · T(n − 1) + 1      met T(0) = 0

Uitgerold tot het basisgeval:

T(n) = 2·T(n−1) + 1
     = 4·T(n−2) + 3
     = 8·T(n−3) + 7
     = …
     = 2ⁿ·T(0) + (2ⁿ − 1)  =  2ⁿ − 1

Voor 1, 2, 3, 4, ... schijven dus 1, 3, 7, 15, ... Elke schijf erbij verdubbelt het werk, ongeveer. Dit is het minimum; met drie palen kan het niet sneller.

Veelgemaakte fouten

Top-3 fouten

1. Basisgeval vergeten → RecursionError.
2. hulp en doel verwisseld in de recursieve call → de test voor 2 schijven faalt, de grootste schijf komt bovenop de kleinste.
3. append in plaats van += bij de recursieve aanroep → een lijst ín de lijst.

Begrippen

Recursie, basisgeval, recurrence

• Recursie: een functie die zichzelf aanroept op een kleiner stuk van het probleem.
• Basisgeval: het kleinste geval, dat je direct beantwoordt zonder nieuwe aanroep. Het zorgt dat de recursie stopt.
• Recurrence: een formule die de kosten van n uitdrukt in de kosten van een kleiner probleem, hier T(n) = 2·T(n−1)+1.