Tarea 3 de Diseño de Algoritmos
Trimestre 2012 Otoño
Entrega: 10 de octubre de 2012 a las 22:00.
Problema 1 [5 puntos]:
Sea N un entero
positivo y sea D1, D2,
..., DN 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 si RI es divisible entre DI.
Por
ejemplo si N = 4 y D = (2, 2, 3, 3) entonces existen
F = 4 formas de llevar a cabo esta tarea: la primera con las torres
en
los renglones (1, 3, 2, 4), la segunda con las torres en los
renglones
(1, 3, 4, 2), etc. Escribe
un programa llamado divtorZZ
(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 D1, D2,
...,
DN (con 1 <= N <= 10 y 1 <= DI
<= N) y la salida de tu programa será el entero F.
Ejemplo de entrada
|
Ejemplo de salida
|
4
2 2 3 3 |
4 |
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.