Tarea 3 de Diseño de Algoritmos
Trimestre 2008 Primavera
Entrega: 28 de julio de 2008 a las 22:00.
Problema
1: Sea N un entero positivo y sea R1, R2,
..., RN un vector de enteros con valores entre 1 y N.
Diseña un algoritmo de búsqueda
con retroceso que calcule la cantidad F de formas en que se
pueden colocar N torres en un tablero de ajedrez de N por N de modo que
no se ataquen entre sí y, para toda 1 <= I <= N,
está prohibido colocar una torre en el renglón RI
de la columna I. Por ejemplo si N = 3 y R = (1, 1, 3) entonces existen
F = 2 formas de llevar a cabo esta tarea: la primera con las torres en
los renglones (2, 3, 1) y la segunda con las torres en los renglones
(3, 2, 1). Escribe
un programa llamado torresZZ
(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 seguido de los N enteros R1, R2,
..., RN (con 1 <= N <= 10 y 1 <= RI
<= N) y la salida de tu programa será el entero F.
Página de prueba.
Ejemplo de
entrada
|
Ejemplo de
salida
|
3
1 1 3
|
2
|
Problema 2: 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.
Página de prueba.
| 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.