Problema de matemáticas y computación
Problema de tores de Hanoi hacia la derecha
Grupo: 1906
Fecha: 22 de septiembre del 2014
Contenido
•
•
•
•
•
Objetivo.
Marco teórico.Definición del problema.
Desarrollo del problema.
Bibliografía.
Objetivo
• Resolver un problema haciendo uso de
recurrencias, programación dinámica, álgebra,
y funciones generadoras, para asíanalizar el
problema, obtener sus recurrencias, sus
propiedades, y al final encontrar una fórmula
cerrada para lo que se nos pide.
Marco teórico
• Para resolver este problema, se hace uso de:
–Recurrencias
– Programación dinámica
– Funciones generadoras
– Álgebra
Definición del problema
Se tiene el problema de las torres de hanoi, pero los únicos movimientos permitidos
serán hacia laderecha, esto es, si quiero mover un disco a la posición 1, este tendrá
que estar en la posición 0, y de la misma manera, para mover un disco a la posición 2,
este tiene que estar en la posición 1,y para mover un disco a la posición 0, este tiene
que estar en la posición 2.
Al igual que en el problema clásico, todos los discos son de diferente tamaño, y un disco
no se puede colocar sobre undisco de menor tamaño.
Se encontrará el número de movimientos necesarios para mover los n discos de la
posición 0 a la 1, y de la posición 0 a la 2.
Desarrollo del problema
• Primero seencuentran las recurrencias:
• Que indican la cantidad de movimientos
necesarios para mover n discos 1 o 2 lugares.
• Esto es relativamente
fácil de programar
usando programación
dinámica.
•Podemos ver que F1 depende de F2, por lo
tanto, podemos definir F2 en términos de sí
mismo.
• Usando funciones
generadoras para
resolver F2…
• Llegamos a que:
• Por lo que:
• Ya queF2(0)=0.
• Comprobando algunos resultados de F1 con
WolframAlpha
• F1(1)=1
• F1(2)=5
• F1(5)=119
• F1(10)=18271
• F1(50)=5264252699486868996095
• Todos estos valores coinciden...
Regístrate para leer el documento completo.