Tarea 3 de Análisis y Diseño de Algoritmos
Trimestre 2013 otoño
Entrega: 16 de septiembre de 2013 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 o C++ 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 <= 20.
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 o C++ 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 <= 20.
Nota: Sus programas no deben
leer ni escribir nada adicional a lo que se indica en el enunciado.
