 |
 |
PUCRS
Faculdade de Informática
Programação para Engenharia II
Caminhos entre Cidades
Descrição |
O objetivo deste trabalho é criar um programa que informe os caminhos possíveis entre duas cidades escolhidas pelo usuário.
Ao iniciar, o programa deve ler um arquivo que define cada caminho possível entre duas cidades quaisquer. Por exemplo:
SaoBorja SaoLuizGonzaga
SaoBorja Santiago
SaoLuizGonzaga CerroLargo
CerroLargo SantaRosa
SaoLuizGonzaga SantaRosa
SantaRosa Girua
CerroLargo Girua
CerroLargo SantoAngelo
Girua SantoAngelo
SantaRosa TresDeMaio
TresDeMaio Horizontina
TresDeMaio TresPassos
TresDeMaio SantoAugusto
TresPassos SantoAugusto
SantoAgusto Ijui
SaoLuizGonzaga Ijui
Ijui Panambi
Panambi PalmeiraDasMissoes
TresDeMaio PalmeiraDasMissoes
PalmeiraDasMissoes FredericoWestphalen
FredericoWestphalen Sarandi
Sarandi Carazinho
Panambi Carazinho
Carazinho PassoFundo
Sarandi PassoFundo
Panambi CruzAlta
Ijui CruzAlta
CruzAlta JulioDeCastilhos
Carazinho Soledade
PassoFundo Soledade
Soledade SantaCruzDoSul
JulioDeCastilhos SantaMaria
SantaMaria SantaCruzDoSul
SantaMaria SaoPedroDoSul
SaoPedroDoSul SaoFranciscoDeAssis
SaoFranciscoDeAssis Santiago
Estas informações foram extraídas a partir do mapa do Estado (veja abaixo). Posteriormente será fornecido um arquivo mais extenso.
Após a leitura, o programa deve exibir ao usuário uma lista em ordem alfabética de todas as cidades existentes no arquivo, sem repetição.
A seguir, o programa deve perguntar ao usuário a cidade de origem e a de destino e mostrar pelo menos um dos caminhos existentes entre elas. O caminho solicitado pode não ser 'direto', ou seja, o programa deve mostrar as cidades por onde se deve passar para ir da cidade origem até a destino.
Aspectos
Técnicos
|
Deve ser implementada uma classe para representar a estrutura de dados, e que permita a realização de consultas sobre ela. Uma forma simples de implementar isso é através de uma matriz bidimensional, onde as linhas representam as cidades de origem e as colunas representam as cidades de destino. Onde houver um caminho entre uma cidade e outra, deve-se colocar uma marca (ex: um número diferente de zero, ou um boolean) na célula correspondente da matriz. Dessa forma, para saber se existe um caminho entre uma cidade A e uma cidade B, basta localizar a intersecção delas na matriz e verificar se a marca está presente.
Por exemplo, imaginando uma matriz com 4 cidades:
| Carazinho | CruzAlta | Ijui | Panambi | |
| Carazinho | X | |||
| CruzAlta | X | |||
| Ijui | X | |||
| Panambi | X |
A classe que representa a estrutura de dados deve ter métodos para:
- Incluir um par de cidades: recebe os nomes da cidade de origem e da cidade de destino, atualiza a matriz.
- Consultar se existe uma ligação entre duas cidades: recebe os nomes da cidade de origem e da cidade de destino e retorna um valor informado se existe ou não.
Programa deve ter ainda duas outras classes:
- uma que permita pesquisar um caminho, dados os nomes de uma cidade de origem e de uma cidade de destino. Este caminho deve ser impresso na tela.
- uma que mantenha uma lista com os nomes das cidades e permita imprimi estes nomes em ordem alfabética.
Veja dicas de implementação nesta página.
Entrega
|
O trabalho deverá consistir de um único arquivo .cpp. Esse arquivo deverá ser enviado para o email do professor até o dia 01/07/2008.
Não serão aceitas entregas fora do prazo.
Cópia de trabalhos caracteriza fraude escolar e nesse caso, todos os envolvidos terão a sua nota anulada.
Data de Entrega |