12.3 Stellingen — eerst voorspellen
Leerdoel: je toetst je beeld van het probleem en van recursie vóórdat je gaat bouwen. Nu je het spel gespeeld en de patronen gezien hebt: denk eerst zelf na, klik dan open.
Stelling 1
Voor 4 schijven heb je 15 zetten nodig.
Waar of niet waar?
Waar. Het patroon is 2ⁿ − 1: voor 1, 2, 3, 4 schijven →
1, 3, 7, 15. Elke schijf erbij verdubbelt (ongeveer) het werk.
Stelling 2
Er bestaat een slimmere aanpak die het met minder dan
2ⁿ − 1zetten doet.
Waar of niet waar?
Niet waar. 2ⁿ − 1 is bewijsbaar het minimum met drie palen. De
grootste schijf moet een keer naar doel, en daarvóór moeten alle n − 1
kleinere schijven opzij — en daarna er weer bovenop. Dat geeft precies
2 · (2ⁿ⁻¹ − 1) + 1 = 2ⁿ − 1.
Stelling 3
Om
nschijven te verplaatsen los je twee keer een probleem metn − 1schijven op.
Waar of niet waar?
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 gewoon, alleen wat langzamer.
Waar of niet waar?
Niet waar. Zonder basisgeval blijft de functie zichzelf aanroepen met
steeds kleinere n, ook onder nul, en stopt nooit. Python kapt dat af met
een RecursionError. Het basisgeval (n == 0) is wat de recursie laat
stoppen.
Stelling 5
Bij het verplaatsen van 3 schijven gaat de grootste schijf precies één keer van paal.
Waar of niet waar?
Waar. De grootste schijf hoeft maar één keer te bewegen: rechtstreeks van bron naar doel, precies in het midden (bij 3 schijven is dat de 4ᵉ van de 7 zetten). Alle andere zetten gaan over de kleinere schijven.
Klaar met voorspellen? Tijd om te bouwen.
Door naar stap 4: één zet →.