Medio–difícil · recursión

Torres de Hanói

Es el primer problema cuya respuesta es llamarte a ti mismo. La primera vez parece hacer trampa. No lo es: es toda la idea.

En una fraseMueve n discos de A a C usando B con tres llamadas recursivas: lleva n−1 al poste auxiliar, mueve el último disco y trae los n−1 de vuelta; en total 2ⁿ − 1 movimientos.

El problema

Entrada: Un entero n (1 ≤ n ≤ 8): el número de discos, todos empezando en el poste A.

Salida: Un movimiento por línea, con la forma X->Y, trasladando toda la pila de A a C usando B como auxiliar. Un disco mayor nunca puede quedar sobre uno menor.

Ejemplos:

Entrada	Salida
`1`	`A->C`
`2`	`A->B A->C B->C`
`3`	`A->C A->B C->B A->C B->A B->C A->C`

n discos necesitan exactamente 2ⁿ − 1 movimientos: 1, 3, 7, 15… Ese número es la huella de la recursión: cada nivel duplica el trabajo más un movimiento.

Tu solución

main.cpp — tu solución

Entrada personalizada para «Ejecutar mi entrada»

La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.

¿Atascado? Pistas

Pista 1 — Olvida los discos pequeños

Para mover n discos de A a C no necesitas pensar en n discos, sino en uno: el mayor. Tiene que acabar en C, y para eso C debe estar vacío y los otros n−1 discos deben estar todos en B. Esa es toda la estructura de la solución.

Pista 2 — Tres líneas, y una es un print

Mueve n−1 de from a aux (usando to de repuesto). Imprime from->to. Mueve n−1 de aux a to (usando from de repuesto). Ya está. Nunca mueves un disco directamente: describes la situación y dejas que la recursión trabaje.

Pista 3 — El caso base es n == 0, no n == 1

Ambos funcionan, pero n == 0 es más limpio: "mover cero discos" es una petición válida, completa y que no hace nada. Con n == 1 como base tienes que tratar el print aparte y el cuerpo de tres pasos deja de ser uniforme. Elegir bien el caso base es la mitad de escribir una recursión correcta.

Solución (¡inténtalo primero!)

#include <iostream>
using namespace std;

void hanoi(int n, char from, char aux, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, aux);
    cout << from << "->" << to << endl;
    hanoi(n - 1, aux, from, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}

Mira qué poco código es: seis líneas para un problema que a la mayoría le cuesta una pizarra razonar. Ese es el premio de la recursión: describes una capa y la máquina la expande a 2ⁿ − 1 movimientos. El coste es real: la pila de llamadas crece hasta profundidad n, y si la recursión fuera lineal en vez de dividir a la mitad, entradas grandes la desbordarían. Por eso toda recursión necesita un caso base realmente alcanzable. Último problema: uno donde el truco es aritmético, no de código: Ceros finales.

Análisis profundo

Por qué funciona

Para mover n discos, piensa solo en el mayor: debe acabar en C, así que C debe estar vacío y los otros n−1 discos deben estar en B. El problema se convierte en dos copias más pequeñas de sí mismo.

El coste

Exactamente 2^n − 1 movimientos: la huella de la recursión, donde cada nivel duplica el trabajo más un movimiento. La pila de llamadas llega a profundidad n.

Dónde falla

Usar n == 1 como caso base en vez de n == 0 obliga a una rama especial para el print y el cuerpo de tres pasos deja de ser uniforme.
Empezar la segunda llamada recursiva en from en vez de aux produce movimientos duplicados e inválidos, y nunca da error: solo está mal.

Siguiente paso

El último problema: el truco es aritmético, no de código: Ceros finales.

Dos cosas para recordar

Piensa solo en el disco mayor; el resto se lo dejas a la recursión.
El caso base n == 0 es lo que mantiene uniformes los tres pasos.

🐞 Esta versión falla: ábrela y pruébala

La segunda recursión parte de from en vez de aux: los movimientos se repiten

#include <iostream>
using namespace std;

void hanoi(int n, char from, char aux, char to) {
    if (n == 0) return;
    hanoi(n - 1, from, to, aux);
    cout << from << "->" << to << endl;
    hanoi(n - 1, from, aux, to);
}

int main() {
    int n;
    cin >> n;
    hanoi(n, 'A', 'B', 'C');
    return 0;
}