Torres de hanoi
Páginas: 8 (1831 palabras)
Publicado: 10 de marzo de 2011
Torres de Hanoi
Contexto Histórico
El juego de las torres de Hanoi fue inventado en 1883 por un matemático francés de nombre Edouard Lucas, quien además de inventar el juego se le atribuye el invento de la historia que precede a las torres.
La historia detrás de esta historia cuenta que cuando Dios creó al mundo, en el centro de la tierra creó tres varillas de diamante y sesenta y cuatrodiscos de oro puro de distintos tamaños. Tiempo después varios monjes durante una expedición encontraron estas varillas con los discos acomodados del de mayor tamaño al de menor tamaño formando una torre. Posteriormente los mismos monjes establecieron ciertas reglas:
1. No se podía mover más de un disco al día.
2. No se puede poner un disco más grande sobre uno más pequeño.
3. Se puedenmover los discos a cualquiera de las otras varillas siempre y cuando no interfiera con las leyes anteriores.
[pic]
Rápidamente después de este hecho los monjes construyeron un templo para esconder el secreto de las Torres de Hanoi para que se conservara el secreto y comenzar el mandato de Dios. La historia establece que los monjes día a día tienen que mover los discos de una varilla a otra ycuando hayan conseguido trasladar todos discos a otra varilla su trabajo estará terminado de tal manera que el templo y la torre se derrumbaran y con un gran trueno el mundo se acabará.
Sin embargo, tiempo después las investigaciones sobre los orígenes de esta historia llegaron a la conclusión de que todo fue un invento del creador del juego para tener un éxito mayor.
Algoritmo recursivo yformula explicita para Hn
1. Si se tiene únicamente un disco, se mueve a la torre tres
2. En la caso contrario al uno, de tener más de un disco en la torre 1, se manda llamar al algoritmo recursivo para mover n-1 discos de hasta arriba de la torre 2. Dejando el último disco fijo.
3. Posteriormente se mueve el disco que queda en la torre 1 a la torre 3.
4. Para finalizar, se vuelve allamar al algoritmo recursivamente para mover los discos de la torre 2 a la torre 3, para que tengamos al final todos los discos en la torre 3.
5. De esta manera, se define la formula como Cn = 2Cn-1 +1 para n > 1, donde n es el número de discos.
Existe la relación de recurrencia Cn = 2Cn-1 +1y la condición inicial C1 = 1de ahí se puede obtener la formula explicita que es 2n-1 para encontrarel n número mínimo de movimientos que se necesitan para resolver el juego. Por ejemplo si nuestro juego contiene 5 discos, el número mínimo de movimientos sería 25-1 = 31. Si aplicamos está formula a la leyenda mencionada anteriormente del juego de 64 discos necesitaríamos 18446744073709551616 movimientos como mínimo para solucionar el juego.
Método de Newton (Newton-Raphson)
ContextoHistórico
La solución de ecuaciones ha sido una tarea esencial de las matemáticas, fueron los antiguos matemáticos de Babilonia quienes descubrieron el método de Completar Cuadrados para encontrar las raíces de ecuaciones de segundo grado. Posteriormente, fue hasta el siglo XVI cuando los italianos Cardan, Ferrari, del Ferro y Tartaglia descubrieron fórmulas para las raíces de ecuaciones de tercer ycuarto grado. Sin embargo en 1824, el noruego Niels Herink Abel, publicó una prueba general de que no existe una fórmula general para una ecuación polinomial de grado 5 o mayor en términos de combinaciones algebraicas de sus coeficientes[1]. Y entonces en tales casos es necesario recurrir a métodos aproximados.
En el siglo XVII, Isaac Newton (1642-1727) hizo importantes aportaciones en distintoscampos de la ciencia, de las cuales se destacan sus aportaciones en la matemática y en la física. Isaac Newton entró a Cambridge en 1661 y para el otoño de 1666, Newton desarrollo lo que hoy conocemos como cálculo, un método nuevo y poderoso que situó a las matemáticas modernas por encima del nivel de la geometría griega[2]. Newton, en su obra Principia Mathematica empezó a aplicar el cálculo...
Contexto Histórico
El juego de las torres de Hanoi fue inventado en 1883 por un matemático francés de nombre Edouard Lucas, quien además de inventar el juego se le atribuye el invento de la historia que precede a las torres.
La historia detrás de esta historia cuenta que cuando Dios creó al mundo, en el centro de la tierra creó tres varillas de diamante y sesenta y cuatrodiscos de oro puro de distintos tamaños. Tiempo después varios monjes durante una expedición encontraron estas varillas con los discos acomodados del de mayor tamaño al de menor tamaño formando una torre. Posteriormente los mismos monjes establecieron ciertas reglas:
1. No se podía mover más de un disco al día.
2. No se puede poner un disco más grande sobre uno más pequeño.
3. Se puedenmover los discos a cualquiera de las otras varillas siempre y cuando no interfiera con las leyes anteriores.
[pic]
Rápidamente después de este hecho los monjes construyeron un templo para esconder el secreto de las Torres de Hanoi para que se conservara el secreto y comenzar el mandato de Dios. La historia establece que los monjes día a día tienen que mover los discos de una varilla a otra ycuando hayan conseguido trasladar todos discos a otra varilla su trabajo estará terminado de tal manera que el templo y la torre se derrumbaran y con un gran trueno el mundo se acabará.
Sin embargo, tiempo después las investigaciones sobre los orígenes de esta historia llegaron a la conclusión de que todo fue un invento del creador del juego para tener un éxito mayor.
Algoritmo recursivo yformula explicita para Hn
1. Si se tiene únicamente un disco, se mueve a la torre tres
2. En la caso contrario al uno, de tener más de un disco en la torre 1, se manda llamar al algoritmo recursivo para mover n-1 discos de hasta arriba de la torre 2. Dejando el último disco fijo.
3. Posteriormente se mueve el disco que queda en la torre 1 a la torre 3.
4. Para finalizar, se vuelve allamar al algoritmo recursivamente para mover los discos de la torre 2 a la torre 3, para que tengamos al final todos los discos en la torre 3.
5. De esta manera, se define la formula como Cn = 2Cn-1 +1 para n > 1, donde n es el número de discos.
Existe la relación de recurrencia Cn = 2Cn-1 +1y la condición inicial C1 = 1de ahí se puede obtener la formula explicita que es 2n-1 para encontrarel n número mínimo de movimientos que se necesitan para resolver el juego. Por ejemplo si nuestro juego contiene 5 discos, el número mínimo de movimientos sería 25-1 = 31. Si aplicamos está formula a la leyenda mencionada anteriormente del juego de 64 discos necesitaríamos 18446744073709551616 movimientos como mínimo para solucionar el juego.
Método de Newton (Newton-Raphson)
ContextoHistórico
La solución de ecuaciones ha sido una tarea esencial de las matemáticas, fueron los antiguos matemáticos de Babilonia quienes descubrieron el método de Completar Cuadrados para encontrar las raíces de ecuaciones de segundo grado. Posteriormente, fue hasta el siglo XVI cuando los italianos Cardan, Ferrari, del Ferro y Tartaglia descubrieron fórmulas para las raíces de ecuaciones de tercer ycuarto grado. Sin embargo en 1824, el noruego Niels Herink Abel, publicó una prueba general de que no existe una fórmula general para una ecuación polinomial de grado 5 o mayor en términos de combinaciones algebraicas de sus coeficientes[1]. Y entonces en tales casos es necesario recurrir a métodos aproximados.
En el siglo XVII, Isaac Newton (1642-1727) hizo importantes aportaciones en distintoscampos de la ciencia, de las cuales se destacan sus aportaciones en la matemática y en la física. Isaac Newton entró a Cambridge en 1661 y para el otoño de 1666, Newton desarrollo lo que hoy conocemos como cálculo, un método nuevo y poderoso que situó a las matemáticas modernas por encima del nivel de la geometría griega[2]. Newton, en su obra Principia Mathematica empezó a aplicar el cálculo...
Leer documento completo
Regístrate para leer el documento completo.