Problema 1: Escribe un
programa llamado hanoiZZ
(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 no se
permite mover discos entre la pila inicial y la pila final. Su programa
debe leer un entero N y debe generar como salida la cantidad M de
movimientos necesarios para mover los N discos de la pila inicial a la
pila final seguido de M renglones, cada uno de ellos indicando de
cuál pila a cuál pila se movió un disco. Por
ejemplo si N = 2 se necesitan M = 8 movimientos para mover los discos.
Las pilas estarán numeradas como 0 = inicial, 1 = auxiliar y 2 =
final. Puedes suponer que 1 <= N <= 10.
| Ejemplo de entrada |
Ejemplo de salida |
| 2 |
8 0 1 1 2 0 1 2 1 1 0 1 2 0 1 1 2 |
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.