Trimestre 2012 Otoño
Entrega: 28 de
septiembre de 2012 a las 22:00.
Problema 1 [5 puntos]:
Diseña un
algoritmo usando la técnica de divide
y
vencerás para resolver el problema de las torres de Hanoi
con la
restricción adicional de que todos los movimientos deben ser de
la aguja 1 a la 2, de la 2 a la 3 o de la 3 a la 1. Escribe un programa
llamado hanoicZZ (donde ZZ es una clave de
dos
dígitos asignada por el profesor) basado en tu algoritmo
que acepte como entrada un entero positivo N (con 1 <= N <= 20) y
que escriba como salida
una lista de movimientos que muevan los N discos de la aguja 1 a la
aguja 3. La lista debe contener dos enteros en cada renglón: 0 0
para indicar que terminó, mientras que A B significa que se
movió un disco de la aguja A a la aguja B. Por ejemplo, si N = 1
una posible salida contiene los tres renglones 1 2, 2 3 y 0 0.
Ejemplos de entrada
Ejemplos de salida
1
1 2
2 3
0 0
2
1 2
2 3
1 2
3 1
2 3
1 2
2 3
0 0
Problema 2 [5 puntos]: Sea n un
entero positivo
y sea a[1], a[2], ..., a[n] un arreglo de enteros distintos
ordenados ascendentemente, es decir, con a[1] < a[2] < ... <
a[n]. El problema del punto fijo es el de encontrar
algún
entero k tal que a[k] = k o decidir que ese entero no existe. Como un
ejemplo, si el arreglo fuera -3, -1, 1, 4, 5, 9 entonces cualquiera
de k = 4 o k = 5 sería una respuesta correcta, pero si el
arreglo
fuera -3, 1, 4, 5, 9 entonces k no existe.
Escribe un
programa llamado pfijoZZ
(donde ZZ es la clave de
dos
dígitos asignada por el profesor) basado en un algoritmo de
divide y vencerás para
resolver el problema del punto fijo (que
es similar al de la búsqueda binaria). Tu
programa debe leer un entero N y un vector A = (A1, A2,
...,
AN) con N enteros positivos tales que A1
< A2 < ... < AN y debe escribir dos
enteros M y P, donde M = AM y P es el número de
preguntas que se hicieron para encontrar M. Por ejemplo si N = 5 y A =
(1, 2, 4, 8, 16) entonces tu algoritmo debe preguntar primero en la
posición 3 y después preguntará en la
posición 1, encontrando un 1 y terminando. Puedes suponer que 1
<= N <= 1,000,000 y que 0 < A1 < A2
< ... < AN < 1,000,000,000.
Ejemplo de entrada
Ejemplo de salida
5
1 2 4 8 16
1 2
Notas: Sus programas no
deben
leer ni escribir nada adicional a lo que se indica en el
enunciado. El
tiempo de ejecución de sus algoritmos será considerado
como parte de la evaluación.