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 :

Combinaison de k valeurs parmi n


Sujet :

C++

  1. #1
    Membre du Club
    Inscrit en
    Février 2011
    Messages
    188
    Détails du profil
    Informations forums :
    Inscription : Février 2011
    Messages : 188
    Points : 51
    Points
    51
    Par défaut Combinaison de k valeurs parmi n
    Bonjour,

    le code suivant permet de calculer la combinaison de k valeurs parmi n. Pour certaines valeurs de n et q, ce code me donne des résultats erronés. J'aime savoir ou résiste le problème. Et si vous pouvez me donner une autre proposition, je serais reconnaissant.

    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
    float MI::combinaison(int n,int q) //la Combinaison de q éléments parmi n
    {
        float comb;
        if(n==q)
        {
            return 1;
        }
        else
            if(q==1)
            {
                 return n;
            }
            else
            {
                 comb=(n/q)*combinaison(n-1,q-1);
                 return comb;
            }
    }

  2. #2
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    Juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : Juin 2006
    Messages : 2 307
    Points : 4 732
    Points
    4 732
    Par défaut
    Soit tu appliques la formule directe en simplifiant un poil pour éviter le calcul de factorielles trop grandes, soit tu calules par reccurence avec une formule correcte.

    Voir ici.

    Autre remarques. k parmi n renvoie un entier, je vois pas pourquoi ta fonction renvoie un float..
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  3. #3
    Membre du Club
    Inscrit en
    Février 2011
    Messages
    188
    Détails du profil
    Informations forums :
    Inscription : Février 2011
    Messages : 188
    Points : 51
    Points
    51
    Par défaut
    Citation Envoyé par Davidbrcz Voir le message
    soit tu calules par reccurence avec une formule correcte.
    cela veut dira que ma proposition est fausse??

    Citation Envoyé par Davidbrcz Voir le message
    Autre remarques. k parmi n renvoie un entier, je vois pas pourquoi ta fonction renvoie un float..
    oui c vrai, j'ai changé le type de retour en int .

  4. #4
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    Juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : Juin 2006
    Messages : 2 307
    Points : 4 732
    Points
    4 732
    Par défaut
    cela veut dira que ma proposition est fausse??

    A toi de voir


    oui c vrai, j'ai changé le type de retour en int
    même un int c'est limite, j'aurais mis un unsigned long voir même un unsigned long long
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  5. #5
    Membre régulier
    Homme Profil pro
    Inscrit en
    Mars 2011
    Messages
    94
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Mars 2011
    Messages : 94
    Points : 122
    Points
    122
    Par défaut
    Je suis aussi tombé là dessus:

    https://gist.github.com/jeetsukumaran/5392166

    au pire boost le fait déjà:

    http://www.boost.org/doc/libs/1_46_1..._binomial.html

  6. #6
    Membre du Club
    Inscrit en
    Février 2011
    Messages
    188
    Détails du profil
    Informations forums :
    Inscription : Février 2011
    Messages : 188
    Points : 51
    Points
    51
    Par défaut
    Merci pour toute ces réponses. J'ai codé ma fonction autrement mais j'ai constaté elle ne fonctionne pas pour les nombre très grand. Est ce qu'il me faut une autre bibliothèque C++ pour que je puisse réussir cette fonction?

    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
    unsigned long long combinaison(unsigned long n, unsigned long k) {
        unsigned long i;
        unsigned long long b;
        if (0 == k || n == k) {
            return 1;
        }
        if (k > n) {
            return 0;
        }
        if (k > (n - k)) {
            k = n - k;
        }
        if (1 == k) {
            return n;
        }
        b = 1;
        for (i = 1; i <= k; ++i) {
            b *= (n - (k - i));
            if (b < 0) return -1; 
            b /= i;
        }
        return b;
    }

  7. #7
    Membre du Club
    Inscrit en
    Février 2011
    Messages
    188
    Détails du profil
    Informations forums :
    Inscription : Février 2011
    Messages : 188
    Points : 51
    Points
    51
    Par défaut
    Je tombe sur http://www.boost.org/doc/libs/1_46_1..._binomial.html donc je me dirige vers l'utilisation des bibliothèques Boost pour résoudre ce problème. Est ce je suis sur le bon chemin?

  8. #8
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    Juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : Juin 2006
    Messages : 2 307
    Points : 4 732
    Points
    4 732
    Par défaut
    Normal que ta fonction ne marche plus pour des nombres grand.
    Le coefficient binomial ca grandit vite et tu dépasse rapidement la capacité d'un int. Passer sur un (unsigned) long (ou même (unsigned) long long) ne fait que déporter le soucis.

    A un moment tu tombes forcement au delà de la capacité maximale du type.

    Boost est bien car il t'assure un algorithme correct et compatible (avec les template) avec n'importe quel type du moment qu'il satisfasse des conditions basiques.

    Ca permet (e toute logique), une utilisation avec des bibliothèques de précision arbitraire telles que GMP.
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  9. #9
    Membre régulier
    Homme Profil pro
    Inscrit en
    Mars 2011
    Messages
    94
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Mars 2011
    Messages : 94
    Points : 122
    Points
    122
    Par défaut
    Citation Envoyé par kochfet Voir le message
    Merci pour toute ces réponses. J'ai codé ma fonction autrement mais j'ai constaté elle ne fonctionne pas pour les nombre très grand. Est ce qu'il me faut une autre bibliothèque C++ pour que je puisse réussir cette fonction?
    Qu'est ce que tu appelles un nombre très grand ?

    Au vu de ton code:

    unsigned long = valeur comprise entre 0 et 4 294 967 295

    Si tu spécifies un entier supérieur à cette valeur, tu peux essayer de spécifier alors comme entier un unsigned long long, qui tourne sur 64 bits. J'ai bien dit "essayer", car ce type n'est pas standard (je crois), et donc tout dépend de ton compilateur: certains l'acceptent, d'autres non.


    Et si malgré tout un unsigned long long n'est pas suffisant, il va falloir faire autrement. Essaie de voir avec cette library qui propose la gestion des grands entiers: https://gmplib.org/


    EDIT: grilled purée j'ai pas de bol

  10. #10
    Membre du Club
    Inscrit en
    Février 2011
    Messages
    188
    Détails du profil
    Informations forums :
    Inscription : Février 2011
    Messages : 188
    Points : 51
    Points
    51
    Par défaut
    j'ai téléchargé boost.zip mais pouvez vous m'aider à l'installer correctement . Je travaille sur visual C++2010.

  11. #11
    Membre régulier
    Homme Profil pro
    Inscrit en
    Mars 2011
    Messages
    94
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : Mars 2011
    Messages : 94
    Points : 122
    Points
    122
    Par défaut
    Pour l'installation je te recommande de voir ici:
    http://cpp.developpez.com/faq/cpp/?p...#BOOST_install


    @Davidbrcz: effectivement boost gère le GMP: http://www.boost.org/doc/libs/1_55_0...s/gmp_int.html
    J'aurai encore appris un truc

  12. #12
    r0d
    r0d est déconnecté
    Expert éminent

    Homme Profil pro
    tech lead c++ linux
    Inscrit en
    Août 2004
    Messages
    4 262
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : tech lead c++ linux

    Informations forums :
    Inscription : Août 2004
    Messages : 4 262
    Points : 6 680
    Points
    6 680
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Boumbata Voir le message
    Pour l'installation je te recommande de voir ici:
    http://cpp.developpez.com/faq/cpp/?p...#BOOST_install
    Cette entrée de la FAQ n'est pas à jour. Notamment boost consulting n'existe plus.
    Pour installer boost, je te conseille de procéder comme suit:
    Récupère le trunk courant dans un répertoire externe à l'arborescence de ton projet. Pour ce faire, un simple svn checkout sur http://svn.boost.org/svn/boost/trunk
    Ensuite, tu vas dans le dossier racine et tu lances la commande suivante:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    b2.exe toolset=msvc-10.0 architecture=x86  address-model=64 link=static stage
    "stage" c'est le nom du dossier dans lequel seront générées toutes les libs, c'est une valeur par défaut, une legacy plutôt, enfin bref, mais tu peux la modifier à ton aise.

    Par contre, entre le chekout et le build, il y a en pour un bon moment, au moins une heure je dirais.
    « L'effort par lequel toute chose tend à persévérer dans son être n'est rien de plus que l'essence actuelle de cette chose. »
    Spinoza — Éthique III, Proposition VII

  13. #13
    Membre du Club
    Inscrit en
    Février 2011
    Messages
    188
    Détails du profil
    Informations forums :
    Inscription : Février 2011
    Messages : 188
    Points : 51
    Points
    51
    Par défaut
    J'ai pas trouvé le .exe dans mon dossier dézzippé.

  14. #14
    Rédacteur

    Avatar de Davidbrcz
    Homme Profil pro
    Ing Supaéro - Doctorant ONERA
    Inscrit en
    Juin 2006
    Messages
    2 307
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 32
    Localisation : Suisse

    Informations professionnelles :
    Activité : Ing Supaéro - Doctorant ONERA

    Informations forums :
    Inscription : Juin 2006
    Messages : 2 307
    Points : 4 732
    Points
    4 732
    Par défaut
    Citation Envoyé par kochfet Voir le message
    J'ai pas trouvé le .exe dans mon dossier dézzippé.
    Toute la procedure est la : http://www.boost.org/doc/libs/1_53_0...es-from-source

    Ca serait bien de chercher un petit peu !
    "Never use brute force in fighting an exponential." (Andrei Alexandrescu)

    Mes articles dont Conseils divers sur le C++
    Une très bonne doc sur le C++ (en) Why linux is better (fr)

  15. #15
    Membre du Club
    Inscrit en
    Février 2011
    Messages
    188
    Détails du profil
    Informations forums :
    Inscription : Février 2011
    Messages : 188
    Points : 51
    Points
    51
    Par défaut
    Citation Envoyé par Davidbrcz Voir le message
    Je me suis bloqué dès le début exactement à cette ligne

    Go to the directory tools\build\v2 ????

    Remarque :J'ai téléchargé boost_build

  16. #16
    Membre expert
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    1 415
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2007
    Messages : 1 415
    Points : 3 156
    Points
    3 156
    Par défaut
    Salut

    Citation Envoyé par Boumbata Voir le message
    unsigned long = valeur comprise entre 0 et 4 294 967 295
    Attention, cela dépend de la plateforme utilisée et de l'implémentation du compilo ! Sur un linux 64 bits avec GCC, un unsigned int fait 4 octets (soit entre 0 et 4 294 967 295) et un unsigned long en fait 8 (soit entre 0 et 18 446 744 073 709 551 615).

    Pour être sûr, on peut utiliser les types entier à taille fixe, dans la limite de ce que supporte la plateforme utilisée.
    Find me on github

  17. #17
    Membre du Club
    Inscrit en
    Février 2011
    Messages
    188
    Détails du profil
    Informations forums :
    Inscription : Février 2011
    Messages : 188
    Points : 51
    Points
    51
    Par défaut
    Citation Envoyé par jblecanard Voir le message
    on peut utiliser les types entier à taille fixe, dans la limite de ce que supporte la plateforme utilisée.
    Merci pour votre intervention mais j'ai décidé d'utiliser boost. Mon problème maintenant comment l'installer et l'utiliser. J'ai passé toute la journée pour l'installer mais sans résultat. J'ai besoin de vos aides et Merciiiii.

  18. #18
    Membre expert
    Profil pro
    Inscrit en
    Mars 2007
    Messages
    1 415
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Mars 2007
    Messages : 1 415
    Points : 3 156
    Points
    3 156
    Par défaut
    Citation Envoyé par kochfet Voir le message
    Merci pour votre intervention mais j'ai décidé d'utiliser boost. Mon problème maintenant comment l'installer et l'utiliser. J'ai passé toute la journée pour l'installer mais sans résultat. J'ai besoin de vos aides et Merciiiii.
    Mon intervention est orthogonale à ton choix : la partie de Boost dont on parle peut être utilisée avec les types que je suggère.
    Find me on github

  19. #19
    Membre averti

    Profil pro
    Étudiant
    Inscrit en
    Décembre 2004
    Messages
    499
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2004
    Messages : 499
    Points : 422
    Points
    422
    Par défaut
    pour calculer n! / ( k! (n-k)! ) modulo 2^L

    il faut calculer :
    a = red_2(n) * red_2(n-1) * red_2(n-2) * ... * red(n-k+1) [modulo 2^L ]
    b = red_2(k) * red_2(k-1) * red_2(k-2) * ... * red_2(2) [modulo 2^L ]
    où red_2(n) renvoie le plus grand diviseur impair de n
    en même temps on calcule :
    c : tel que 2^c divise n! / (n-k)! et n! / (2^c (n-k)!) est impair
    d : tel que 2^d divise k! et k! / 2^d est impair
    si c-d > L-1 alors le résultat est 0
    sinon
    - calculer inv_b l'inverse modulaire de b [modulo 2^L ]
    - et le résultat final est a * 2^(c-d) * inv_b [modulo 2^L ]

    note que c est forcément supérieur ou égal à d vu que k! divise toujours n! / (n-k)!

    et que b a un unique inverse modulo 2^L puisqu'il est impair (il n'existe pas de p tel que b^p = 0 modulo 2^L donc b génère un groupe cyclique donc b a un inverse)
    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
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
     
     
    void red_2(int & n, int & cn) {
        if (n & 1) return;
        else {
            n = n/2;
            cn++;
            red_2(n,cn);
        }
    }
     
     
    // k^phi(n) = 1 modulo n
    // donc inv_k = k^(phi(n)-1) modulo n
    // ici n = 2^L
    // donc phi(n) = 2^(L-1)
    // donc on a un algo simple pour calculer k^(phi(n)-1)
    // http://fr.wikipedia.org/wiki/Inverse_modulaire#Th.C3.A9or.C3.A8me_d.27Euler
     
    unsigned int inv_modulo_2_puis(int k, int L) {
    	int res = 1;
    	int tmp = k;
    	for (int l = 0; l < L-1; l++) {
    		res *= tmp;
    		tmp *= tmp;
    	}
    	return res; // res % (1 << L) si L n'est pas sizeof(int)*8
    }
     
    int comb(int  N, int K) {
       int a = 1;
       int b = 1;
       int c = 0;
       int d = 0;
       for (int n = N; n > N - K; n--) {
           int tmp = n;
           red_2(tmp,c);
           a *= tmp;
       }
       for (int k = K; k > 1; k--) {
           int tmp = k;
           red_2(tmp,d);
           b *= tmp;
       }
       int L = sizeof(int) * 8;
       if (c-d > L - 1) return 0;
       int deux_puis_c_d = 1 << (c-d);
       int inv_b = inv_modulo_2_puis(b,L);
     
       return a * inv_b * deux_puis_c_d ;
    }
    moralité : programmer avec des grands nombres ça implique d'utiliser l'arithmétique modulaire

    il manque juste un truc pour être rigoureux :
    pourquoi a^phi(n) = 1 modulo n (si pgcd(a,n) = 1) ?
    - si pgcd(a,n) > 1 alors a n'a pas d'inverse modulo n
    - les éléments qui ont un inverse modulo n forment un groupe multiplicatif ( puisque inv(a * b) = inv(b)*inv(a) )
    - ce groupe possède phi(n) éléments (où phi(n) est l'indicatrice d'Euler : nombre d'entiers entre 1 et n-1 et premiers avec n)
    - l'ordre d'un élément divise l'ordre du groupe (ça se montre en faisant le quotient du groupe par le groupe cyclique engendré par l'élément : le quotient d'un groupe par un autre est un groupe)

  20. #20
    r0d
    r0d est déconnecté
    Expert éminent

    Homme Profil pro
    tech lead c++ linux
    Inscrit en
    Août 2004
    Messages
    4 262
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : tech lead c++ linux

    Informations forums :
    Inscription : Août 2004
    Messages : 4 262
    Points : 6 680
    Points
    6 680
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par kochfet Voir le message
    Merci pour votre intervention mais j'ai décidé d'utiliser boost. Mon problème maintenant comment l'installer et l'utiliser. J'ai passé toute la journée pour l'installer mais sans résultat. J'ai besoin de vos aides et Merciiiii.
    Qu'est-ce qui te pose problème?
    Je t'ai expliqué, en deux étapes:
    1. Récupérer le trunk par un simple checkout (svn/cvs).
    2. Exécuter la ligne de commande que je t'ai donné.
    Quelle étape te pose problème?
    « L'effort par lequel toute chose tend à persévérer dans son être n'est rien de plus que l'essence actuelle de cette chose. »
    Spinoza — Éthique III, Proposition VII

+ Répondre à la discussion
Cette discussion est résolue.
Page 1 sur 2 12 DernièreDernière

Discussions similaires

  1. Combinaisons à 6 chiffres possibles parmi 20 nombres
    Par djbebop dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 14/05/2011, 15h46
  2. Réponses: 2
    Dernier message: 17/10/2008, 19h17
  3. Récupérer une seule valeur parmi plusieurs
    Par geraldgg dans le forum XSL/XSLT/XPATH
    Réponses: 4
    Dernier message: 11/05/2007, 11h26
  4. [XSLT]Recuperer une valeur parmis une liste. (tri)
    Par Asaturne dans le forum XSL/XSLT/XPATH
    Réponses: 2
    Dernier message: 16/06/2006, 18h27
  5. Réponses: 2
    Dernier message: 22/07/2002, 19h02

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