Tarea 1 de Diseño de Algoritmos
Trimestre 2007 Primavera
Entrega: 7 de mayo de 2007 a las 22:00.
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:
Problema
1: 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ñe 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. Escriba un programa en C (gcc), C++ (g++), Pascal (fpc) o Java (gcj) llamado curvadZZ (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 la
sucesión de números correspondiente a la curva C de nivel
N. De nuevo, si la entrada fuera 2
entonces la salida debe ser 2 0
0 6. Puede suponer que 0 <= N <= 100.
Problema 2: Ahora suponga que
se definen los giros de 0, 90, 180 y 270 grados (en la dirección
de las manecillas del reloj) como los números 0, 1, 2 y 3.
Observe que la curva C de nivel 0 no tiene giros y que la curva C de
nivel 1 tiene sólo un giro de 90 grados. Diseñe un
algoritmo recursivo para encontrar la sucesión de giros que
definen la curva C de nivel N. Por ejemplo, si N = 2 los giros
serían de 90, 0 y 90 grados. Escriba un programa en C (gcc), C++ (g++), Pascal (fpc) o Java (gcj) llamado curvagZZ
(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 la sucesión de números
correspondiente a la curva C
de nivel N. De nuevo, si la entrada fuera 2 entonces la salida debe ser 1 0 1. Puede suponer que 0
<= N <= 100.
Nota: Sus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado.
