1ª QUESTÃO - semana 16/05

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Considere um tabuleiro 3x4. Cada quadrado contém um número:

O objetivo do jogo consiste em deslocar sua peça do canto superior esquerdo até o canto inferior direito,através de uma sequência de movimentos para a direita ou para baixo, de forma de minimizar o somatório dos pontos correspondentes aos quadrados que você passou. 

O jogo pode ser descrito como um problema de caminho mínimo, onde cada quadrado tem sua posição correspondente, mostrado na figura abaixo:

Nessas condições, ao aplicarmos o algoritmo de Dijkstra para resolver o jogo, quantos nós (quadrados) pares não estarão no caminho ótimo ?

(a) 4

(b) 3

(c) 2

(d) 5

(e) NDA

Ideia original de: Lucas Miguel de Carvalho

2ª QUESTÃO - semana 16/05

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado:  Você está jogando um jogo online chamado DotA. Percebendo que você pode converter o mapa do jogo em um grafo com vértices representando as posições no mapa e as arestas os caminhos até eles, você observa que cada passagem no grafo provoca uma quantidade diferente de danos à você no jogo. É possível ainda alterar o grafo para usar pesos para representar os danos causados ​​por cada aresta. Você então, usa o algoritmo de Dijkstra para encontrar o caminho de A a H, com o menor dano possível. Anote a ordem em que os vértices são removidos da fila de prioridade ao executar o algoritmo de Dijkstra.

(a) A, B, D, C, F, E, G, H 

(b) A, B, C, D, F, E, G, H

(c) A, B, D, C, E, F, G, H

(d) A, B, C, D, E, F, G, H

(e) NDA

Ideia original de: Lucas Miguel de Carvalho