Programmation calcul coef binomiaux

[J-R]

bonjour,

en vue de réaliser une programme sur le calcul des coefficients binomiaux en méthode récursive, j'ai besion de trouver une récursion simple qui peut sastisfaire ce calcul.

pour l'ensemble gradué je prendrais bien avec comme fonction descente ?? .

mais pour définir ma récursion ie trouver F((n,p),x) ...

merci

[nuage]

Salut,
mais connaissances en algorithmique sont trop anciennes pour que je soit certain de bien te comprendre.
Quand même un indice (si j'ai bien compris)

[J-R]

bonjour,

oui en effet j'avais pensé ce genre de formule et notamment la célèbre

seulement il faudrait rester sur le entiers car d'après mon prof, on se ramène sur des flottants que quand il est nécessaire (raison de coût) et justement c'est cela que je veux améliorer en prenant une récursion simple...

nan mais sinon c'est bon.

je reste sur ma récursion double (avec Pascal complexité linéaire à C^n_p .... on peut sans doute trouver mieux mais pas le temps).

merci bien et @+

[abcd22]

Bonjour,

en vue de réaliser une programme sur le calcul des coefficients binomiaux en méthode récursive, j'ai besion de trouver une récursion simple qui peut sastisfaire ce calcul.

Quand tu dis récursion simple c'est dans le sens « pas compliqué » ou dans le sens « un seul appel à la fonction, par opposition à la récursion double obtenue avec » ?
Si c'est le premier cas je pense qu'il faut utiliser la formule juste au-dessus même si ce n'est pas du tout efficace. Si on veut calculer efficacement les coefficients binomiaux la solution habituelle est de le faire itérativement en calculant successivement les lignes du triangle de Pascal grâce à la formule ci-dessus; on peut transformer ça en fonction récursive en passant un paramètre supplémentaire (la ligne courante du triangle de Pascal) à la fonction (c'est la façon habituelle de faire des calculs itératifs dans les langages qui n'ont pas de boucle for ou équivalent, comme scheme) mais je ne vois pas trop l'intérêt de faire du récursif juste pour faire du récursif.

[Doraki]

bonjour,

oui en effet j'avais pensé ce genre de formule et notamment la célèbre

seulement il faudrait rester sur le entiers car d'après mon prof, on se ramène sur des flottants que quand il est nécessaire (raison de coût) et justement c'est cela que je veux améliorer en prenant une récursion simple...

nan mais sinon c'est bon.

Meme s'il y a une division tu ne devrais pas avoir besoin de flottants vu que tous les résultats sont entiers.

Et puis comparé avec le temps que mettrait une récursion double (en temps proportionnel au résultat si tu le fais de la manière la plus basique possible ; en temps O(n*p) si tu stockes les résultats intermédiaires), il n'y a pas à hésiter...

[abcd22]

Meme s'il y a une division tu ne devrais pas avoir besoin de flottants vu que tous les résultats sont entiers.

L'ordinateur ne sait pas que le résultat est entier au moment où il fait l'opération (ni même à la fin).
J'ai écrit les 3 versions (en scheme, c'est bien le scheme) : (a) avec récursion double, (b) avec calcul itératif, (c) avec récursion simple mais des fractions. Pour les petites valeurs (b) et (c) renvoient pareil (et (a) aussi mais il met plus longtemps) sauf que le résultat donné par (c) est considéré comme un flottant (1144066.0 et pas 1144066), mais pour les grandes valeurs (b) renvoie le résultat exact et pas (c), par exemple avec (b) renvoie 770746561468507650149628192324 et (c) renvoie 7.70746561468508e29 (et (a) n'est pas près d'avoir terminé). (c) est un peu plus rapide que (b) pour les grandes valeurs mais c'est au prix de l'exactitude du résultat (si les calculs étaient exacts il serait probablement plus lent que (b), les divisions et produits coûtent beaucoup plus cher que les sommes).

Edit: et la différence entre (b) et (c) n'est pas juste au niveau des arrondis, avec on a :
(b) 353600757093566136507612787110853036794237151113912561824416144510382925290233544323102871009782289037916748152467480
(c) 3.5360075709356655e116
ça fait quand même une erreur de l'ordre de 10 puissance 101.

[Doraki]

Scheme peut faire de l'arithmétique exacte avec + et * mais n'a pas de division euclidienne ?

Au hasard, je dirais que le coût du calcul exact de a/b est en complexité log(a)*log(b),
et que le résultat est du e^O(n)
Donc le (c) est normalement du O(n² * log(n)), et le (b) du O(n^3)

[abcd22]

Ah, j'avais fait (n/p) * C_{n - 1}^{p - 1} comme c'était écrit, il fallait faire (n * C_{n - 1}^{p - 1})/p, si on fait ça ça marche effectivement.