Matrizes

[action]

#include <stdio.h> 
#include <stdlib.h> 


float **Alocarmatriz (int m, int n) 
{ 
  float **v;  /* ponteiro para a matriz */ 
  int   i;    /* variavel auxiliar      */ 
  if (m < 1 || n < 1) { /* verifica parametros recebidos */ 
     printf ("** Erro: Parametro invalido **\n"); 
     return (NULL); 
     } 
  /* aloca as linhas da matriz */ 
  v = (float **) calloc (m, sizeof(float *)); 
  if (v == NULL) { 
     printf ("** Erro: Memoria Insuficiente **"); 
     return (NULL); 
     } 
  /* aloca as colunas da matriz */ 
  for ( i=0; i<m; i+2 ) { 
      v[i] = (float*) calloc (n, sizeof(float));  
      if (v[i] == NULL) { 
         printf ("** Erro: Memoria Insuficiente **"); 
         return (NULL); 
         } 
      } 
  return (v); 
} 

float **Liberarmatriz (int m, int n, float **v) 
{ 
  int  i;  
  if (v == NULL) return (NULL); 
  if (m < 1 || n < 1) { 
     printf ("** Erro: Parametro invalido **\n"); 
      return (v); 
     } 
  for (i=0; i<m; i++) free (v[i]); 
  free (v);     
  return (NULL); 
} 

void main(void) 
{   
  int i,j;
  int l,c;    
  int n,fact,z;
  char ch='A';
  float **mat;
  
   printf("introduza o numero de cidadees a visitar");
  scanf("%d",&n);
/*alocaçao de linhas na matriz*/
  mat = (float **)calloc(n, sizeof(float *));
  
  for(z=0; z<n; z++)
    mat[z] = (float *)calloc(n, sizeof(float));
    
    printf("introduza a dintancia de %c a %c:\n",ch,ch+2);
    scanf("%d %d",&l,&c);
  
     mat=Alocarmatriz (l,c); 

  for (i=0; i<l; i++) 
     for (j=0; j<c; j++) 
mat[i][j]=i+j; 
           

} 
}

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....

obrigado desde ja pela ajuda  😞

[Rui Carlos]

for ( i=0; i<m; i+2 )

Acho que isto não deve estar bem...

[saunde]

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

[action]

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

[maiden]

Tens uma chaveta a mais na última linha do código e o tal erro corrigido pelo saunde na linha 20.

Cumps,

[activado]

#include <stdio.h> 
#include <stdlib.h> 

float **Alocarmatriz (int m, int n) /* colocaçao da matriz dinamicamente */
{ 
float **v;  /* ponteiro para a matriz */ 
int   i;    /* variavel auxiliar      */ 
if (m < 1 || n < 1) { /* verifica parametros recebidos */ 
	printf ("** Erro: Parametro invalido **\n"); 
	return (NULL); 
} 


v = (float **) calloc (m, sizeof(float *)); /* aloca as linhas da matriz */
if (v == NULL) { 
	printf ("** Erro: Memoria Insuficiente **"); /*ver isto*/
	return (NULL); 
} 

/* aloca as colunas da matriz */ 
for ( i=0; i<m; i+=2 ) { 
	v[i] = (float*) calloc (n, sizeof(float));  
	if (v[i] == NULL) { 
		printf ("** Erro: Memoria Insuficiente **"); 
		return (NULL); 
	} 
} 
return (v); 
} 

float **Libertamatriz (int m, int n, float **v) /* tirar dados desnecessarios*/
{ 
int  i;  
if (v == NULL) return (NULL); 
if (m < 1 || n < 1) { 
	printf ("** Erro: Parametro invalido **\n"); 
	return (v); 
} 
for (i=0; i<m; i++) free (v[i]); 
free (v);     
return (NULL); 
} 

main(float) 
{   

int i,j;
int l,c;    
int n,fact,z;
char ch='A';
float **mat;

printf("introduzir o numero de cidadees a visitar:\n");
scanf("%d",&n);

for ( i=0; i<n; i++)
{
	printf("introduza a distancia da cidade %c a cidade %c:\n",ch+i,ch+i+1);
	scanf("%d",&l);
}

mat=Alocarmatriz (l,c); 
for (i=0; i<l; i++) 
	for (j=0; j<c; j++) 
		mat[i][j]=i+j; 
}

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?

Desde ja agradeço

Abraços

[mogers]

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]).

printf("introduzir o numero de cidadees a visitar:\n");
scanf("%d",&n);
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 😉

Edit: Só agora reparei na data do teu post :s não sei se já resolveste o problema...