Actualmente, he aprendido 3 enfoques diferentes para contar la cantidad mínima de movimientos para resolver la Torre de Hanoi.
El primer enfoque es: 2 a la potencia de "discos" menos 1. Con todo, muy sencillo y comprensible.
const towerHanoi = (discs) => 2**discs - 1; console.log(towerHanoi(0)); // 0 console.log(towerHanoi(2)); // 3 console.log(towerHanoi(3)); // 7 console.log(towerHanoi(4)); // 15 console.log(towerHanoi(5)); // 31 console.log(towerHanoi(6)); // 63El segundo enfoque es con un "bucle for". En cada iteración, agregue "contar" al resultado de 2 a la potencia de "i" Una vez más, muy sencillo y comprensible.
function towerHanoi(discs,count=0) { for (let i = 0; i < discs; i++) count += 2**i; return count; }Sin embargo, en el tercer enfoque con recursividad, simplemente no pude captar el concepto del proceso recursivo.
const towerHanoi = (discs) => discs === 0 ? 0 : 2 * towerHanoi(discs-1) + 1;Usemos 5 discos como ejemplo para ilustrar el proceso recursivo que requiere un mínimo de 31 movimientos para completar el juego. Voy a hacer todo lo posible para desglosar el proceso recursivo como pueda de la siguiente manera:
2 * (5-1) + 1 === 9 2 * (4-1) + 1 === 7 2 * (3-1) + 1 === 5 2 * (2-1) + 1 === 3 2 * (1-1) + 1 === 1 9 + 7 + 5 + 3 + 1 --> 25 =/= 31Como puede ver, obtengo 25 en lugar de 31. ¿Qué me estoy perdiendo? ¿Puede alguien amablemente ayudarme a entender el proceso recursivo del código? Gracias por leer y millones de gracias de antemano :)
El razonamiento detrás de esta fórmula recursiva:
const towerHanoi = (discs) => discs === 0 ? 0 : 2 * towerHanoi(discs-1) + 1;...es como sigue:
Supongamos que sabemos cómo mover discs-1 discos de una pila a otra. Entonces podemos usar ese conocimiento de la siguiente manera:
Mueva todos los discos, excepto el de abajo, al punto medio (usando ese conocimiento). Luego mueva el disco más grande al lugar final. Finalmente, mueva la pila del medio encima de ese disco más grande, aplique nuevamente ese conocimiento.
Entonces, de hecho, necesitamos mover dos veces una pila de discs - 1 disco y hacer otro movimiento. Eso nos da esa parte recursiva de la fórmula.
En cuanto a su análisis para 5 discos. No aplicaste la recursividad correctamente. El (5-1) no se puede evaluar así, aún debe expandirse a niveles de recursividad más profundos. Así es como se debe hacer:
2 * ( 2 * ( 2 * ( 2 * ( 2 * ( 0 = 0 (base case) ) + 1 = 1 ) + 1 = 3 ) + 1 = 7 ) + 1 = 15 ) + 1 = 31