UEA: Diseño de Algoritmos
Trimestre: 2006 Invierno
Fecha: 17 de febrero de 2006

Instrucciones: Conteste cada una de las siguientes preguntas. Puede auxiliarse de programas de computadora (y en ese caso use el tipo unsigned long long int de C o equivalente de al menos 64 bits en el lenguaje de su elección) pero no necesita entregarlos. Envíe sus respuestas usando pine a franz.

Problema 1: Si X es un número real, el piso(X) es el mayor entero P tal que P <= X y el techo(X) es el menor entero T tal que X <= T. Considere la función recursiva A(N) definida como A(1) = 1 y A(N) = A(piso(N/2))+A(techo(N/2))+N-1 para toda N >= 2. Calcule A(N) para los valores de N en el conjunto {3, 31, 314, 3141, 31415}. Evaluación: 1 punto por cada respuesta correcta.

Problema 2: Considere la función recursiva B(N) definida como B(1) = 1 y para N >= 2, B(N) es la suma de las B(D) tales que D < N y D divide a N. Calcule B(N) para los valores de N en el conjunto {2, 27, 271, 2718, 27182}. Evaluación: 1 punto por cada respuesta correcta.

Problema 3: Considere la función recursiva C(N) definida como C(1) = 1 y C(N) = C(1)*C(N-1) + C(2)*C(N-2) * ... + C(N-1)*C(1) para N >=2. Calcule C(N) para los valores de N en el conjunto {4, 16, 64, 256, 1024}. Evaluación: 1 punto por cada respuesta correcta.