¿Cuál es el algoritmo recursivo para la Torre de Hanoi?
La Torre de Hanoi, también conocida como Torre de Hanoi, es un juguete educativo con origen en antiguas leyendas indias. Cuando Brahma creó el mundo, hizo tres pilares de diamantes y se apilaron 64 discos de oro en un pilar en orden de tamaño de abajo hacia arriba.
Brahma le ordenó a Brahma que reorganizara los discos en el otro pilar en orden de tamaño de abajo hacia arriba. También se estipula que la placa pequeña no se puede ampliar y solo se puede mover una placa entre tres pilares a la vez.
El matemático francés Edward Lucas escribió una vez una antigua leyenda india: En el templo de Benarés (norte de la India), en el centro del mundo, había tres palos en una placa de latón con una aguja de gemas. Cuando el dios hindú Brahma creó el mundo, colocó 64 piezas de oro de mayor a menor en una de las agujas de abajo hacia arriba. Esta se llama la Torre de Hanoi.
No importa de día o de noche, siempre hay un monje que mueve estas piezas de oro siguiendo las siguientes reglas: solo mueve una pieza a la vez, no importa en qué aguja esté, la pieza más pequeña debe ser en la pieza más grande. El monje predijo que cuando todas las piezas de oro sean trasladadas de la aguja que llevaba Brahma a otra aguja, el mundo será destruido con un rayo, y Brahma, el templo y todos los seres vivientes perecerán juntos.
No importa cuán creíble sea esta leyenda, si consideras mover 64 monedas de oro de una aguja a otra, y siempre mantienes el orden de pequeño hacia arriba y grande hacia abajo.
¿Cuántos pasos se necesitarán? Aquí se necesita un enfoque recursivo. Supongamos que hay n películas y el número de movimientos es f (n). Obviamente, f(1) es igual a 1, f(2) es igual a 3, f(3)=7, f(k 1)=2*f(k) 1. No es difícil demostrar que f (n) = 2 n-1. Cuando n=64.
Si ocurre una vez cada segundo, ¿cuánto tiempo tardará? * * *: Un año normal tiene 365 días y 31.536.000 segundos, un año bisiesto tiene 366 días y 31.622.400 segundos y el año promedio es 31.556.952 segundos. . Calcular: 184474073737.
Esto demuestra que se necesitarán más de 584.554 millones de años para eliminar estos copos de oro, mientras que la Tierra sólo existe desde hace 4.500 millones de años y se dice que la vida útil del sistema solar es de decenas de miles de millones de años. años. Realmente han pasado 584.554 millones de años, por no hablar del sistema solar y la Vía Láctea. Al menos toda la vida en la Tierra, incluidos Brahma y los templos, hace tiempo que desapareció.