Problema 1: Escribe un
programa llamado relojZZ
(donde ZZ es la clave de
dos
dígitos asignada por el profesor) basado en el algoritmo visto
en clase para resolver el problema de las torres de Hanoi cuando
sólo se
permite mover discos de la aguja 1 a la aguja 2, de la aguja 2 a la
aguja 3 y de la aguja 3 a la aguja 1. Su programa
debe leer un entero N y debe generar 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. Puedes
suponer que 1 <= N <= 10.
| Ejemplo de entrada |
Ejemplo de salida |
| 1 |
1 2 2 3 0 0 |
Problema 2: Los
números de Lucas se definen de la siguiente manera: L(0) = 2,
L(1) = 1 y L(N) = L(N-1) + L(N-2). Escribe un programa llamado lucasZZ (donde ZZ es la clave de
dos
dígitos asignada por el profesor) que lea un entero N y que
calcule tanto el N-ésimo número de Lucas L(N) como la
cantidad R de llamadas recursivas necesarias para obtener ese
resultado. Por ejemplo si N = 3 entonces se llama a L(3), que a su vez
llama a L(2) y a L(1). De estas dos, sólo L(2) hace llamadas
recursivas a L(1) y a L(0), así en total se hacen R = 5 llamadas
recursivas para calcular L(3) = 4.
| Ejemplo de entrada |
Ejemplo de salida |
| 3 |
4 5 |
Notas: Tus 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.