# C et C++ > C > Contribuez >  Calcul direct des coefficients du binome

## orthomimi

Bonjour  tous

Je me suis intress, par ces grosses chaleurs, au calcul des coefficients du binme : j'ai utilis cette rcurrence qui m'a sembl assez rapide.

Etant peu familiaris avec les programmes rcursifs, j'ai opt pour le calcul direct.

La question finale sera , bien sur : comment feriez vous cela en rcursif ?



D'abord le principe de la rcurrence :

*c(n,k)=n!/(n-k)!*k!*  est le k ime coefficient de x^(n-k) dans le dveloppement 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 rcurrence 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 procd rcursif, soit remonter depuis c(n-k,0)=1 jusqu'  c(n,k) : c'est ce que j'ai fait.

L'algorithme est le suivant :



```

```

Ds que l'on veut faire de trs gros calculs il faut utiliser gmp !



```

```

On peut vrifier le rsultat directement avec la fonction de gmp, *mpz_bin_uiui* 



```

```

pour ne pas faire d'erreurs il vaut mieux s'assurer que k<n donc mettre au dbut



```

```

et profiter ensuite de la symtrie des coefficients dans le dveloppement du binome :



```
if (k > n/2) k=n-k;
```


Voici maintenant le programme complet



```

```


Il faut avoir pralablement charg gmp : pour ma part j'utilise la bibliothque fixe de gmp : libgmp.a
et le "include" : gmp.h.
Ceux ci seront placs 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 rcursif : 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.

----------


## WhiteCrow

Bonjour,

Si tu regardes les coefficients d'un peu plus prs tu remarqueras que


Du coup il n'y a aucun souci  calculer tous les coefficients binomiaux au moins jusqu' la ligne 67 du triangle de Pascal.
Ensuite le plus simple est de prcalculer le triangle, un tableau statique de 6868 ; une fois calcul accder  un coef particulier n'est qu'un accs RAM.
En ce qui concerne le calcul rien de plus simple : tu initialises la premire ligne avec {1,0} et ensuite pour chaque ligne suivante tu initialises le premier lment  1 puis tu appliques la formule classique pour le calcul.

Si tu veux t'affranchir du prcalcul, tu le fais une premire fois et tu gnres un .h qui encode ce tableau statiquement 


Edit : un petit code qui va bien avec :


```

```

Edit 2 : la modification du code pour arriver  sortir un header est relativement simple.

----------


## orthomimi

Bonsoir et merci de ta rponse

Je ne souhaitais pas utiliser le triangle de Pascal car je voulais pouvoir calculer des coefficients avec de trs gros "n" et "k" donc viter l'addition et me rapprocher  ainsi des techniques d'exponentiation rapide.

Je viens de faire deux essais avec mon programme :

- n=100001, k=45657 : rponse est instantane ; nb de chiffres du coefficient : 29937.
- n=1000057, k=356572 : 9 secondes de calcul ; nb de chiffres du coefficient 282917. 

Je pense que pour de trs gros chiffres, le calcul sera plus lent avec les sries d'addition du triangle.

La question que je posais tait en fait la suivante : en se servant de cet algorithme comment crire la rcursion, donc partir du haut et sur la dfinition, alors que, actuellement, je pars d'en bas et cela m'oblige  "siouxer" sur les conditions du point de dpart.

Autre intrt, cet algorithme est extrment court : une ligne de code en fait.

Il est possible qu'avec Python cela aille aussi vite  calculer, mais je ne sais pas car je n'ai pas essay.

Amicalement

----------


## WhiteCrow

Alors si tu veux un algo rcursif juste pour crire un code rcursif c'est jamais compliqu, mais en gnral toujours inadapt. Dans ce cas tu suis au pied de la lettre une dfinition mathmatique rcursive :


Le code que l'on peut tirer de cette dfinition pourrait ressembler  :


```

```

Tu te rendras vite compte que ce code est inefficace  moins de mmoser les rsultats.

Aprs si tu manipules un peu tout a tu pourras remarquer que :


Cela peut te donner une indication pour une autre approche rcursive. Mais bon, si tu veux en plus manipuler des entiers  prcision arbitraire tu vas vite te retrouver face  des temps d'excution rdhibitoires.

----------


## orthomimi

Bonsoir et merci de ta rponse.
Je viens de tester mon algorithme versus celui de gmp : il y a encore beaucoup de progrs  faire pour le concurrencer en rapidit.
J'ai en effet calcul 1 seconde contre 9 pour mon dernier essai.
Je vais donc recreuser la question et chercher une autre mthode plus rapide.

----------


## WhiteCrow

Dans ce cadre il vaut mieux ne pas utiliser la rcursivit mais driver cette formule pour 1<k≤n de la dernire relation que je t'ai donn :


en prenant soin d'utiliser la symtrie des coefs

----------


## orthomimi

Tu as raison.
Et encore merci.

----------

