IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Discussion :

Calcul direct des coefficients du binome


Sujet :

Contribuez

  1. #1
    Membre à l'essai
    Homme Profil pro
    chirurgien retraité
    Inscrit en
    Mai 2018
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 76
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : chirurgien retraité
    Secteur : Santé

    Informations forums :
    Inscription : Mai 2018
    Messages : 21
    Points : 15
    Points
    15
    Par défaut Calcul direct des coefficients du binome
    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 :


    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.

  2. #2
    Membre expérimenté
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    Juillet 2020
    Messages
    352
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : Juillet 2020
    Messages : 352
    Points : 1 376
    Points
    1 376
    Par défaut
    Bonjour,

    Si tu regardes les coefficients d'un peu plus près tu remarqueras que
    Formule mathématique

    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 précalculer le triangle, un tableau statique de 68×68 ; une fois calculé accéder à un coef particulier n'est qu'un accès RAM.
    En ce qui concerne le calcul rien de plus simple : tu initialises la première ligne avec {1,0} et ensuite pour chaque ligne suivante tu initialises le premier élément à 1 puis tu appliques la formule classique pour le calcul.

    Si tu veux t'affranchir du précalcul, tu le fais une première fois et tu génères un .h qui encode ce tableau statiquement …


    Edit : un petit code qui va bien avec :
    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
    #include <inttypes.h>
    #include <stdint.h>
    #include <stdio.h>
     
    #define MAX_N ((size_t)68)
     
    static uint64_t coefs[MAX_N][MAX_N] = {
        {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1},
        {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1},
        {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1},
        {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1},
        {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1}, {1},
    };
     
    void _init_coefs(void) {
      for (size_t n = 1; n < MAX_N; n++) {
        for (size_t k = 1; k < MAX_N; k++) {
          coefs[n][k] = coefs[n - 1][k - 1] + coefs[n - 1][k];
        }
      }
    }
     
    int main(void) {
      _init_coefs();
      for (size_t n = 0; n < MAX_N; n++) {
        for (size_t k = 0; k <= n; k++) {
          printf("%" PRIu64 " ", coefs[n][k]);
        }
        putchar('\n');
      }
    }
    Edit 2 : la modification du code pour arriver à sortir un header est relativement simple.

  3. #3
    Membre à l'essai
    Homme Profil pro
    chirurgien retraité
    Inscrit en
    Mai 2018
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 76
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : chirurgien retraité
    Secteur : Santé

    Informations forums :
    Inscription : Mai 2018
    Messages : 21
    Points : 15
    Points
    15
    Par défaut reponse
    Bonsoir et merci de ta réponse

    Je ne souhaitais pas utiliser le triangle de Pascal car je voulais pouvoir calculer des coefficients avec de très 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 : réponse est instantanée ; 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 très gros chiffres, le calcul sera plus lent avec les séries d'addition du triangle.

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

    Autre intérêt, cet algorithme est extrèment 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

  4. #4
    Membre expérimenté
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    Juillet 2020
    Messages
    352
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : Juillet 2020
    Messages : 352
    Points : 1 376
    Points
    1 376
    Par défaut
    Alors si tu veux un algo récursif juste pour écrire un code récursif c'est jamais compliqué, mais en général toujours inadapté. Dans ce cas tu suis au pied de la lettre une définition mathématique récursive :
    Formule mathématique

    Le code que l'on peut tirer de cette définition pourrait ressembler à :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
     
    int choose(int n, int k) {
        if ( (k==0) || (k==1) ) return 1;
        else if ( k>n ) return 0;
        else return choose(n-1,k-1)+choose(n-1,k);
    }
    Tu te rendras vite compte que ce code est inefficace à moins de mémoïser les résultats.

    Après si tu manipules un peu tout ça tu pourras remarquer que :
    Formule mathématique

    Cela peut te donner une indication pour une autre approche récursive. Mais bon, si tu veux en plus manipuler des entiers à précision arbitraire tu vas vite te retrouver face à des temps d'exécution rédhibitoires.

  5. #5
    Membre à l'essai
    Homme Profil pro
    chirurgien retraité
    Inscrit en
    Mai 2018
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 76
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : chirurgien retraité
    Secteur : Santé

    Informations forums :
    Inscription : Mai 2018
    Messages : 21
    Points : 15
    Points
    15
    Par défaut
    Bonsoir et merci de ta réponse.
    Je viens de tester mon algorithme versus celui de gmp : il y a encore beaucoup de progrès à 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 méthode plus rapide.

  6. #6
    Membre expérimenté
    Homme Profil pro
    Chef de projet NTIC
    Inscrit en
    Juillet 2020
    Messages
    352
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Chef de projet NTIC

    Informations forums :
    Inscription : Juillet 2020
    Messages : 352
    Points : 1 376
    Points
    1 376
    Par défaut
    Dans ce cadre il vaut mieux ne pas utiliser la récursivité mais dériver cette formule pour 1<k≤n de la dernière relation que je t'ai donné :
    Formule mathématique

    en prenant soin d'utiliser la symétrie des coefs
    Formule mathématique

  7. #7
    Membre à l'essai
    Homme Profil pro
    chirurgien retraité
    Inscrit en
    Mai 2018
    Messages
    21
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 76
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : chirurgien retraité
    Secteur : Santé

    Informations forums :
    Inscription : Mai 2018
    Messages : 21
    Points : 15
    Points
    15
    Par défaut
    Tu as raison.
    Et encore merci.

  8. #8
    Rédacteur/Modérateur

    Avatar de Roland Chastain
    Homme Profil pro
    Enseignant
    Inscrit en
    Décembre 2011
    Messages
    4 058
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 50
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Décembre 2011
    Messages : 4 058
    Points : 15 339
    Points
    15 339
    Billets dans le blog
    9
    Par défaut
    Intéressante discussion. Dommage que les liens vers les formules soient cassés.

    N'étant pas un professionnel des mathématiques, je n'ai pas bien compris l'objet de la discussion. Le binôme. Quel binôme ? Quel problème veut-on résoudre exactement ?
    Mon site personnel consacré à MSEide+MSEgui : msegui.net

Discussions similaires

  1. Réponses: 2
    Dernier message: 27/06/2007, 11h42
  2. Calcul à partir des résultats d'une requète
    Par Sendo dans le forum Access
    Réponses: 1
    Dernier message: 29/09/2005, 18h46
  3. calculer à travers des lignes de dbgrid
    Par bertrand_declerck dans le forum Bases de données
    Réponses: 2
    Dernier message: 25/07/2005, 12h55
  4. Calcul dans des champs de saisie
    Par leeloo076 dans le forum ASP
    Réponses: 4
    Dernier message: 07/04/2004, 11h09
  5. Réponses: 4
    Dernier message: 15/12/2002, 05h19

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo