Op zoek naar patronen

Leerdoel: je ontdekt door te spelen en te tellen twee patronen: hoeveel zetten je minimaal nodig hebt, en hoe je elke toren aanpakt. Dat tweede patroon wordt straks de code.

Patroon 1 — hoeveel zetten?

Speel het spel met 1, 2, 3, 4 en 5 schijven en zoek telkens het kleinste aantal zetten. Vul de tabel in, in je hoofd of op papier:

Schijven	Minimaal aantal zetten
1	?
2	?
3	?
4	?
5	?

Speel zelf

Klik een paal om de bovenste schijf op te pakken, klik dan een andere paal om hem neer te leggen. Verplaats de hele toren naar paal C.

0zetten

Aantal schijven:

Kies een paal om een schijf op te pakken.

Wat heb jij gevonden?

Schijven	Minimaal aantal zetten
1	1
2	3
3	7
4	15
5	31

Zie je het patroon?

Kijk naar de rij 1, 3, 7, 15, 31. Hoe kom je van het ene getal bij het volgende?

Hint

Elk getal is het dubbele van het vorige, plus 1: 3 = 2·1 + 1, 7 = 2·3 + 1, 15 = 2·7 + 1, en zo verder.

De formule

Elke schijf erbij verdubbelt het werk, ongeveer. De rij 1, 3, 7, 15, 31 is precies 2ⁿ − 1.

Voor 6 schijven is dat 2⁶ − 1 = 63, en voor de 64 schijven van de monniken 2⁶⁴ − 1: meer dan 18 triljoen zetten. Geen wonder dat het even duurt.

Patroon 2 — hoe pak je het aan?

Het aantal zetten is leuk om te weten, maar dit tweede patroon heb je nodig om te programmeren. Speel nog eens met 3 of 4 schijven en let op de grootste schijf, die onderop ligt. Die moet uiteindelijk naar paal C, en dat kan pas als alle schijven erbovenop weg zijn. Waar moeten die naartoe voordat je de grootste kunt verplaatsen? En wat doe je met ze nadat de grootste op C ligt?

Wat moet er telkens gebeuren?

Om de grootste schijf van A naar C te krijgen:

1. verplaats eerst alle schijven erbovenop (de bovenste n − 1) naar de hulp-paal B;
2. verplaats de grootste schijf van A naar C;
3. verplaats die n − 1 schijven van B bovenop de grootste, naar C.

Stap 1 en stap 3 zijn zelf weer Torens van Hanoi, met één schijf minder. Je lost het probleem op met een kleinere versie van zichzelf.

Het recept

Wat je net ontdekte is een recursief recept. Om n schijven van bron naar doel te verplaatsen, met hulp als derde paal:

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.

Bij 0 schijven hoef je niets te doen, en daar stopt het. Dat heet het basisgeval; zonder basisgeval zou het recept eindeloos naar zichzelf blijven verwijzen.

De twee patronen kloppen met elkaar

Het recept verklaart ook het aantal zetten: je doet twee keer een probleem met n − 1 schijven, plus die ene zet voor de grootste:

T(n) = 2 · T(n−1) + 1     →     T(n) = 2ⁿ − 1

Waarom daar precies 2ⁿ − 1 uitkomt, reken je na bij uitrollen tot het basisgeval, als de code staat.

info

Deze patronen kun je ook zonder scherm ontdekken, met muntjes op tafel: print Torens van Hanoi op tafel.

Door naar stellingen →.