PUC-Rio
Departamento de Informática
Profs. Marcus Vinicius S. Poggi de Aragão
Período: 2004.2
Horário: 3as-feiras e 5as-feiras de 15-17
25 de novembro de 2004
Data da Entrega: 16 de dezembro de 2004

ESTRUTURAS DISCRETAS (INF 1631)

1^o Trabalho de Implementação

Descrição

Este trabalho prático consiste em desenvolver um código para resolver o problema descrito abaixo. O desenvolvimento deste código deve seguir o seguinte roteiro:

Demonstrar o entendimento do problema, explicando em detalhe o resultado que o algoritmo deve obter.
Descrever o algoritmo proposto para a sua resolução.
Explicar a fundamentação do algoritmo e justificar a sua corretude. Preferencialmente, prove por indução matemática (no caso, indicando qual o reforço de hipótese feito) que o algoritmo obtém a resposta desejada.
Documente o arquivo contendo o código fonte de modo que cada passo do algoritmo esteja devidamente identificado e deixe claro como este passo é executado.

A descrição do problema, abaixo, contém a especificação do arquivo de entrada e da saída desejada. A corretude código será testada sobre um arquivo de entrada que será distribuido após a entrega do trabalho. O trabalho entregue deve conter:

Um documento contendo o roteiro de desenvolvimento do algoritmo (e do código), comentários e análises sobre a implementação e os testes realizados (papel).
A impressão do código fonte (papel).
Um e-mail ou disquete contendo o código fonte e o executável correspondente (no caso do e-mail é obrigatório o uso do assunto (ou subject) ED042T2).

Walk of a King

Considere um tabuleiro de xadrez e um rei que está inicialmente na posição (1,1) (as posições do tabuleiro são representadas por (i,j) onde 1 £ i £ 8 e 1 £ j £ 8). Para cada posição do tabuleiro estão associados um prêmio p_ij e um consumo q_ij (o prêmio pode ser em USD(!!) e o consumo em litros de gasolina, por exemplo). Os prêmios e os consumos assumem somente valores positivos. O rei tem inicialmente Q unidades para consumir e pode passar quantas vezes quiser em cada posição do tabuleiro e a cada vez receber o prêmio e, naturalmente, consumir os seus recursos. Ao final (do passeio) o rei tem que estar de volta na posição (1,1).

Apresente um algoritmo para determinar o caminho que o rei deve fazer para obter o maior total possível em prêmios.
Desenvolva um código para o seu algoritmo e teste para um arqivo de dados com a estrutura apresentadas abaixo.

Descrição do Arquivo de Entrada

A primeira linha contém um inteiros Q que indica o número de unidades que o rei tem para consumir. Seguem dois blocos de 8 linhas cada uma com 8 inteiros positivos. O primeiro bloco corresponde ao consumo de cada posição do tabuleiro, enquanto que o segundo bloco corresponde ao prêmios atribuídos às posições.

A posição (1,1) é a primeira da oitava linha de cada bloco. Na mesma linha se encontram as posições (1,2), (1,3), ..., (1,8). A primeira linha de cada bloco contém valores referentes às posições (8,1), (8,2), ..., (8,8). Naturalmente esta linha é seguida pela linha (7,1), (7,2), ..., (7,8) e assim por diante.

O arquivo de dados possui múltiplas instâncias e termina quando o valor de Q é zero.

Descrição do Arquivo de Saída

Para cada entrada do arquivo acima você deve imprimir o maior prêmio possível, o total consumido, o valor de Q e a sequência de posições correspondente à caminhada do rei.

This document was translated from L^AT_EX by H^EV^EA.