Enviado em 16/06/2006 - 14:17h
Iai galera da comu ... blza ?/
Bom, preciso da ajuda de vcs que manjam de C, tenho prova de programação na quarta e preciso que me enviem os códigos do seguintes exercícios para que eu possa estudar baseado neles .... peço a colaboração de vcs já que ainda sou iniciante na linguagem e pelo pouco tempo de preparação para a prova ...
Considere n cidades numeradas de 0 a n-1 que estão interligadas por uma série de estradas de mão única. As ligações entre as cidades são representadas pelos elementos de uma matriz quadrada Lnxn, cujos elementos lij assumem o valor 1 ou 0, conforme exista ou não estrada direta que saia da cidade i e chegue à cidade j. Assim, os elementos da linha i indicam as estradas que saem da cidade i, e os elementos da coluna j indicam as estradas que chegam à cidade j.
Por convenção lii = 1. A figura mostra um exemplo para n = 4.
| 1 1 1 0 | |----->-----|->-|
L= | 0 1 1 0 | 0 --> 1 --> 2 3
| 1 0 1 1 | |-----<-----|-<-|
| 0 0 1 1 |
OBS : Estas duas definições acima foram colocadas manualmente pois elas estavam em formato de imagem e não deu pra colocá-las, então coloquei de forma manual .... sendo que a primeira representa uma matriz e a segunda as ligações possíveis: 0 pra 1, 1 pra 2, 2 pra 3, 3 pra 2, 2 pra 0 e 0 pra 2, estas ligações são apenas pra exemplificar a forma de resolução do problema .
ITENS À FAZER
(a) Dado k, determinar quantas estradas saem e quantas chegam à cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
i. As cidades isoladas, isto é, as que não têm ligação com nenhuma outra;
ii. As cidades das quais não há saída, apesar de haver entrada;
iii. As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e n-1, verificar se é possível realizar o roteiro correspondente. No exemplo dado, o roteiro representado pela seqüência (m=5) 2 3 2 1 0 é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p pelas estradas existentes. Você consegue encontrar o menor caminho entre as duas cidades?
h) Dado k, determinar se é possível, partindo de k, passar por todas as outras cidades apenas uma vez e retornar a k.
Sugestões:
i. Pule esse item.
ii. Teste todas as possibilidades.
Agradeço pela colaboração de todos ..
Aguardo respostas.
Bom, preciso da ajuda de vcs que manjam de C, tenho prova de programação na quarta e preciso que me enviem os códigos do seguintes exercícios para que eu possa estudar baseado neles .... peço a colaboração de vcs já que ainda sou iniciante na linguagem e pelo pouco tempo de preparação para a prova ...
Considere n cidades numeradas de 0 a n-1 que estão interligadas por uma série de estradas de mão única. As ligações entre as cidades são representadas pelos elementos de uma matriz quadrada Lnxn, cujos elementos lij assumem o valor 1 ou 0, conforme exista ou não estrada direta que saia da cidade i e chegue à cidade j. Assim, os elementos da linha i indicam as estradas que saem da cidade i, e os elementos da coluna j indicam as estradas que chegam à cidade j.
Por convenção lii = 1. A figura mostra um exemplo para n = 4.
| 1 1 1 0 | |----->-----|->-|
L= | 0 1 1 0 | 0 --> 1 --> 2 3
| 1 0 1 1 | |-----<-----|-<-|
| 0 0 1 1 |
OBS : Estas duas definições acima foram colocadas manualmente pois elas estavam em formato de imagem e não deu pra colocá-las, então coloquei de forma manual .... sendo que a primeira representa uma matriz e a segunda as ligações possíveis: 0 pra 1, 1 pra 2, 2 pra 3, 3 pra 2, 2 pra 0 e 0 pra 2, estas ligações são apenas pra exemplificar a forma de resolução do problema .
ITENS À FAZER
(a) Dado k, determinar quantas estradas saem e quantas chegam à cidade k.
(b) A qual das cidades chega o maior número de estradas?
(c) Dado k, verificar se todas as ligações diretas entre a cidade k e outras são de mão dupla.
(d) Relacionar as cidades que possuem saídas diretas para a cidade k.
(e) Relacionar, se existirem:
i. As cidades isoladas, isto é, as que não têm ligação com nenhuma outra;
ii. As cidades das quais não há saída, apesar de haver entrada;
iii. As cidades das quais há saída sem haver entrada.
(f) Dada uma seqüência de m inteiros cujos valores estão entre 0 e n-1, verificar se é possível realizar o roteiro correspondente. No exemplo dado, o roteiro representado pela seqüência (m=5) 2 3 2 1 0 é impossível.
(g) Dados k e p, determinar se é possível ir da cidade k para a cidade p pelas estradas existentes. Você consegue encontrar o menor caminho entre as duas cidades?
h) Dado k, determinar se é possível, partindo de k, passar por todas as outras cidades apenas uma vez e retornar a k.
Sugestões:
i. Pule esse item.
ii. Teste todas as possibilidades.
Agradeço pela colaboração de todos ..
Aguardo respostas.