1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Rotina para array de numeros

Discussão em 'Programação' iniciada por Barata, 3 de Maio de 2005. (Respostas: 15; Visualizações: 1775)

  1. Barata

    Barata I folded Myself

    Boas!

    Precisava que me dessem umas dicas de como codar uma rotina que permita testar todas as combinações entre elementos de um array.

    Exemplo:

    int array[5]={12, 23,45, 10, 9};

    A rotina tem de todas as combinações possiveis destes 5 numeros.

    Por exemplo: 23, 12, 9, 10, 45 .

    Se não fui claro, não hesitem em colocar as vossas duvidas à cerca do problema.

    Hugzz! ;)

    PS- A linguagem é C, mas o que necessito mesmo é de um algoritmo e não do código em si.
     
    Última edição: 3 de Maio de 2005
  2. Karmack

    Karmack Power Member

    Estas combinações são possiveis?
    { 12 }
    { 12 23 }
    { .........}
    E
    { 23, 12, 9, 10, 45 } é diferente de:
    { 23, 12, 9, 45, 10 }

    ?
     
  3. Barata

    Barata I folded Myself

    As combinações geradas têm que ter sempre os 5 numeros.

    Sim, { 23, 12, 9, 10, 45 } != { 23, 12, 9, 45, 10 }.

    ;)
     
  4. redalert

    redalert Folding Member

    combinacoes de 5 numeros com repeticao?

    [[]]
     
  5. Barata

    Barata I folded Myself

    ORa bem, não pensei que isto fosse dar tantos problemas de interpretação, mas aqui vai algo que decerto facilitará.

    Isto é para um programa que estou a fazer para descobrir qual o menor caminho entre 40 cidades.

    Decidi fazer isto recorrendo ao menor caminho entre blocos de 10 cidades.

    Exemplo:

    Caminho 1: {1,2,3,4,5,6,7,8,9,10} = 500km
    !=
    Caminho 2: {2,1,3,4,5,6,7,8,9,10}= 493km

    Como é obvio já tenho função que me vai dar estas distancias. Isto foi apenas um exemplo. Cada numero representa uma cidade.
    :(
     
  6. Karmack

    Karmack Power Member

    Já ouviste falar do algoritmo de Dijkstra? Dado um ponto este calcula a menor distancia e os nós do caminho mais curto.
    Investiga no wikipedia ou usa o google.
     
  7. redalert

    redalert Folding Member

    o Dijkstra n calcula a arvore minima de suporte? :wow:

    ja agora --> http://matrix.inesc-id.pt/aed/?Material_de_apoio

    [[]]
     
  8. zx-9r

    zx-9r Power Member

    Tantos Investigadores Operacionais :D
     
  9. fap

    fap Power Member

    não sei a que te referes quando dizes árvore mínima de ?suporte?... o Dijkstra calcula o caminho mais curto de um ponto a todos os pontos de um grafo

    se querias dizer árvore mínima abrangente (minimum spanning tree) tens outros como o de Kruskal, Primm ou Essau-Williams
     
  10. redalert

    redalert Folding Member

    mst :)
     
  11. PrOdG

    PrOdG Power Member

    http://en.wikipedia.org/wiki/Dijkstra's_algorithm

    Isto fazia parte da minha consulta para o exame de AED2, deu bastante jeito(tem implementações em C, C++ e Python, para dar ainda menos trabalho ;)).

    Lembro-me também de um site que simulava (em applets de java) o funcionamento de vários algoritmos relacionados com grafos, aqueles de que o fap falou, por exemplo :) Se quiseres posso procurar-te isso.
     
  12. redalert

    redalert Folding Member

    venha! :D

    [[]]
     
  13. PrOdG

    PrOdG Power Member

  14. sapropel

    sapropel Power Member

    isso é permutações
    http://en.wikipedia.org/wiki/Permutation
    têm lá no "permutation in computing" algoritmos para isso, lê.

    entretanto toma já uma implmentação para vectores de inteiros com o exemplo que deste:

    Código:
    #include <stdlib.h>
    #include <stdio.h>
    
    void swap( int * array, int a, int b )
    {
    	int temp = array[a];
    	array[a] = array[b];
    	array[b] = temp;
    }
    
    int permute( int *  array, int size )
    {
    	int key = size - 1;
    	int newkey = size - 1;
    
    	while( (key > 0) && (array[key] <= array[key-1]) )
    	{
    		key--;
    	}
    	key--;
    
    	if( key < 0 )
            return 0;
    
    	newkey = size - 1;
    	while( (newkey > key) && (array[newkey] <= array[key]) )
    	{
    		newkey--;
    	}
    
    	swap( array, key, newkey );
    
    	size--;
    	key++;
    
    	while( size > key )
    	{
    		swap( array, size, key );
    		key++;
    		size--;
    	}
    
    	return 1;
    }
    
    int main( int argc, char *argv[] )
    {
    	int test_array[] = { 12, 23,45, 10, 9 };
    
    	do  
    	{
    		printf( "%d  %d  %d  %d  %d\n", test_array[0], test_array[1], test_array[2], test_array[3], test_array[4] );
    	}
    	while( permute( test_array, 5 ) );
    	
    	return 0;
    }
    
     
  15. Barata

    Barata I folded Myself

    thanks alot sapropel! :D :001:
     
  16. toninho_77

    toninho_77 Power Member

Partilhar esta Página