Tarea 4 de Diseño de Algoritmos
Trimestre 2012 Primavera
Entrega: 6 de junio de 2012 a las 22:00.
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 acabaZZ
(donde ZZ es una clave de
dos
dígitos asignada por el profesor) 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.
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: 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.