Matrizes - C - Portugal-a-Programar
Por action, 11 de Dezembro de 2007 em C
float **Alocarmatriz (int m, int n)
int   i;    /* variavel auxiliar      */
for ( i=0; i<m; i+2 ) {
float **Liberarmatriz (int m, int n, float **v)
for (i=0; i<m; i++) free (v[i]);
int n,fact,z;
printf("introduza o numero de cidadees a visitar");
/*alocaçao de linhas na matriz*/
mat = (float **)calloc(n, sizeof(float *));
mat[z] = (float *)calloc(n, sizeof(float));
printf("introduza a dintancia de %c a %c:\n",ch,ch+2);
mat=Alocarmatriz (l,c);
Tenho aqui um duvida, o k e preciso para comexar a inserir os dados na matriz??
e k nao ta a correr e nao sei porque....
for ( i=0; i<m; i+2 )
Acho que isto não deve estar bem...
for(i=0;i<m; i+=2)
Assim já dá...Se for isto que queres fazer.. que não li o código.... é que senão não estás a afectar o i
por akaxo nao tinha visto exe promenor obrigado
mas o k eu nao sei fazer e como inserir os dados na matriz e fazer com k eles fikem la guardados
Tens uma chaveta a mais na última linha do código e o tal erro corrigido pelo saunde na linha 20.
activado 0
float **Alocarmatriz (int m, int n) /* colocaçao da matriz dinamicamente */
v = (float **) calloc (m, sizeof(float *)); /* aloca as linhas da matriz */
printf ("** Erro: Memoria Insuficiente **"); /*ver isto*/
for ( i=0; i<m; i+=2 ) {
float **Libertamatriz (int m, int n, float **v) /* tirar dados desnecessarios*/
main(float)
printf("introduzir o numero de cidadees a visitar:\n");
printf("introduza a distancia da cidade %c a cidade %c:\n",ch+i,ch+i+1);
Isto é tudo o que sou capaz de fazer para resolver o problema do caixeiro viajante. O proble baseia-se em o utilizador colocar o nº de cidades a visitar e a distancia entre elas, e o programa devolver a sequencia com a distancia percorrida menor(passando por todas as cidades, nunca voltando ã mesma e no fim voltando á de partida).
Alguem me pode ajudar a acabar?
Tens aí algumas coisas que não fazem sentido muito sentido:
- Só aceitas uma ligação para cada cidade, e é só para a cidade com indice seguinte. Aqui lês um inteiro (a distância) mas não guardas esse valor na matriz.
- Só alocas a matriz de distâncias depois de ler as distancias entre as cidades. O valor das colunas © não foi inicializado, enquanto que o valor das linhas (l) vai ter o valor da ultima distância lida.
- Estás a inicializar a matriz com o valor "i+j", devia ser aqui que lias a distância entre a cidade i e j
Primeiro tens de definir se as distâncias são inteiros ou floats. No ciclo de leitura de distancias lês inteiros mas alocas a matriz para floats.
Independentemente disto, para simplificar, podias ter uma matriz com tamanho NxN (N = número de cidades) com as distâncias entre a cidade i e j (mat[ i][ j]).
mat=Alocarmatriz ( n , n );
Normalmente, não há ligação entre todas as cidades (isto é, se temos Porto , Coimbra e Lisboa, temos só a distancia entre Porto-Coimbra e Coimbra-Lisboa). Assim, podes perguntar qual é o número de ligações entre cidades - E ( do ingles Edge ) e ler "cidade1 cidade2 distancia" , e preencher a matriz de acordo com isso.
printf("Qual e' o numero de ligacoes entre cidades? ");
scanf("%d" , & E );
for ( i=0; i< E ; i++)
printf("introduza a distancia entre a cidade1 e a cidade2 no formato  <cidade1> <cidade2> <distancia> \n");
scanf("%d %d %d", & cid1 , & cid2 , & distancia );  // se distancia for um float, mudar o terceiro %d
mat[ cid2 ][ cid1 ] = mat[ cid1 ][ cid2 ] = distancia ; // considerando que a distancia e' igual nos 2 sentidos
Outra forma de ler as distancias sem perguntar o numero de ligações, é ler dados com uma sentinela perguntando se o utilizador pretende continuar a inserir distâncias.
Posto isto, o teu problema é o algoritmo. Eu nunca resolvi este problema, mas já ouvi falar nele. Sei que é um problema NP-Completo o que significa que não há algoritmos eficientes para resolver este problema.
Assim, resta testar todas as hipoteses de solução. Suponho que já tenhas prática com funções recursivas ?
Basicamente, tu precisas de fazer uma pesquisa num grafo. Aquilo que queres determinar é um caminho com N+1 cidades sendo que a primeira e última cidade já sabes qual é ( cidade 0 não é?).
Assim, a minha sugestão é que chames uma função que comece a visita na cidade 0. Esta função recebe como argumento o indice da cidade que vai percorrer, e para cada cidade vizinha (com distância definida) vai fazer uma pesquisa na vizinha ignorando a cidade anterior. Na vizinha faz o mesmo e assim sucessivamente até teres visitado todas as cidades.
Acho que o melhor é começares por fazer um programa que procure a distancia minima a percorrer as N cidades e só depois obrigas a que regresse à cidade original.
Já me alonguei bastante, espero ter ajudado, se o que escrevi estiver confuso é porque não queria deixar a solução já feita