Problema 1: Escribe un
programa llamado pfijoZZ
(donde ZZ es la clave de
dos
dígitos asignada por el profesor) basado en un algoritmo de
divide y vencerás para resolver el problema del punto fijo del
examen (que a su vez es similar al de la búsqueda binaria). Tu
programa debe leer un entero N y un vector A = (A1, A2,
..., AN) con N enteros positivos tales que A1
< A2 < ... < AN y debe escribir dos
enteros M y P, donde M = AM y P es el número de
preguntas que se hicieron para encontrar M. Por ejemplo si N = 5 y A =
(1, 2, 4, 8, 16) entonces tu algoritmo debe preguntar primero en la
posición 3 y después preguntará en la
posición 1, encontrando un 1 y terminando. Puedes suponer que 1
<= N <= 1,000,000 y que 0 < A1 < A2
< ... < AN < 1,000,000,000. También puedes
suponer que siempre habrá al menos un punto fijo.
| Ejemplo de entrada |
Ejemplo de salida |
| 5 1 2 4 8 16 |
1 2 |
Problema 2: Diseñe un algoritmo usando la técnica de búsqueda con retroceso 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 ksumaZZ (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 |
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.