Recursie: De Torens van Hanoi David Joseph
Koen Mahieu
Recursie: De Torens van Hanoi David Joseph
Koen Mahieu
Recursie?
Pseudocode ! Een recursieve procedure roept zichzelf telkens op om zijn resultaat te bekomen
vb. Iemand is een Jood
zijn of haar moeder een Jood is
zij de vrouw is van Abraham
to isJood:persoon
IF (persoon = Abrahams’ vrouw)
[PRINT ( SE :persoon is joods) STOP]
isJood :moeder_van_persoon
end
Recursie
roept op oplossingsprocedure (argument n - 1) roept op oplossingsprocedure (argument n - 2) …. stopconditie keert terug keert terug keert terug bepaalde recursieve eigenschap van het probleem maakt probleem plots veel simpeler
moeilijkste taak: deze eigenschap ontdekken
oplossingsprocedure (argument n)
De Torens van Hanoi (historiek)
Speldoos : “ De Toren van Hanoi” Uitgevonden door een Franse wiskundige, Edouard Lucas en als spel op de markt gebracht in 1883
De Torens van Hanoi (historiek)
Inspiratie door een mythe over een hindoetempel met een koepel op 3 diamanten zuilen
Op 1 zuil : 64 gouden schijven van steeds kleinere diameter
Schijven verplaatsen volgens bepaalde regels
Hanoi
Spel
verplaats alle schijven van 1ste zuil naar de 2de met behulp van de 3de
Regels
(1) Slecht 1 schijf per keer verplaatsen
(2) Geen grotere schijf boven een kleinere
Hanoi Test
Probeer zelf het probleem op te lossen met 4 à 5 schijven.
http://www.hallofscience.nl/old/kidscorner/nl/cool/Towers/Tower.htm
Recursieve eigenschap van Hanoi ?
Oplossing :
stap voor stap:
http://chemeng.p.lodz.pl/zylla/games/hanoi6e.html
automatisch:
http://schoolweb.gemeenschapsonderwijs.be/bs/kruibeke/reyn/spel/Hanoi/Hanoi.html
Recursieve eigenschap van Hanoi ?
bron doel hulp Hoe kunnen we dit bereiken? Welke van deze 4 schijven is de belangrijkste om eerst op de doel staaf te verplaatsen ? (vergeet even de regels)
Recursieve stap
bron doel hulp Stap 1 : bovenste schijven naar de hulp staaf verplaatsen
Recursieve stap
bron doel hulp Stap 2 : grootste schijf naar de “doel” staaf verplaatsen
Recursieve stap Stap 3 : bovenste 3 schijven er terug op plaatsen bron doel hulp
Recursieve stappen
Welke problemen blijven nog over?
Stap 1 Het verplaatsen van de bovenste 3 schijven van de bron staaf naar de hulp staaf.
Stap 3 Het verplaatsen van deze 3 schijven van de hulp naar de doel staaf.
Recursieve stappen
bron doel hulp Stap 1
Het verplaatsen van de bovenste 3 schijven van de bron staaf naar de hulp staaf.
Recursieve stappen Stap 1
Het verplaatsen van de bovenste 3 schijven van de bron staaf naar de hulp staaf. bron doel hulp
Recursieve stappen
bron doel hulp Stap 3
Het verplaatsen van deze 3 schijven van de hulp naar de
doel staaf.
Recursieve stappen
bron doel hulp Stap 3
Het verplaatsen van deze 3 schijven van de hulp naar de
doel staaf.
Schrijf in logo een programma dat de volgende uitvoer geeft:
Hanoi algoritme
to hanoitext :aantal :bron :doel :hulp
hanoitext (:aantal-1) :bron :hulp :doel
print (SE "verplaats "schijf "van :bron "naar :doel)
hanoitext (:aantal-1) :hulp :doel :bron
end ;verplaats een :aantal schijven van :bron naar :doel m.b.v :hulp
to hanoitext :aantal :bron :doel :hulp
verplaatsen van (aantal - 1) schijven van bron naar hulp m.b.v doel
verplaatsen van een onderste schijf van bron naar doel
verplaatsen van (aantal - 1) schijven van hulp naar doel m.b.v bron
end
Om een zin te printen : print (SE “woord :variabele)
Comments