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 :

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;
}
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
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
}
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
 
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
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
5
if (k > n) 
{
	puts("k supérieur a n");
	exit(-1);
}
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
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.