PDF de programación - Práctica 10. Algoritmo Vuelta Atrás. Juego de la Oca

Práctica 10. Algoritmo Vuelta Atrás. Juego de la Oca



Objetivos

•

Practicar el diseño e implementación de algoritmos basados en el esquema “vuelta

atrás”.


Utilizando el mismo enunciado de la practica 8 en el que se describía en funcionamiento de
nuestro “juego de la Oca”
Se pide


• Diseñar un algoritmo de tipo vuelta atrás que nos indique la mejor puntuación posible.
Para ello, deberemos probar TODAS las posibilidades a la hora de recorrer el tablero.

• Como sabemos, el algoritmo voraz de la practica 8 no era optimo. ¿Este lo es?. Justifica

si lo es. Si no lo fuera, poner contraejemplos que lo corroboren.

• Poner un tablero de ejemplo, si es que existe, donde se compruebe que el algoritmo de

vuelta atrás es mejor que el voraz.

• Comparar el rendimiento del algoritmo diseñado con el voraz de la practica 8, viendo

cual de los dos es más eficiente. Para ello aplicaremos ambos algoritmos sobre diversos
tableros aleatorios de distintos tamaños y mediremos los tiempos. Plasmar los
resultados en una tabla.

• Modificar el algoritmo diseñado para que no devuelva la mejor puntuación obtenida,

sino la SECUENCIA de TIRADAS necesarias para obtener dicha puntuación máxima.

• Como es evidente, probar TODAS las posibilidades de recorrer el tablero de juego

puede ser una tarea ardua y costosa en tiempo. Mejorar el algoritmo anterior
descartando aquellas secuencias que no se consideren prometedoras.