Tarea 5 de Diseño de Algoritmos
Trimestre 2013 Otoño
Entrega: 30 de septiembre de 2013 a las 22:00.
Problema 1:
Diseñe un
algoritmo usando la técnica de búsqueda con retroceso
para resolver el siguiente problema: Sea N un entero positivo y
considere un tablero de ajedrez de N por N en el que se desean
colocar
reinas idénticas
de forma tal que éstas ataquen todas las posiciones del
tablero (no
importa si las reinas se atacan entre sí o no). Su
algoritmo deberá encontrar el mínimo
número K de reinas que satisfacen esta condición y
deberá calcular el número F de formas distintas se puede
realizar. Observe que K <= N. Por ejemplo, si N = 2 entonces K =
1 y
F = 4. Escriba un programa llamado ataca basado en su algoritmo
que acepte como entrada el entero positivo N y que escriba como
salida
los números K y F en ese orden. De nuevo, si la entrada fuera 2 entonces la salida debe
de
ser 1 4. Puede suponer
que 1 <= N <= 20.
Ejemplo de
entrada
|
Ejemplo de
salida
|
| 2 |
1 4
|
Problema 2: Diseñe un
algoritmo usando la técnica de búsqueda con retroceso
para resolver el siguiente problema: Dados tres enteros positivos N,
A
y B considere un tablero de ajedrez de N por N en el que hay un
caballo
en la posición (1, 1) que se quiere hacer llegar a la
posición (N, N). Este caballo puede brincar A cuadros en
cualquier dirección paralela a los lados del tablero y luego B
cuadros en cualquier dirección perpendicular a la anterior (un
caballo del juego de ajedrez normal tiene A = 2 y B = 1). Su
algoritmo
deberá encontrar el mínimo número P de pasos que
se necesitan para lograr el objetivo. Observe que P <= N2.
Por ejemplo, si N = 4, A = 1 y B = 2 entonces P = 2. Escriba un
programa llamado acaba
basado en su algoritmo que acepte como entrada tres enteros
positivos
N, A y B en ese orden y que escriba como salida el número P. De
nuevo, si la entrada fuera 4
1 2
entonces la salida debe de ser 2.
Puede suponer que 1 <= N <= 20, que 1 <= A <= N, que 1
<= B <= N y que el objetivo se puede lograr.
| Ejemplo de
entrada |
Ejemplo de
salida |
4 1 2
|
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.