Diseño de Algoritmos - Primer Examen

NOMBRE:	__________________________________________ MATRICULA: __________

INSTRUCCIONES: Conteste cada una de las siguientes preguntas. Puede 
auxiliarse de programas de computadora pero no necesita entregarlos.

PREGUNTA 1: Considere la definición recursiva de la función Z(n) dada 
por Z(2n) = Z(n) * (Z(n+1) + Z(n)), Z(2n+1) = Z(n)^2 + Z(n+1)^2, además 
de Z(1) = 1 y Z(2) = 1. Calcule el valor de Z(n) y diga cuántas llamadas 
recursivas se necesitaron para cada uno de los siguientes valores de n:

n		2	3	5	9	17	33

Z(n)		_1_	___	___	___	___	___

# de llamadas	_1_	___	___	___	___	___

Evaluación: 0.5 puntos por cada valor correcto. TOTAL: ___


PREGUNTA 2: Considere la definición recursiva de la función A(n) dada 
por A(0,y) = 1 para toda y >= 0, A(1,0) = 2, A(x,0) = x+2 para x >= 2 
además de A(x,y) = A(A(x-1,y),y-1) en los demás casos. Llene la tabla:

A(x,y)	x=0	x=1	x=2	x=3	x=4	x=5	x=6

y=0	_1_	_2_	___	___	___	___	___

y=1	_1_	___	___	___	___	___	___

y=2	_1_	___	___	___	___	___	___

y=3	_1_	___	___	___	___	___	___

Evaluación: 0.25 puntos por cada valor correcto. TOTAL: ___


PREGUNTA 3: Sea M(n) el número mínimo de multiplicaciones que se deben 
hacer para calcular x^n, y sea D(n) el número mínimo de multiplicaciones 
y divisiones que se deben hacer para calcular x^n. Calcule M(n) y D(n) 
para todos los valores de n <= 7 y llene la siguiente tabla:

n	0	1	2	3	4	5	6	7

M(n)	_0_	_0_	_1_	___	___	___	___	___

D(n)	_0_	_0_	_1_	___	___	___	___	___

Evaluación: 0.5 puntos por cada valor correcto. TOTAL: ___


CALIFICACION FINAL: ___