Skip to content
ExamplesEspañolWorkspace →

Towers of Hanoi

Solves the classic tower puzzle step by step.

Level
Advanced
Topic:
Subprocesses & functions
Concepts:
Input & output
SubProcesos
Recursion
Si
Open in Codoritmo

Run, change and debug this example in your browser.

What you'll learn

Hanoi is a recursive SubProceso: it calls itself with one disk fewer. The base case (a single disk) is what stops the recursion.

Code

hanoi.psc · 18 lines
SubProceso Hanoi(discos, origen, destino, auxiliar)    Si discos = 1 Entonces        Escribir "Mover disco 1 de ", origen, " a ", destino    SiNo        // Primero apartamos los discos de arriba, luego volvemos a apilarlos        Hanoi(discos - 1, origen, auxiliar, destino)        Escribir "Mover disco ", discos, " de ", origen, " a ", destino        Hanoi(discos - 1, auxiliar, destino, origen)    FinSiFinSubProcesoAlgoritmo TorresDeHanoi    Definir n Como Entero    Escribir "¿Cuántos discos? (1 a 6)"    Leer n    Hanoi(n, "A", "C", "B")    Escribir "Total de movimientos: ", 2 ^ n - 1FinAlgoritmo

Flowchart

Each block in the flowchart matches one instruction in the code.

Algoritmo TorresDeHanoi
Algoritmo TorresDeHanoiAlgoritmo TorresDeHanoiAlgoritmo TorresDeHanoiDefinir n Como EnteroDefinir n Como EnteroEscribir "¿Cuántos discos? (1 a 6)"Escribir "¿Cuántos discos? (1a 6)"Leer nLeer nHanoi(n, "A", "C", "B")Hanoi(n, "A", "C", "B")Escribir "Total de movimientos: ", 2 ^ n - 1Escribir "Total demovimientos: ", 2 ^ n - 1FinAlgoritmoFinAlgoritmo
SubProceso Hanoi
SubProceso HanoiSíNoSubProceso Hanoi(discos, origen, destino, auxiliar)SubProceso Hanoi(discos, origen,destino, auxiliar)Si discos = 1 Entoncesdiscos = 1Escribir "Mover disco 1 de ", origen, " a ", destinoEscribir "Mover disco 1 de ",origen, " a ", destinoHanoi(discos - 1, origen, auxiliar, destino)Hanoi(discos - 1, origen,auxiliar, destino)Escribir "Mover disco ", discos, " de ", origen, " a ", destinoEscribir "Mover disco ",discos, " de ", origen, " a ",destinoHanoi(discos - 1, auxiliar, destino, origen)Hanoi(discos - 1, auxiliar,destino, origen)FinSubProcesoFinSubProceso

Sample run

This is what the program shows when it runs. The answers typed by the user are highlighted.

¿Cuántos discos? (1 a 6)User answer: 3Mover disco 1 de A a CMover disco 2 de A a BMover disco 1 de C a BMover disco 3 de A a CMover disco 1 de B a AMover disco 2 de B a CMover disco 1 de A a CTotal de movimientos: 7

Complexity

How much work and memory it needs as the amount of data (n) grows.

Complexity
CaseCost
BestO(2ⁿ)
AverageO(2ⁿ)
WorstO(2ⁿ)
MemoryO(n)

Challenge

Check that the number of disks is between 1 and 6 before starting.

Show hint

Put a Repetir ... Hasta Que around the Leer n.

Open in Codoritmo

Related examples

  • Merge Sort

    Splits the array in halves, sorts each one recursively and merges them.

    Advanced

  • Quicksort

    Picks a pivot, splits smaller from larger values and sorts each side recursively.

    Advanced

  • By Reference and by Value

    Sorts three numbers by swapping them in subprocesses.

    Intermediate