Tarea 2 de Diseño de Algoritmos
Trimestre 2007 Primavera
Entrega: 18 de mayo de 2007 a las 22:00.
Problema
1: Sean A, B y M tres números positivos. Diseñe un
algoritmo de divide y vencerás para calcular AB
módulo M de manera eficiente, es decir, con pocas
multiplicaciones. Por ejemplo, si A = 2, B = 8 y M = 5 entonces podemos
calcular 22 mod 5 = 4 con una multiplicación, luego 24
mod 5 = 1 con otra y finalmente 28 mod 5 = 1 con una
tercera. Escriba un programa en C (gcc),
C++ (g++), Pascal (fpc) o Java (gcj) llamado moduloZZ (donde ZZ es una clave de dos
dígitos asignada por el profesor) basado en su algoritmo
que acepte como entrada tres enteros A, B y M y que escriba como salida
el valor de AB módulo M. De nuevo, si la entrada
fuera 2 8 5
entonces la salida debe ser 1.
Puede suponer que 0 < A < 230, 0 < B < 230
y 0 < M < 215.
Problema 2: Sea N un entero
positivo y considere el problema de las torres de Hanoi donde los
discos 1, 4, 7, ..., etc. son verdes, los discos 2, 5, 8, ..., etc. son
blancos, los discos 3, 6, 9, ..., etc. son rojos y no se permite poner
un disco sobre otro del mismo color. Diseñe un
algoritmo de divide y vencerás para mover los N discos de la
aguja 1 a la aguja 3. Observe que para N <= 3 la solución es
la misma que para el problema original de las torres de Hanoi. Escriba
un programa en C (gcc),
C++ (g++), Pascal (fpc) o Java (gcj) llamado thtresZZ
(donde ZZ es una clave de
dos dígitos asignada por el profesor) basado en su algoritmo que
acepte como entrada un entero N y que
escriba como salida una sucesión de movimientos para resolver el
problema (uno por renglón y terminando con 0 0). Si la entrada fuera 3 entonces la salida
podría ser
1
3
1 2
3 2
1 3
2 1
2 3
1 3
0 0
Puede suponer que 0
<= N <= 100.
Nota: Sus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado.