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

 C++ Discussion :

transformer un code itératif en récursif


Sujet :

C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre confirmé
    Inscrit en
    Mai 2008
    Messages
    112
    Détails du profil
    Informations forums :
    Inscription : Mai 2008
    Messages : 112
    Par défaut transformer un code itératif en récursif
    Salut tout le monde,

    Je veux développer une fonction qui me rend toutes les combinaisons possibles à partir d'un vecteur d'entier.
    Par exemple si j'ai le vecteur v1={1,2,3,4} elle me retourne un string qui contient toutes les combinaisons séparée par un espace{1,12,123,1234,124,13,134,14,2,23,234,24,3,34,4}.Je pense qu'une fonction récursive pourra résoudre mon problème.J'ai raisonné de cette façon mais je n'est pas su comment faire pour rendre ce code récursif:
    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
     
    vector<int> v1;
    vector<int>v2;
    ostringstream oss;
    string ss;
     
    v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);
     
    for(int i=0;i<v1.size();i++)
    {
    oss<<v1[i]<<" ";
    ss=oss.str();
    for(int k=i+1;k<v1.size();k++)
    {
    	oss<<v1[i]<<v1[k]<<" ";
    	ss=oss.str();
    	for(int j=k+1;j<v1.size();j++)
    	{
    	oss<<v1[i]<<v1[k]<<v1[j]<<" ";
    	ss=oss.str();
    	for(int l=j+1;l<v1.size();l++)
    	{
    	oss<<v1[i]<<v1[k]<<v1[j]<<v1[l]<<" ";
    	ss=oss.str();
    	for(int p=l+1;p<v1.size();p++)
    	{
    	oss<<v1[i]<<v1[k]<<v1[j]<<v1[l]<<v1[p]<<" ";
    	ss=oss.str();
    	}
    	}
    	}
    }
    }
    cout<<ss;
    Je serais très reconnaissante si vous pourriez me donner un petit coup de main pour résoudre mon problème.Merci d'avance

  2. #2
    Invité
    Invité(e)
    Par défaut
    L'idée est de parcourir ton vecteur du premier au dernier élément, et à chaque étape d'ajouter 2 "groupes de solutions" : ceux qui incluent l'élément, et celles qui ne l'incluent pas. Donc, tu pourrais avoir une fonction récursive de ce genre...

    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
     
    // tes données
    vector<int> v;
     
    // w est la solution en cours de construction, 
    //lev la position dans v où l'on se trouve
    // lev peut être remplacé par un itérateur sur v, 
    // si tu veux absolument faire moderne
    void recurs(vector<int> &w,int lev)
    {
    // on a fini, imprimer le vecteur résultat
    if(lev==v.size()) print(w);
    else {
      //ajouter l'élément en cours
      vector w1=w;
      w1.push_back(v[lev]);
      lev++;
      recurs(w1,lev);
      recurs(w,lev);
    }
    }
    Pour énumérer tous les sous ensembles, tu remplis v, tu crées un vecteur w vide, et tu appelles recurs(w,0). Ca devrait t'imprimer le résultat dans le même ordre que ta fonction d'avant... Je n'ai pas testé, donc il se peut qu'il faille modifier un ou deux trucs, mais c'est l'esprit.

    Comme souvent avec les fonctions récursives, celle ci sera probablement lente. Une façon plus élégante d'aborder ce problème serait de le considérer comme un problème d'énumération. En gros, tu énumères tous les sous ensembles de v, et pour cela, tu vas, pour chaque élément, avoir deux cas : "avec" et "sans". Ca te fait donc 2^N cas.

    Pour N pas trop grand (de toutes façons, si N dépasse la vingtaine, l'énumération dépasse le million de cas, et ca n'a plus beaucoup de sens), tu pourrait avoir une simple boucle, de 0 à 2^N, dans laquelle le compteur de boucle te sert également de masque de bits pour savoir quels éléments de ton vecteur v sont sélectionnés. Pour 4 éléments tu aurais un truc comme

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    unsigned masks[4]={1,2,4,8};
    for(unsigned int i=0;i<16;i++) {
      for(int j=0;j<4;j++) if( (i&masks[j]) !=0) cout<<v[j];
      cout<<" ";
    }
    Ca risque d'aller nettement plus vite... (dans un vrai programme, tu remplacerais bien sur 16 et les masques par des paramètres).

    Ceci fonctionne si tu cherches des sous ensembles (donc si v n'a pas d'éléments en doublon), si tu as des répétitions, alors il te faudra d'autres méthodes d'énumération (il y avait autrefois sur le site de Knuth des previews du tome 4 de l'art of computer programming, qui contenait un plein chapitre sur le sujet...)

    Francois
    Dernière modification par Invité ; 20/08/2009 à 08h55.

  3. #3
    Membre confirmé
    Inscrit en
    Mai 2008
    Messages
    112
    Détails du profil
    Informations forums :
    Inscription : Mai 2008
    Messages : 112
    Par défaut
    Merci pour votre réponse.J'ai essayé ta fonction récursive:
    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
     
    void recurs(vector<int> &w,int lev)
    {
    	vector<int> v;
    // on a fini, imprimer le vecteur résultat
    if(lev==v.size())  PRINT_ELEMENT(w);
    else {
      //ajouter l'élément en cours
      vector <int>w1=w;
      w1.push_back(v[lev]);
      lev++;
      recurs(w1,lev);
      recurs(w,lev);  
    }
    }
    et pour l'appeler:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    vector<int> v1;
    v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);
    recurs(v1,0);
    pour le niveau 0 ça me ramène le résultat exacte mais à partir du niveau 1 ça me génère le message de débordement de mémoire.Je me demande si on pourrais pas rajouter un clear() dans l'un des vecteurs dans la fonction récursive

  4. #4
    Membre Expert
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 34
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Par défaut
    sinon y'a std::next_permutation() et std::prev_permutation() hein pour les différentes combinaisons d'un containeur.

  5. #5
    Membre confirmé
    Inscrit en
    Mai 2008
    Messages
    112
    Détails du profil
    Informations forums :
    Inscription : Mai 2008
    Messages : 112
    Par défaut
    svp pourriez vous me donner un petit exemple comment utiliser std::next_permutation() et std::prev_permutation().Merci d'avance

  6. #6
    Membre Expert
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 34
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Par défaut
    Voilà :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
        std::vector<int> v1;
        v1 += 0,1,2,3;
     
        while(std::next_permutation(v1.begin(), v1.end()))
        {
            std::copy(v1.begin(), v1.end(), std::ostream_iterator<int>(std::cout, " "));
            std::cout << std::endl;
        }

  7. #7
    Invité
    Invité(e)
    Par défaut
    Citation Envoyé par FstDsi Voir le message
    et pour l'appeler:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
     
    vector<int> v1;
    v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);
    recurs(v1,0);
    pour le niveau 0 ça me ramène le résultat exacte mais à partir du niveau 1 ça me génère le message de débordement de mémoire.Je me demande si on pourrais pas rajouter un clear() dans l'un des vecteurs dans la fonction récursive
    Ben forcément .... Dans mon code, le premier parametre de recurs() c'est une référence sur le vecteur contenant le résultat (qu'on imprimera à la fin). Au démarrage, il faut lui passer un vecteur vide. Si tu lui passes la donnée, il va se passer des choses affreuses...

    Et dans ta version de mon code, si tu mets v comme variable locale de la fonction recurs() ca va pas marcher non plus...

    En fait, tu as deux vecteurs
    - v, qui correspond aux données, celui là il ne bouge pas d'un appel à l'autre de la fonction récursive (tu peux le passer en réference constante si tu veux)
    - w, le paramètre de recurs() qui contient la solution en cours de construction (puisque chaque appel à recurs() la construit un peu plus)


    @goten : les permutations, c'est tout autre chose...
    {1,12,123,1234,124,13,134,14,2,23,234,24,3,34,4}, ce ne sont certainement pas les permutations de {1,2,3,4} (les permutations, ce seraient 1234,1243,1342,1432, etc...)... Ce que FstDsi génère, ce sont les sous ensembles (et, au passage, les combinaisons c'est encore autre chose: c'est quand on prend k objets parmi n, les permutations y'en a n!, les sous ensembles 2^n, les combinaisons C(n,k), le coeff binomial, les sous ensembles, ce sont toutes les combinaisons, pour toutes les valeurs de k).

    Francois
    Dernière modification par Invité ; 20/08/2009 à 11h00.

  8. #8
    Membre Expert
    Avatar de Goten
    Profil pro
    Inscrit en
    Juillet 2008
    Messages
    1 580
    Détails du profil
    Informations personnelles :
    Âge : 34
    Localisation : France

    Informations forums :
    Inscription : Juillet 2008
    Messages : 1 580
    Par défaut
    oups matin toussa toussa ^^. Ca m'apprendra à lire en travers. (btw j'avais pas vu le mots sous-ensemble justement)

  9. #9
    Membre confirmé
    Inscrit en
    Mai 2008
    Messages
    112
    Détails du profil
    Informations forums :
    Inscription : Mai 2008
    Messages : 112
    Par défaut
    Merciiiiiiiii bcp fcharton.En fait je passais de faux paramètres pour la fonction.ça marche mnt.Merci a tous

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. [XML] Transformer un code XML en PHP
    Par leila2006 dans le forum Bibliothèques et frameworks
    Réponses: 1
    Dernier message: 07/05/2006, 18h51
  2. [LG] Transformer un code ascii en un autre
    Par JoseF dans le forum Langage
    Réponses: 8
    Dernier message: 29/12/2005, 11h47
  3. transformer de l'itératif en récursif
    Par hiina dans le forum C
    Réponses: 8
    Dernier message: 27/11/2005, 21h16
  4. [PHP-JS] pasteHTML qui transforme le code
    Par jibouze dans le forum Langage
    Réponses: 1
    Dernier message: 28/10/2005, 17h36
  5. [] transformer un code ean en isbn
    Par dlpxlid dans le forum VB 6 et antérieur
    Réponses: 3
    Dernier message: 15/10/2005, 15h54

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