Ga naar hoofdinhoud

Torens van Hanoi op tafel

Verplaats een toren van schijven met één beperking, en ontdek al spelend de formule en het recept dat je later in code giet. Een potlood per tweetal, 35 minuten: de voorkant vindt het patroon, de achterkant maakt er een recept van dat je zo in Python overtypt.

Wat je nodig hebt​

  • Vijf "schijven" van verschillende grootte per tweetal: muntjes, of papiertjes genummerd 1 (kleinste) t/m 5 (grootste).
  • Drie vakken naast elkaar op tafel, gemarkeerd A, B en C (drie briefjes volstaan).

De spelregels​

Start: alle schijven op vak A, grootste onderop, kleinste bovenop. Doel: de hele toren naar vak C.

  1. Verplaats één schijf per beurt, altijd de bovenste van een stapel.
  2. Een schijf mag nooit op een kleinere schijf liggen.

Werkvorm 1 — tel de zetten​

Los de puzzel op met 1 schijf, dan 2, dan 3, dan 4. Eén leerling verplaatst, de ander telt. Zoek per toren het kleinste aantal; opnieuw beginnen mag.

SchijvenMinimaal aantal zetten
1
2
3
4
5(voorspel eerst, speel dan)

Werkvorm 2 — het patroon​

  1. Kijk naar je rij getallen. Hoe kom je van elk getal bij het volgende? Regel: ____________________
  2. Voorspel met die regel het aantal voor 5 schijven en controleer door te spelen. Klopte het?

Werkvorm 3 — de zeven zetten bij 3 schijven​

Speel de kortste oplossing met 3 schijven nog eens, langzaam, en schrijf elke zet op: welke schijf, van welk vak, naar welk vak.

ZetSchijfVanNaar
1
2
3
4
5
6
7
  1. Bij welke zet verhuist de grootste schijf, nummer 3? Omcirkel die rij.
  2. Waar liggen schijf 1 en 2 op dat moment? Wat hebben de zetten vóór de omcirkelde rij dus samen gedaan, en via welk vak?
  3. Wat doen de zetten ná de omcirkelde rij samen, en via welk vak?

Werkvorm 4 — 4 schijven in drie fasen​

Bij 3 schijven zag je drie fasen: een toren van 2 opzij, de grootste over, de toren van 2 er weer bovenop. Speel met 4 schijven en vul de fasen in. Let op de vakken: ze wisselen van rol.

  1. Fase 1: een toren van ___ schijven van vak ___ naar vak ___, via vak ___. Dat kost ___ zetten.
  2. Fase 2: schijf ___ van vak ___ naar vak ___. Dat kost ___ zet.
  3. Fase 3: een toren van ___ schijven van vak ___ naar vak ___, via vak ___. Dat kost ___ zetten.
  4. Samen: ___ + ___ + ___ = ___ zetten. Klopt dat met werkvorm 1?

Werkvorm 5 — schrijf het als aanroep​

In de les heet de functie hanoi(n, bron, doel, hulp): verplaats n schijven van bron naar doel, met hulp als parkeerplek. Schrijf de drie fasen zo op.

  1. hanoi(4, A, C, B) = hanoi(___, ___, ___, ___) + schijf 4 van ___ naar ___ + hanoi(___, ___, ___, ___)
  2. Hetzelfde voor 3 schijven, met de fasen uit werkvorm 3: hanoi(3, A, C, B) = hanoi(___, ___, ___, ___) + schijf 3 van ___ naar ___ + hanoi(___, ___, ___, ___)
  3. Nu voor elke n, met de namen in plaats van de letters: hanoi(n, bron, doel, hulp) = hanoi(n − 1, ______, ______, ______)
    • schijf n van ______ naar ______ + hanoi(n − 1, ______, ______, ______)

Bespreek na​

  • De regel van werkvorm 5 roept zichzelf aan, met een toren van één schijf minder. Waar houdt dat op?
  • Elke schijf erbij verdubbelt het werk. Volgens een legende verplaatsen monniken 64 schijven, één zet per seconde. Schat: duurt dat minuten, jaren, of langer dan het heelal oud is?

Voor wie klaar is​

  • De kleinste schijf: om de hoeveel zetten beweegt hij, en welke kant op?
  • Bij welke zet gaat de grootste schijf naar C? Tel bij 2, 3 en 4 schijven.
Antwoorden (voor de docent; print als losse laatste pagina)

Op het scherm staat dit dicht, zodat een leerling die deze pagina opent de oplossing niet ziet; op papier is het de losse laatste pagina.

Werkvorm 1: 1, 3, 7, 15, en 5 schijven kost 31 zetten.

Werkvorm 2: elk getal is het dubbele van het vorige plus 1 (3 = 2·1 + 1, 7 = 2·3 + 1, …). Dat is de rij 2ⁿ − 1.

Werkvorm 3: de zeven zetten, met de grootste schijf in het midden.

ZetSchijfVanNaar
11AC
22AB
31CB
43AC
51BA
62BC
71AC

Bij zet 4 liggen schijf 1 en 2 samen op B: de zetten 1 tot en met 3 hebben een toren van 2 van A naar B gebracht, via C. De zetten 5 tot en met 7 brengen die toren van B naar C, via A.

Werkvorm 4: fase 1 is een toren van 3 van A naar B via C, 7 zetten; fase 2 is schijf 4 van A naar C, 1 zet; fase 3 is een toren van 3 van B naar C via A, 7 zetten. Samen 7 + 1 + 7 = 15. Zo telt het door: 3 + 1 + 3 = 7, 7 + 1 + 7 = 15, 15 + 1 + 15 = 31, dezelfde rij als werkvorm 1.

Werkvorm 5:

  1. hanoi(4, A, C, B) = hanoi(3, A, B, C) + schijf 4 van A naar C + hanoi(3, B, C, A)
  2. hanoi(3, A, C, B) = hanoi(2, A, B, C) + schijf 3 van A naar C + hanoi(2, B, C, A)
  3. hanoi(n, bron, doel, hulp) = hanoi(n − 1, bron, hulp, doel) + schijf n van bron naar doel + hanoi(n − 1, hulp, doel, bron)

In fase 1 is doel even de parkeerplek, in fase 3 is bron dat. Dit zijn precies de drie regels van bouwsteen 3 in de les.

Bespreek na: het houdt op bij een toren van nul schijven: die verplaats je met nul zetten. Stoppen bij één schijf kan ook, maar in de les kies je nul: dan telt de recursie vanzelf af tot er niets meer te doen is. Voor de monniken: 2⁶⁴ − 1 zetten is ruim 18 triljoen. Met één zet per seconde is dat zo'n 580 miljard jaar, ruim veertig keer de leeftijd van het heelal.

Voor wie klaar is: de kleinste schijf beweegt om de andere zet, en altijd dezelfde kant op (bij een even aantal schijven met de klok mee, bij een oneven aantal ertegenin). De grootste schijf gaat precies in het midden: bij 2, 3 en 4 schijven is dat zet 2, 4 en 8 van de 3, 7 en 15.

Voor de docent​

Doel: je leerlingen vinden de rij 2ⁿ − 1 en het recursieve recept zelf, en schrijven op de achterkant de aanroep op die ze in bouwsteen 3 in Python zetten. Reken op 35 minuten; de voorkant is het patroon, de achterkant het recept. De fout die het vaakst voorkomt: een tweetal telt een reeks die niet de kortste is en schrijft 9 op bij 3 schijven. Laat ze opnieuw beginnen, met de vraag waar de grootste schijf naartoe moet en wat daarvoor eerst weg moet. Bij werkvorm 4 en 5 is de valkuil het hulpvak: in fase 1 is dat C, in fase 3 is dat A.

Verder op de site​