PDF de programación - Práctica 8. Algoritmo Voraz. Juego de la Oca

Práctica 8. Algoritmo Voraz. Juego de la Oca



Objetivos



Practicar el diseño e implementación de algoritmos basados en el esquema “voraz”.


Algoritmo del “Juego de la Oca”

Disponemos de un tablero de juego que consta de n casillas consecutivas (tipo juego de la oca).
Cada casilla tiene asociado un valor entero, que puede ser positivo o negativo. Los jugadores
parten de una casilla de salida, que no tiene asociado ningún valor. Para avanzar a través de las
casillas, el jugador realiza sucesivas tirada de un dado (de 6 caras). El juego termina cuando el
jugador sobrepasa la casilla n. La puntuación obtenida por cada jugador es igual a la suma de
los valores asociados a las casillas en las que el jugador ha ido cayendo con las tiradas del dado.
El propósito del juego es obtener la mayor puntuación posible.

Se pide

 Diseñar un algoritmo voraz que encuentre una secuencia de tiradas con la mejor

puntuación posible.

 Aplicar el algoritmo al siguiente ejemplo: n= 15, Tablero= {1, 3, 5, -4, -3, 8, 2, -1, -8,

-1, -7, -2, -6, -3, 2}.

 El algoritmo diseñado, ¿garantiza la solución óptima?. En caso de que no sea optima,

demostrar que no lo es mediante el uso de contraejemplos.

 Probar con distintas funciones de selección, intentando buscar una función de selección

que mejore el algoritmo incial.