Problema 1: 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 |
Problema 2: Sea N un entero
positivo y considera un tablero de ajedrez de N por N donde al cuadrito
de coordenadas (I,J) le ha sido asignado un costo C[I,J]. Se desea
colocar N torres en el tablero de modo que
no se ataquen entre sí y la suma de los costos de los cuadritos
donde se colocan sea la mínima posible. Diseña un
algoritmo de búsqueda
con retroceso que encuentre una forma de colocar las torres
sujeta a estas condiciones. Por ejemplo, si N = 3 y los costos son como
se indica en el ejemplo entonces si colocas las torres en los renglones
R = (2, 1, 3) obtienes un costo de S = 3. Escribe
un programa llamado mintorZZ
(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 una matriz C de N
renglones y N columnas (con 1 <= N <= 10 y 0 <= C[I,J] <=
9) y la salida de tu programa será el entero S seguido del
vector R. Nota: para este
problema puede haber muchos vectores R que tienen el mismo costo
mínimo, sólo debes presentar un vector (cualquiera que
cumpla las condiciones será considerado como correcto).
| Ejemplo de entrada |
Ejemplo de salida |
| 3 1 1 2 1 3 3 2 1 1 |
3 2 1 3 |
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.