Problema de matemáticas y computación

Universidad Nacional Autónoma de México
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...