Bonjour à tous
Je me suis intéressé, par ces grosses chaleurs, au calcul des coefficients du binôme : j'ai utilisé cette récurrence qui m'a semblé assez rapide.
Etant peu familiarisé avec les programmes récursifs, j'ai opté pour le calcul direct.
La question finale sera , bien sur : comment feriez vous cela en récursif ?
D'abord le principe de la récurrence :
c(n,k)=n!/(n-k)!*k! est le k ième coefficient de x^(n-k) dans le développement de (x+1)^n ( avec c(n,0)=1 et c(n,1)=n )
c(n,k)=c(n-1,k-1)*n/k car :
n!/(n-k)!*k = (n-1)!*n/(n-1-(k-1))!*(k-1)*k
ou encore
n!/(n-k)!*k=(n-1)!/(n-1-(k-1))!*(k-1) * n/k
donc : c(n,k)=c(n-1,k-1) * n/k
En descendant la récurrence pas à pas :
c(n,k)=c(n-1,k-1) * n/k pour i=0
.
.
c(n-j,k-i)=c(n-j-1,k-i-1) * (n-j)/k-j) pour i=j
.
.
c(n-k+1,1)=c(n-k,0) * (n-k+1) : et c(n-k,0)=1 pour i=k-1
d'où:
c(n-k+1,1)= (n-k+1) pour i=k-1
On peut, soit descendre en partant de i=0 jusqu' à i=k-1 par un procédé récursif, soit remonter depuis c(n-k,0)=1 jusqu' à c(n,k) : c'est ce que j'ai fait.
L'algorithme est le suivant :
Dès que l'on veut faire de très gros calculs il faut utiliser gmp !
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7 int n=?, k=?, i=0; long long int c=1; //mais on verra que l'on sera vite limité par la taille des coefficients for (i=0; i<k; i++ ) { c=c*(n-k+i+1)/i+1; }
On peut vérifier le résultat directement avec la fonction de gmp, mpz_bin_uiui
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9 int n=?, k=?, i=0; mpz_t c; mpz_init_set_ui(c,1);// le coefficient en mpz_t for (i=0; i<k; i++) { mpz_mul_ui(c, c, n-k+i+1); // c=c*(n-k+i+1) mpz_divexact_ui(c, c, i+1); // c=c/i+1 }
pour ne pas faire d'erreurs il vaut mieux s'assurer que k<n donc mettre au début
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 mpz_t rop; mpz_init(rop); mpz_bin_uiui(rop, n, k); gmp_printf("c=%Zd\nrop=%Zd\n", c, rop); //impression des deux résultats
et profiter ensuite de la symétrie des coefficients dans le développement du binome :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5 if (k > n) { puts("k supérieur a n"); exit(-1); }
Code : Sélectionner tout - Visualiser dans une fenêtre à part if (k > n/2) k=n-k;
Voici maintenant le programme complet
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 #include <stdio.h> #include <stdlib.h> #include <gmp.h> // Surtout ne pas l'oublier sinon un gigantesque message d'erreur apparait ! int main(int argc, char const *argv[]) { int n=9, k=4, i=0, j=0; // pas de limitation, en taille, de n et de k. Les chiffres deviennent, néanmoins, rapidement monstrueux if (k > n) { puts("k supérieur a n"); exit(-1); } if (k > n/2) k=n-k; mpz_t c; mpz_init_set_ui(c,1); for (i=0; i<k; i++) { mpz_mul_ui(c, c, n-k+i+1); mpz_divexact_ui(c, c, i+1); } mpz_t rop; mpz_init(rop); / /verification avec la fonction de gmp, mpz_bin_uiui mpz_bin_uiui(rop, n, k); gmp_printf("c=%Zd\nrop=%Zd\n", c, rop); mpz_clears(rop, c, NULL); return 0; }
Il faut avoir préalablement chargé gmp : pour ma part j'utilise la bibliothèque fixe de gmp : libgmp.a
et le "include" : gmp.h.
Ceux ci seront placés respectivement dans deux dossiers distincts, au sein du dossier de travail : "lib" et "include".
Si le programme est coef.c ( je suis sur mac ) :
clang -I include -Llib coef.c -lgmp -o coef
suivi de
./coef
Je demande maintenant aux savants de ce groupe ( pour toi Sve@r...) comment ils feraient ce programme en récursif : car je l'avoue, et je n'aime pas trop cette technique , et surtout, je la comprends mal.
Merci de votre aide à tous et de votre patience pour avoir tout lu.
Partager