Problema 1: Diseñe un algoritmo usando la técnica de programación dinámica para resolver el siguiente problema: Dados dos enteros positivos N y K encuentre la cantidad F de formas distintas en que se puede escribir N como suma de K enteros positivos. Considere que dos formas son idénticas si sólo difieren en el orden de sus sumandos. Por ejemplo, si N = 7 y K = 3 entonces F = 4 debido a que 7 = 1 + 1 + 5 = 1 + 2 + 4 = 1 + 3 + 3 = 2 + 2 + 3. Escriba un programa llamado pdksumZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) basado en su algoritmo que acepte como entrada dos enteros positivos N y K y que escriba como sallida el número F. Puede suponer que 1 <= K <= N <= 100.
| Ejemplo de entrada |
Ejemplo de salida |
| 7 3 |
4 |
Problema 2: Sean N, P y Q tres enteros positivos. Diseña un algoritmo de programación dinámica que calcule la cantidad S de formas en que se puede obtener el valor N sumando enteros distintos entre P y Q. Dos sumas se consideran idénticas si sólo difieren en el orden de sus sumandos. Por ejemplo, si N = 12, P = 3 y Q = 7 entonces S = 2 porque 12 se puede obtener de las siguientes formas: 3+4+5 y 5+7. Escribe un programa llamado sumapdZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que implemente tu algoritmo. La entrada a tu programa serán los tres enteros N, P y Q (con 1 <= P <= Q <= N <= 1000) y la salida de tu programa será el entero S.
| Ejemplo de entrada |
Ejemplo de salida |
| 12 3 7 |
2 |
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.