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. Diseña un algoritmo de programación dinámica que calcule el valor de A(N). Escribe un programa llamado tipicoZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que implemente tu algoritmo. La entrada a tu programa será un entero N (con 1 <= N <= 1,000,000) y la salida de tu programa será el entero A(N).
| Ejemplo de entrada |
Ejemplo de salida |
| 5 |
13 |
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. Diseña un algoritmo de programación dinámica que calcule el valor de B(N). Escribe un programa llamado divideZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que implemente tu algoritmo. La entrada a tu programa será un entero N (con 1 <= N <= 1,000,000) y la salida de tu programa será el entero A(N).
| Ejemplo de entrada |
Ejemplo de salida |
| 6 |
3 |
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.