Universidade Federal do Espı́rito Santo - CT - DI
Trabalho Computacional - PD II - Engenharia de Computação
Profa. Claudia Boeres
Considere o esboço do estado do ES e n cidades enumeradas de 1, 2, . . . , n.
Na ilustração do mapa apresentado, consideramos n = 30. No entanto, o
número de cidades a serem consideradas no problema podem variar entre 15
e 30. Desta forma, o valor de n, os nomes das cidades e as suas respectivas
coordenadas x e y estão armazenadas no arquivo nome-coord.txt. Cada
estrada entre duas cidades possui um custo por quilômetro que deve ser
multiplicado pela distância para calcular o custo de viagem entre as cidades.
Além disso, o hotel em cada cidade possui um determinado valor para a
diária. Os valores das diárias e os custos por quilômetro estão armazenados
no arquivo diaria-custo.txt. Observe que a fórmula para o cálculo do custo
total de viagem mencionado nas questões seguintes é apresentada no item a)
de {Observações Importantes}.
Faça um programa na linguagem C para:
1. Ler o arquivo de dados nome-coord.txt
2. Ler o arquivo de dados diaria-custo.txt
3. Construir uma matriz Dn×n de distâncias entre todas as cidades e armazenar em um arquivo que se chamará distancia.txt
4. Construir uma matriz Cn×n de custos de viagem entre todas as cidades
e armazenar em um arquivo que se chamará custo.txt
5. Criar o arquivo saida.txt que deverá conter em cada linha, as respostas
dos itens 6, 7, 8 e 9 no seguinte formato:
linha
linha
linha
linha
1:
2:
3:
4:
respostas
respostas
respostas
respostas
do
do
do
do
item
item
item
item
6
7
8
9
separadas
separadas
separadas
separadas
por
por
por
por
espaços
espaços
espaços
espaços
em
em
em
em
branco
branco
branco
branco
6. Imprimir no arquivo saida.txt a(s) cidade(s) mais ao norte, mais ao
sul, mais a oeste, mais a leste e a mais central. Defina o critério para
encontrar a cidade mais central.
7. Construir (imprimir no arquivo saida.txt) o caminho da cidade 1 até
a cidade n, passando por todas as cidades na ordem 1 → 2 → 3 →
. . . → 29 → n. Calcular (imprimir no arquivo saida.txt) a distância
total deste caminho (usando a matriz D) e o custo total desta viagem
(usando a matriz C), considerando que o viajante dormirá uma noite
em cada cidade, exceto a cidade 1.
8. Construir (imprimir no arquivo saida.txt) um caminho da cidade 1
até a cidade n seguindo a lei de formação: a cidade seguinte no caminho é a mais próxima e de maior ordem que a atual, considerando as
cidades na ordem fornecida no arquivo nome-coord.txt e ilustradas
no gráfico. Exemplo: se estamos na cidade 10 a cidade seguinte será
uma cidade de maior ordem (por exemplo, a cidade 12 ou 15) e não
uma cidade de menor ordem (por exemplo, a cidade 8 ou 9). Se houver
empate com relação à distância, escolher a cidade de maior ordem. Calcular (imprimir no arquivo saida.txt) a distância total deste caminho
e o custo total desta viagem.
9. Construir (imprimir no arquivo saida.txt) um caminho da cidade 1
até a cidade n seguindo a lei de formação: a cidade seguinte no caminho é a menos custosa e e de maior ordem que a atual, considerando as
cidades na ordem fornecida no arquivo nome-coord.txt e ilustradas
no gráfico. Se houver empate com relação ao custo, escolher a cidade
de maior ordem. Calcular (imprimir no arquivo saida.txt) a distância
total deste caminho e o custo total desta viagem.
10. Considere que a empresa de transporte de carga VIAJECOMPAZ possui um centro de armazenamento de carga na cidade 10. O centro tem
que ser abastecido com a carga necessária à demanda das solicitações
das cidades do estado. Essa carga chega ao Espı́rito Santo na cidade 1
e a empresa VIAJECOMPAZ é responsável pela sua distribuição para
as cidades de 1 a 10 e abastecer o centro de armazenamento na cidade
10. As demais cidades do estado (11 a 30) não utilizam esta empresa
e se responsabilizam por buscar no centro de armazenamento a carga
solicitada. Devido à economia de custos e à possibilidade de interdições
de estradas, a empresa VIAJECOMPAZ deseja fazer um estudo dos k
(o valor de k deve ser lido pelo teclado) menores caminhos existentes entre as cidades 1 e 10 e que passem por todas as cidades entre
elas (2 a 9), calculando a distância total de cada caminho. Para isso,
deve-se escrever em um arquivo chamado caminhos.txt, as seguintes
informações:
• o número k de caminhos construı́dos
• a lista com todos os k caminhos calculados e suas respectivas
distâncias ordenadas em ordem crescente.
Observações importantes:
a) Para calcular o custo de viagem entre as cidades i e j, utilize a expressão:
CVij = cij × dij + diariaj
b) Os arquivos de dados nome-coord.txt e diaria-custo.txt estarão disponı́veis na página da disciplina (www.inf.ufes.br/~pet)
c) Data de Entrega: O trabalho deverá ser entregue até às 23:59 horas
do dia 28/11/2008 (sexta-feira).
A seguir, o esboço do ES com as n = 30 cidades.
27
30
26
29
25
25
24
24
23
26
28
22
23
21
21
20
27
22
20
19
18
19
17
18
16
16
15
17
14
13
15
12
10
11
14
9
10
13
8
9
11
12
8
7
7
6
1
6
5
5
4
4
2
3
3
2
1
1
2 3
4
5 6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
Forma de Entrega:
1. Compacte o arquivo texto (o nome do arquivo DEVE ser caminho.c)
com o código fonte do programa do seu trabalho e envie o arquivo
compactado para o e-mail [email protected]. O nome do arquivo
compactado deverá ser trab2.zip (por favor, não enviem .rar)
2. O assunto do e-mail deverá ser o seguinte (somente o que está entre aspas duplas): ”pd2:trab2:nome1:nome2”, onde nome1 e nome2 (máximo
2 componentes) são os nomes dos integrantes do grupo. Substitua
nome1 (e demais) pelo primeiro nome e último sobrenome, separados
por espaços. Compacte o arquivo fonte utilizando o programa (ou comando) zip e envie o arquivo compactado em anexo. Ressaltamos que
o arquivo trab2.zip gerado deverá conter apenas o arquivo com o código
fonte do seu trabalho (não podem ter arquivos executáveis ou qualquer
outro arquivo)
3. O recebimento dos trabalhos é automatizado. Siga as instruções à
risca pois algum erro na submissão pode inviabilizar a entrega do seu
trabalho. Não deixe para enviar seu trabalho nos momentos finais de
seu prazo. É comum a ocorrência de problemas em virtude de erros na
submissão. Logo, enviem com algumas horas de antecedência para que
haja tempo hábil para eventuais correções
Veja abaixo um exemplo de um e-mail de envio do trabalho do grupo formado por João da Silva e José Geraldo Castro (enviado por João da Silva).
Apenas um integrante do grupo envia o trabalho. Não use acentos, cedilhas
ou qualquer outro caractere especial.
Para: [email protected]
De: Joao da Silva
Assunto: pd2:trab2:Joao Silva:Jose Castro
Anexo: trab2.zip
Atenção:
1. No assunto, a disciplina (pd2) e a identificação do trabalho (trab2)
devem ser escritos todos em letras minúsculas
2. NÃO escreva o seu nome com caracteres estendidos (ã, ç, é, etc)
3. Apenas um mail por trabalho deve ser enviado
Outras Observações Importantes:
1. Os trabalhos serão verificados automaticamente por uma ferramenta de
detecção de plágio. Em caso de deteção de cópia (parcial ou integral),
todos os envolvidos recebem nota ZERO. Em outras palavras, tanto os
alunos que copiaram quanto os que deixaram copiar recebem ZERO
2. Enviem o trabalho no prazo especificado e no formato especificado.
Trabalhos recebidos fora do prazo ou em formato inadequado recebem
nota ZERO
3. O trabalho deve ser enviado estritamente para o e-mail especificado
acima
4. Trabalho que não compila recebe nota ZERO. Não adianta submeter
5. Os trabalhos serão compilados e verificados usando o compilador gcc
no sistema operacional Linux
6. Os programas serão avaliados pela sua correção durante a execução e
também pelo estilo de programação. Serão observados particularmente
se os programas possuem os comentários apropriados, se usam nomes
significativos para as variáveis e funções, se o código está indentado
corretamente e se utilizam modularização sempre que possı́vel e apropriado