Torres de Hanói
Resuelve el clásico rompecabezas de las torres paso a paso.
- Nivel
- Avanzado
- Conceptos:
- Entrada y salida
- SubProcesos
- Recursión
- Si
Ejecuta, modifica y depura este ejemplo en el navegador.
Lo que aprenderás
Hanoi es un SubProceso recursivo: se llama a sí mismo con un disco menos. El caso base (un solo disco) es el que detiene la recursión.
Código
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 - 1FinAlgoritmoDiagrama de flujo
Cada bloque del diagrama corresponde a una instrucción del código.
Ejemplo de ejecución
Esto muestra el programa al ejecutarlo. Las respuestas escritas por el usuario aparecen resaltadas.
¿Cuántos discos? (1 a 6)Respuesta del usuario: 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
Complejidad
Cuánto trabajo y memoria necesita según la cantidad de datos (n).
| Caso | Costo |
|---|---|
| Mejor | O(2ⁿ) |
| Promedio | O(2ⁿ) |
| Peor | O(2ⁿ) |
| Memoria | O(n) |
Desafío
Valida que la cantidad de discos esté entre 1 y 6 antes de empezar.
Ver pista
Usa Repetir ... Hasta Que alrededor del Leer n.
Ejemplos relacionados
Ordenamiento por mezcla
Parte el arreglo en mitades, ordena cada una con recursión y las mezcla.
AvanzadoOrdenamiento rápido (Quicksort)
Elige un pivote, separa los menores de los mayores y ordena cada lado con recursión.
AvanzadoPor Referencia y por valor
Ordena tres números intercambiándolos con subprocesos.
Intermedio