TORRES HANOI

¿COMO ES EL ALGORITMO PARA RESOLVER EL PROBLEMA DE LAS TORRES HANOI?

El rompecabezas de la Torre de Hanoi fue inventado por el matemático francés Edouard Lucas en 1883. Se inspiró en una leyenda acerca de un templo hindú donde el rompecabezas fue presentado a los jóvenes sacerdotes. Al principio de los tiempos, a los sacerdotes se les dieron tres postes y una pila de 64 discos de oro, cada disco un poco más pequeño que el de debajo. Su misión era transferir los 64 discos de uno de los tres postes a otro, con dos limitaciones importantes. Sólo podían mover un disco a la vez, y nunca podían colocar un disco más grande encima de uno más pequeño. Los sacerdotes trabajaban muy eficientemente, día y noche, moviendo un disco cada segundo. Cuando terminaran su trabajo, dice la leyenda, el templo se desmenuzaría en polvo y el mundo se desvanecería.

Aunque la leyenda es interesante, usted no tiene que preocuparse de que el final del mundo ocurra pronto en cualquier momento. El número de movimientos necesarios para mover correctamente una torre de 64 discos es 264−1=18,446,744,073,709,551,615$2^{64}-1=18,446,744,073,709,551,615$. A una velocidad de un movimiento por segundo, ¡eso sería 584,942,417,355$584,942,417,355$ años! Claramente hay algo más en este rompecabezas de lo que parece.

La Figura 1 muestra un ejemplo de una configuración de discos en el proceso de movimiento del primer poste al tercero. Observe que, según especifican las reglas, los discos de cada poste se apilan de manera que los discos más pequeños estén siempre encima de los discos más grandes. Si usted no ha intentado resolver este rompecabezas antes, debe probarlo ahora. No necesita discos y postes elegantes, una pila de libros o trozos de papel servirán.

Figura 1: Una disposición ilustrativa de los discos para la Torre de Hanoi

¿Cómo vamos a resolver este problema recursivamente? ¿Cómo resolvería usted este problema en todo caso? ¿Cuál es nuestro caso base? Pensemos en este problema desde abajo hacia arriba. Supongamos que usted tiene una torre de cinco discos, originalmente en un poste. Si usted ya sabía cómo mover una torre de cuatro discos al poste dos, entonces podría mover fácilmente el disco inferior al poste tres, y luego mover la torre de cuatro discos desde el poste dos al poste tres. Pero ¿qué tal si usted no sabe cómo mover una torre de altura cuatro? Supongamos que usted sabía cómo mover una torre de altura tres al poste tres; entonces sería fácil mover el cuarto disco al poste dos y mover los tres discos del poste tres encima de aquél. Pero ¿qué tal si usted no sabe cómo mover una torre de tres discos? ¿Qué tal si usted mueve una torre de dos discos al poste dos y luego mueve el tercer disco al poste tres, y luego mueve la torre de altura dos encima de dicho disco? Pero ¿qué tal si todavía no sabe cómo hacer esto? Seguramente estaría de acuerdo en que mover un solo disco al poste tres es bastante fácil, trivial incluso podría decirse. Esto suena como un caso base.

El siguiente es un esquema de alto nivel de cómo mover una torre desde el poste de origen, hasta el poste destino, utilizando un poste intermedio:

1. Mover una torre de altura-1 a un poste intermedio, utilizando el poste destino.
2. Mover el disco restante al poste destino.
3. Mover la torre de altura-1 desde el poste intermedio hasta el poste destino usando el poste de origen.

Siempre y cuando obedezcamos la regla de que los discos más grandes deben permanecer en la parte inferior de la pila, podemos usar los tres pasos anteriores recursivamente, tratando cualquier disco más grande como si ni siquiera estuviera allí. Lo único que falta en el esquema anterior es la identificación de un caso base. El problema de la torre de Hanoi más simple es una torre de un disco. En ese caso, sólo necesitamos mover un solo disco a su destino final. Una torre de un disco será nuestro caso base. Además, los pasos descritos anteriormente nos mueven hacia el caso base reduciendo la altura de la torre en los pasos 1 y 3. El Programa 1 muestra el código en Python para resolver el rompecabezas de la Torre de Hanoi.

Programa 1

1 2 3 4 5

def moverTorre(altura,origen, destino, intermedio): if altura >= 1: moverTorre(altura-1,origen,intermedio,destino) moverDisco(origen,destino) moverTorre(altura-1,intermedio,destino,origen)

Note que el código en el Programa 1 es casi idéntico a la descripción en español. La clave de la simplicidad del algoritmo es que realizamos dos llamadas recursivas diferentes, una en la línea 3 y otra en la línea 5. En la línea 3 movemos todo menos el disco inferior de la torre de origen hacia un poste intermedio. La siguiente línea simplemente mueve el disco inferior a su lugar final. Luego, en la línea 5, movemos la torre desde el poste intermedio hasta la parte superior del disco más grande. El caso base se detecta cuando la altura de la torre es 0; en ese caso no habrá nada que hacer, por lo que la función moverTorre simplemente regresa el control. Lo importante a tener en cuenta al tratar el caso base de esta manera es que simplemente el regreso desde moverTorre es lo que finalmente permite que la función moverDisco sea invocada.

La función moverDisco, que se muestra en el Programa 2, es muy simple. Todo lo que hace es imprimir que se está moviendo un disco de un poste a otro. Si usted codifica y ejecuta el programa moverTorrepodrá ver que le da una solución muy eficiente al rompecabezas.

Note que el código en el Programa 1 es casi idéntico a la descripción en español. La clave de la simplicidad del algoritmo es que realizamos dos llamadas recursivas diferentes, una en la línea 3 y otra en la línea 5. En la línea 3 movemos todo menos el disco inferior de la torre de origen hacia un poste intermedio. La siguiente línea simplemente mueve el disco inferior a su lugar final. Luego, en la línea 5, movemos la torre desde el poste intermedio hasta la parte superior del disco más grande. El caso base se detecta cuando la altura de la torre es 0; en ese caso no habrá nada que hacer, por lo que la función moverTorre simplemente regresa el control. Lo importante a tener en cuenta al tratar el caso base de esta manera es que simplemente el regreso desde moverTorre es lo que finalmente permite que la función moverDisco sea invocada.

La función moverDisco, que se muestra en el Programa 2, es muy simple. Todo lo que hace es imprimir que se está moviendo un disco de un poste a otro. Si usted codifica y ejecuta el programa moverTorrepodrá ver que le da una solución muy eficiente al rompecabezas.

Programa 2

def moverDisco(desde,hacia):
    print("mover disco de",desde,"a",hacia)

¿LAS TORRES DE HANOI SON DE COMBINACION O DE PERMUTACION?

Las torres de hanoi, son de permutacion ya que se agrupan las difrentes combinaciones de disco que se puden hacer par resolver el problema de las torres de hanoi.

¿Como se representa una torre de hanoi?

Una torre

¿Que es una torre de Hanoi?
Un Rompecabezas

¿Porque Se compone una de hanoi?
Por discos y una torre

¿Cual es el pseudocodigo del problema de hanoi?

def moverTorre(altura,origen, destino, intermedio):
    if altura >= 1:
        moverTorre(altura-1,origen,intermedio,destino)
        moverDisco(origen,destino)
        moverTorre(altura-1,intermedio,destino,origen)

¿Poque matematico fue inventado la torre de hanoi?
Edouard Lucas

¿En que año?
1883
¿En que se inspiro?
Se inspiró en una leyenda acerca de un templo hindú donde el rompecabezas.
¿Para quienes fue presentado?
fue presentado a los jóvenes sacerdotes
¿En cuantas secciones fue dividida?
3
¿Como eran al principio los templos de los sacerdotes?

Al principio de los tiempos, a los sacerdotes se les dieron tres postes y una pila de 64 discos de oro, cada disco un poco más pequeño que el de debajo. Su misión era transferir los 64 discos de uno de los tres postes a otro, con dos limitaciones importantes. Sólo podían mover un disco a la vez, y nunca podían colocar un disco más grande encima de uno más pequeño.

CUESTIONARIO

1°-¿Qué son las Torres de Hanoi?

La Torres de Hanoi es un rompecabezas o juego matemático.

2°-¿Cuándo se inventaron las Torres de Hanoi?

Fue inventado en 1883 por el matemático francés Édouard Lucas.

3°-¿En que consiste este juego?

Este juego de mesa individual consiste en un número de discos perforados de radio creciente que se apilan insertándose en uno de los tres postes fijados a un tablero. 

4°-¿Cuál es el objetivo del juego?

El objetivo del juego es trasladar la pila a otro de los postes siguiendo ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.

5°-¿Cual es la formula para el juego?

La fórmula para encontrar el número de movimientos necesarios para transferir n discos desde un poste a otro es: 2ⁿ - 1

6°-¿Cómo es el algoritmo para resolver el problema de las Torres de Hanoi?

La solución del problema de las Torres de Hanói es muy fácil de hallar, aunque el número de pasos para resolver el problema crece exponencialmente conforme aumenta el número de discos.Como ya se ha indicado, el número mínimo de movimientos necesarios para resolver un rompecabezas de la Torre de Hanoi es 2ⁿ - 1, donde n es la cantidad de discos.

Una manera sencilla para saber si es posible terminar el "juego" es que si la cantidad de discos es impar la pieza inicial ira a destino y si es par a auxiliar.

7°-¿Mediante que procesos se puede resolver el problema de las Torres de Hanoi?

-Solución Simple

-Mediante recursividad

-Iterativa

8°-¿En qué consiste "La solución Simple"?

El disco 2.^o n-1 se debe mover, por regla, a la varilla destino. Luego, el disco n.^o 1 se mueve también a la varilla destino para que quede sobre el disco n.^o 2. A continuación, se mueve el disco que sigue de la varilla origen, en este caso el disco n.^o 3, y se coloca en la varilla auxiliar. Finalmente, el disco n.^o 1 regresa de la varilla destino a la origen (sin pasar por la auxiliar), y así sucesivamente. Es decir, el truco está en el disco más pequeño.

9°-¿En qué consiste la solución "Mediante Recursividad"?

Si numeramos los discos desde 1 hasta n, si llamamos origen a la primera pila de discos, destino a la tercera y auxiliar a la intermedia, y si a la función la denomináramos hanoi, con origen, auxiliar y destino como parámetros, el algoritmo de la función sería el siguiente:

El número de movimientos mínimo a realizar para resolver el problema de este modo es de 2ⁿ – 1, siendo n el número de discos.

10°-¿En qué consiste la solución "Iterativa"?

Se basa en el hecho de que para obtener la solución más corta, es necesario mover el disco más pequeño en todos los pasos impares, mientras que en los pasos pares solo existe un movimiento posible que no lo incluye.

SERIE FIBONACCI

 ¿QUE ES UNA SERIE FIBONACCI?

La sucesión de Fibonacci, en ocasiones también conocida como secuencia de Fibonacci o incorrectamente como serie de Fibonacci, es en sí una sucesión matemática infinita. Consta de una serie de números naturales que se suman de a 2, a partir de 0 y 1. Básicamente, la sucesión de Fibonacci se realiza sumando siempre los últimos 2 números.

¿QUIEN CREO LA SERIE FIBONACCI?

Leonardo de Pisa, también conocido como Fibonacci (1170 – 1250) es un famoso matemático italiano famoso por difundir en Europa el sistema de numeración actualmente utilizado, esto es un sistema de numeración posicional en base decimal y un dígito de valor nulo (cero), y por idear la sucesión de Fibonacci.

La sucesión de Fibonacci es una serie de números que se obtiene por adición de lo dos números anteriores, obteniéndose la serie: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.

Y que tiene de especial esta serie? Bien, esta serie se hizo especialmente famosa por describir las proporciones naturales, supuestamente, de todas las cosas en el universo. Lo cierto es que hoy en día la aparición de esta serie ocurre de forma muy amplia y extensa en campos como las matemáticas, ciencias de la computación, biología o teoría de juegos.

Las famosas proporciones que describen la serie de Fibonacci se van obteniendo mediante cocientes entre números de la serie, por ejemplo, si se divide un número de la serie entre el siguiente se obtiene una proporción de 0.618 (inverso de la proporción áurea), por ejemplo, 21 entre 34. Si divides dos número alternos obtendrás 0.382, por ejemplo 55 entre 144.

No tendrás que calcularlas, es muy extraño que un software de trading no tenga las herramientas de cálculo de las proporciones de Fibonacci.

¿COMO ES LA SERIE FIBONASSI?

CUESTIONARIO

1°-¿Que es la serie de Fibonacci?

En matemáticas la sucesión o serie de Fibonacci es la siguiente sucesión infinita de números naturales:

       

2°-¿Cuando se creo la Serie de Fibonacci?

Esta sucesión fue descrita en Europa por Leonardo de Pisa, matemático italiano del siglo XIII también conocido como Fibonacci.

3°-¿En qué ámbitos se aplica dicha serie?

Tiene numerosas aplicaciones en ciencias de la computación, matemática y teoría de juegos. 

4°-¿Cuál es la relación de la sucesión de Fibonacci?

La sucesión comienza con los números 0 y 1,​ y a partir de estos, «cada término es la suma de los dos anteriores», es la relación de recurrencia que la define.

5°-¿Cuál es la regla de la sucesión de Fibonacci?

 Por regla, la sucesión de Fibonacci se escribe así: xn = xn-1 + xn-2.

6°-¿Cuáles son los métodos para calcular los números de Fibonacci?

-Función generadora

-Formula explicita 

-Por la función

7°-¿En que consiste la "Función Generadora"?

Una función generadora para una sucesión cualquiera a0, a1, a2,… es la función f(X) = a0 + a1x + a2x2+…, es decir, una serie formal de potencias donde cada coeficiente es un elemento de la sucesión. Los números de Fibonacci tienen la función generadora:

8°-¿En qué consiste la "Formula Explicita"?

Esta manera de calcular los números de Fibonacci utiliza la expresión del número áureo:

9°-¿Cómo se desarrolla el método"Por la Función"  para calcular los números de Fibonacci ?Partiendo de los números 0 y 1, los números de Fibonacci quedan definidos por la función

10°-¿Cómo es la serie de Fibonacci?

Básicamente, la sucesión de Fibonacci se realiza sumando siempre los últimos 2 números (Todos los números presentes en la sucesión se llaman números de Fibonacci) de la siguiente manera:
                                                       0,1,1,2,3,5,8,13,21,34...