Problema 1: La curva C
es una curva que se define recursivamente de la siguiente manera: La
curva C de nivel 0 es simplemente un segmento de recta. Para toda N
> 0, la curva C de nivel N se obtiene de la curva C de nivel N-1
reemplazando cada segmento ac
de recta por dos segmentos ab
y bc de recta de la siguiente
manera:
Suponga que se definen las ocho direcciones E, NE, N, NO, O,
SO, S y SE como los números 0, 1, 2, 3, 4, 5, 6 y 7 y que la
curva C de nivel 0 es un segmento E. Diseña un algoritmo
recursivo para encontrar la sucesión de direcciones que definen
la curva C de nivel N. Por ejemplo, si N = 2 las direcciones
serían N, E, E y S. Escribe un programa llamado curvacZZ (donde ZZ es una clave de dos
dígitos asignada por el profesor) basado en tu algoritmo
que acepte como entrada un entero N y que escriba como salida la
sucesión de números correspondiente a la curva C de nivel
N. Puedes suponer que 0 <= N <= 100.
| Ejemplo de entrada |
Ejemplo de salida |
| 2 |
2 0 0 6 |
Problema 2: 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 |
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.