Stellingen — eerst voorspellen

Leerdoel: je toetst je beeld van het probleem en van recursie voordat je gaat bouwen. Elke stelling is waar of niet waar. Beslis eerst zelf, klik dan open.

Stelling 1

Voor 4 schijven heb je 15 zetten nodig.

Antwoord

Waar. Het patroon is 2ⁿ − 1: voor 1, 2, 3 en 4 schijven is dat 1, 3, 7 en 15. Elke schijf erbij verdubbelt het werk, ongeveer.

Stelling 2

Er bestaat een slimmere aanpak die het met minder dan 2ⁿ − 1 zetten doet.

Antwoord

Niet waar. Met drie palen is 2ⁿ − 1 het minimum, en dat is te bewijzen. De grootste schijf moet één keer naar doel; daarvóór moeten alle n − 1 kleinere schijven opzij, en daarna moeten ze er weer bovenop. Dat is precies 2 · (2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1.

Stelling 3

Om n schijven te verplaatsen los je twee keer een probleem met n − 1 schijven op.

Antwoord

Waar. Eerst verplaats je n − 1 schijven naar de hulp-paal, dan de grootste schijf, dan diezelfde n − 1 schijven naar doel. Twee keer een kleiner Hanoi-probleem, met één losse zet ertussen.

Stelling 4

Een recursieve functie zonder basisgeval werkt ook, alleen wat langzamer.

Antwoord

Niet waar. Zonder basisgeval blijft de functie zichzelf aanroepen met een steeds kleinere n, ook onder nul, en stopt ze nooit. Python kapt dat af met een RecursionError. Het basisgeval, het kleinste probleem dat je direct kunt beantwoorden, is wat de recursie laat stoppen.

Stelling 5

Bij het verplaatsen van 3 schijven gaat de grootste schijf precies één keer van paal.

Antwoord

Waar. De grootste schijf hoeft maar één keer te bewegen: rechtstreeks van bron naar doel. Alle andere zetten gaan over de kleinere schijven. Wanneer die ene zet precies valt, zoek je uit bij zelf bouwen.

Klaar met voorspellen? Dan ga je bouwen.

Door naar één zet →.