Pda 2007

Fundação CECIERJ - Vice Presidência de Educação Superior a Distância

Curso de Tecnologia em Sistemas de Computação
Disciplina: Projeto e Desenvolvimento de Algoritmos
Gabarito
AD1 2° semestre de 2007.

1ª questão (5.0 pontos): Jogo de Tabuleiro
Um jogo divertido consiste de um tabuleiro contendo uma trilha de quadrados e um conjunto de peças coloridas. No início do jogo cada jogador recebe uma peça; todas as peças são inicialmente posicionadas imediatamente antes do primeiro quadrado da trilha. O jogo progride em turnos. Em cada turno, jogadores jogam um par de dados, e movem suas peças para frente. As peças são movidas sempre para frente pelo número de quadrados correspondente à soma dos pontos obtidos nos dados. A maioria dos quadrados da trilha é normal, mais alguns são armadilhas. Se a peça de um jogador, ao final de um movimento, cai em uma armadilha, ele perde a vez de jogar no próximo turno. Ou seja, ele não joga os dados e sua peça fica um turno sem ser movimentada. Há sempre três armadilhas na trilha do tabuleiro conforme mostra a Figura 1. A ordem em que os jogadores jogam os dados, nos turnos, é sempre a mesma (jogador 1, depois jogador 2 etc.), a menos que algum jogador tenha caído em uma armadilha.

Figura 1: Exemplo de um tabuleiro do jogo.
O vencedor do jogo é o jogador cuja peça alcança primeiro o final da trilha. O final é após o último quadrado da trilha. Considere, por exemplo, o tabuleiro mostrado na Figura 1, cujos quadrados são numerados de 1 a 48. No início do jogo, as peças são posicionadas no local marcado "Início" na Figura, ou seja, antes do quadrado número 1. Portanto, se um jogador obtém um resultado 7 na soma dos valores dos dados, sua peça é posicionada no quadrado número 7 ao final do primeiro turno do jogo. Além do mais, se a peça de um jogador está posicionada no número 41, o jogador necessita de um resultado pelo menos igual a 8 nos dados para alcançar o final da trilha e vencer o jogo. Note que não há