Tarea 4 de Diseño de Algoritmos

Trimestre 2012 Otoño
Entrega: 19 de octubre de 2012 a las 22:00.

Problema 1 [5 puntos]: 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

Problema 2 [5 puntos]: Sea N un entero positivo. Una permutación P del 1 al N es un arreglo P[1], P[2], ..., P[N] que contiene cada entero del 1 al N exactamente una vez. Un punto fijo de una permutación P del 1 al N es un entero I tal que P[I] = I. Diseña un algoritmo de búsqueda con retroceso que encuentre todas las permutaciones del 1 al N que no tienen puntos fijos. Por ejemplo, si N = 4 entonces hay 9 permutaciones sin puntos fijos que son [2, 1, 4, 3], [2, 3, 4, 1], [2, 4, 1, 3], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1], [4, 1, 2, 3], [4, 3, 1, 2] y [4, 3, 2, 1]. Escribe un programa llamado nofijoZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) basado en tu algoritmo que acepte como entrada un entero N y que escriba como salida la cantidad de permutaciones del 1 al N sin puntos fijos. Puedes suponer que 0 < N < 32.

Ejemplo de entrada Ejemplo de salida
4
 9

Notas: Sus 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.