Tarea 4 de Diseño de Algoritmos
Trimestre 2010 Primavera
Entrega: 14 de junio de 2010 a las 22:00.
Problema
1: Sean N, P y Q tres
enteros positivos. Diseña un algoritmo de búsqueda con
retroceso 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 sumasiZZ
(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
|
Problema 2: 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: 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.