Discussion :

[kochfet]

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;
        }
}

[Davidbrcz]

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

[kochfet]

soit tu calules par reccurence avec une formule correcte.

cela veut dira que ma proposition est fausse??

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 .

[Davidbrcz]

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

[Invité]

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

[kochfet]

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;
}

[kochfet]

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?

[Davidbrcz]

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.