IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Combinatoire et recherche


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Inscrit en
    Mars 2005
    Messages
    98
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 98
    Par défaut Combinatoire et recherche
    Bonjour a tous

    voila j'ai un probleme de programmation mais je ne sais pas comment faire
    je suis neophite en la matiere voila mon probleme .

    comment programmer ceci en C .

    dans un fichier j'ai des entiers ( 10 par ligne ) ex

    1 2 3 4 5 6 7 8 9 10
    1 2 5 7 9 10 11 13 14 15
    .....
    .....
    .....
    dans mon programme je genere toutes les combinaisons possibles
    de 1 a 25 de 10 chiffres C ( 10 25 ) ce qui fait 3 268 760 combinaisons

    chaque combinaisons generé doit etre verifier avec chaque ligne de mon fichier ( donc verifier chffre par chiffre) quand un chiffre est commun je doit incrementer un compteur ,faire cela jusqu'a la fin des combinaisons generées .

    comment programmer ce genre de choses de façon a ce qu'il soit le plus optimiser possible ? ( par exemple les boucles imbriquées qui sont tres nombreuse , recursivité ... enfin bref je sais pas ;-) )

    merci de votre aide
    cordialement
    ps) pardon pour les fautes

  2. #2
    Expert éminent
    Avatar de Emmanuel Delahaye
    Profil pro
    Retraité
    Inscrit en
    Décembre 2003
    Messages
    14 512
    Détails du profil
    Informations personnelles :
    Âge : 68
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Retraité

    Informations forums :
    Inscription : Décembre 2003
    Messages : 14 512
    Par défaut
    Citation Envoyé par zhao
    voila j'ai un probleme de programmation mais je ne sais pas comment faire je suis neophite en la matiere voila mon probleme .
    <snip 0 lignes de code>
    Tu as oublié de poster le code avec lequel tu as un problème, et de préciser quel est le problème.

  3. #3
    Membre confirmé
    Inscrit en
    Mars 2005
    Messages
    98
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 98
    Par défaut
    Bonjour

    heu desolé mais justement je n'ai rien oublier , le fichier dont je parle est generer par une application completement independante .
    et je doit faire le programme cité plus haut qui lui aussi est independant .
    mais je ne sais ABSOLUMENT pas comment faie ;-(
    cordialement

  4. #4
    Membre averti
    Profil pro
    Inscrit en
    Décembre 2005
    Messages
    12
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2005
    Messages : 12
    Par défaut Pourquoi pas un arbre type patricia?
    tu cree un arbre, tu le peuple avec les sequences de ton fichier, puis tu le parcours au fur et a mesure de la generation des sequences exhaustives.
    Je pencherais pour la recursivité pour la generation, ce qui permet d'arreter la generation des qu'un prefixe n'est pas connu dans l'arbre.
    Il existe peut etre plus efficace!

  5. #5
    Membre Expert Avatar de zooro
    Homme Profil pro
    Développeur Java
    Inscrit en
    Avril 2006
    Messages
    921
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 47
    Localisation : France, Marne (Champagne Ardenne)

    Informations professionnelles :
    Activité : Développeur Java

    Informations forums :
    Inscription : Avril 2006
    Messages : 921
    Par défaut
    Bonjour,

    Trouves déjà un algo général qui te permettra de résoudre le problème.
    Du genre:
    - générer et stocker toutes les combinaisons possibles...
    - ouvrir le fichier
    - pour chaque ligne lue dans le fichier, faire...
    - fermer le fichier

    Ensuite, tu pourras affiner l'algo en fonction de la solution que tu veux implémenter (tableau(x), arbre, listes, etc.).

    On ne fera pas l'exercice à ta place, mais on t'aidera si tu postes ton travail au fur et à mesure en posant des questions sur les problèmes que tu rencontres, ou pour avoir des conseils sur les algos que tu a trouvés, ou sur ton code.

  6. #6
    Membre confirmé
    Inscrit en
    Mars 2005
    Messages
    98
    Détails du profil
    Informations forums :
    Inscription : Mars 2005
    Messages : 98
    Par défaut
    voila ce que je sais faire OH cela n'est pas tres tres joli mais bon ..., mais ensuite je ne sais pas faire :-)
    bref je sais generer les combinaisons mais cela s'arrete la et encore je suis quasiment sur qu'il y en a qui ont des algorythme plus performant que ma methode ultra classique ;-)

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
     
     
    #include<stdio.h>
    #include <dos.h>
    #include <time.h>
     
     main()
     
    			{
     
    	                int tc[10];
    	                int nt=0;
    			register int i,j,k,l,m,n,o,p,q,r;
     
    			FILE *fichier; 
     
    			fichier=fopen("test.txt","r"); 
     
                            printf("entrez votre valeur   ");
    			scanf("%d",&nt);
    			a=nt-9;
     
    				  for(i=1;i<=a;i++)
    				  for(j=i+1;j<=a+1;j++)
    				  for(k=j+1;k<=a+2;k++)
    				  for(l=k+1;l<=a+3;l++)
    				  for(m=l+1;m<=a+4;m++)
    				  for(n=m+1;n<=a+5;n++)
                                      for(o=n+1;o<=a+6;o++)
    				  for(p=o+1;p<=a+7;p++)
    				  for(q=p+1;q<=a+8;q++)
    				  for(r=q+1;r<=a+9;r++)
     tc[0]=i;tc[1]=j;tc[2]=k;tc[3]=l;tc[4]=m;tc[5]=n,
     tc[6]=o;tc[7]=p;tc[8]=q;tc[9]=r;		   
    }

Discussions similaires

  1. recherche des algorythmes pour images 2d
    Par exxos dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 24/05/2002, 13h46
  2. recherches des cours ou des explications sur les algorithmes
    Par Marcus2211 dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 19/05/2002, 22h18
  3. Réponses: 8
    Dernier message: 17/05/2002, 09h08
  4. [PRO*C] Recherche information
    Par Anonymous dans le forum Interfaces de programmation
    Réponses: 2
    Dernier message: 04/04/2002, 17h53
  5. Recherche de documentation complète en algorithmes
    Par Anonymous dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 29/03/2002, 12h09

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo