Recursie: De torens van Hanoi Lesgever: Tineke Broekaert
Recursie: De torens van Hanoi Lesgever: Tineke Broekaert
Herhaling
algoritme roept zichzelf op
opgeroepen probleem kleiner dan origineel
2 delen: basisgeval en recursief gedeelte
oplossing: Eerst basisgeval behandelen!
voorbeeld: n! = n(n-1)! Recursie?
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel Voorwaarden: 1 schijf verplaatsen per beurt
geen grote staaf op kleinere plaatsen 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3 BASISGEVAL: 1 schijf verplaatst
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3 toren van 2 schijven verplaatst
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3 Toren van drie schijven verplaatst
De torens van Hanoi
hulp bron doel 1 2 3
De torens van Hanoi
hulp bron doel 1 2 3 Toren van 4 schijven verplaatst
De torens van Hanoi
Als N = 1 enige schijf verplaatst
Als N > 1
- Verplaats bovenste n-1 schijven van bron- naar hulpstaaf
- Verplaats onderste schijf van begin- naar doelstaaf
- Verplaats n-1 schijven van hulp- naar doelstaaf recursie!! recursie!! basisgeval!! Probleem opsplitsen in deelproblemen
Algoritme:
Implementatie in Logo
beginsituatie: staven en schijven op het scherm tekenen
verplaatsen van schijven: schijf afhalen van staaf
schijf toevoegen aan staaf beginsituatie HANOI verplaatsSchijven basisgeval Recursieve oproep Deelproblemen?
Comments