funktion für den binomialkoeffizienten?



  • Hallo,

    Gibt es eine funktion für den binomialkoeffizienten?

    mfg



  • nix fertiges jedenfalls. das war doch irgendwas mit fakultäten, oder? musste dir jedenfalls selber schreiben.
    🙂



  • teflon2 schrieb:

    Hallo,
    Gibt es eine funktion für den binomialkoeffizienten?
    mfg

    ja. auf deime taschenrechner die taste nCr.
    aber keine fertige in den headerfiles von c.
    den pseudocode auf http://de.wikipedia.org/wiki/Binomialkoeffizient haste bestimmt in einem viertel stündchen nach c übersetzt.



  • Habe mal so ne Funktion in C geschrieben, ohne Gewähr 🙂

    /*------------------------------------------------------------------*
     *                        n       n   n - k + 1     n       n       *
     *  Binomialkoeffizient (   ) = (   ) --------- , (   ) = (   ) = 1 *
     *                        k      k-1      k         0       n       *
     *                                                                  *
     *  Rekursive Berechnung, damit keine zu grossen Zahlen entstehen   *
     *------------------------------------------------------------------*/
    
    long int bin (long int n, long int k)
       {
       long int i;
       long int binomialkoeffizient = 1;
    
       if (n <  0 || n > 20 || k < 0 || k > n) return (-1);
    
       if (k == 0 || k == n) return (binomialkoeffizient);
    
       for (i = 1; i <= k; i++)
          binomialkoeffizient = binomialkoeffizient * (n - i + 1) / i;
       return (binomialkoeffizient);
       }
    

    Gruß,

    Andreas



  • bisschen spät, aber ich sehe da keine rekursion..

    fehlerchecks nicht vorhanden, aber müsste so gehen:

    int binominal (int n, int k){
        int tmp0,tmp1;
        if (( k ==0 ) || (n == k)){
            return 1;
        }
        else{
            tmp0 = binominal (n - 1, k);     // hier ist die rekursion ;)
            tmp1 = binominal (n - 1, k - 1); // und hier 
            return tmp0 + tmp1;
        }
    }
    


  • Da steht rekursive Berechnung, nicht rekursiver Funktions-
    aufruf. Wer lesen kann ist klar im Vorteil.



  • dem würde man dann aber iterative berechnung sagen..

    die erste funktion ist falsch!
    die zwischenresultate sind nicht ganzzahlig, müsste also mit float gemacht werden, das ist dann aber auch nicht so optimal. genauso wie eine rekursive lösung.

    hier mein vorschlag:

    unsigned int fac(int n)
    {
    unsigned int t=1;
    for (int i=n;i>1;i--)
    t*=i;
    return t;
    }
    unsigned int binCoeff2(int n, int k)
    {
    if (k == 0 || k == n)
    return 1;
    else if (n == 0 || k > n)
    return 0;
    else
    return fac(n)/(fac(n-k)*fac(k));
    }



  • Man läuft generell in das Problem, dass Binomialkoeffizienten verdammt groß werden können - von den Fakultäten bei der direkten Berechnung ganz zu schweigen.

    Ich denke, es wäre einen Versuch wert, den Binomialkoeffizienten über die Gamma-Funktion als Fließkommazahl auszurechnen. Natürlich ist das dann nur so genau wie die Mantisse, aber es ist immer noch besser als ein Integer-Overflow.

    long double bin_coeff(unsigned n, unsigned k) {
      return tgammal(n + 1) / (tgammal(k + 1) * tgammal(n - k + 1));
    }
    


  • flarno schrieb:

    dem würde man dann aber iterative berechnung sagen..

    die erste funktion ist falsch!
    die zwischenresultate sind nicht ganzzahlig, müsste also mit float gemacht werden, das ist dann aber auch nicht so optimal. genauso wie eine rekursive lösung.

    Die von AndreasBo?
    Die ist richtig, würde ich sagen. Also wenigstens nicht wegen Rundungsfehlern falsch.
    Faszinierenderweise geht die Division IMMER glatt auf.



  • Naja, so faszinierend ist das jetzt auch nicht. Beim ersten mal ist i=1, da stellt sich die Frage nicht. Beim zweiten mal ist i = 2, und n - i + 1 ist entweder in diesem oder war im letzten Schleifendurchlauf durch zwei teilbar. Beim nächsten mal ist i = 3, und in einem der drei Durchläufe war der Zähler durch drei teilbar. Und so weiter.



  • seldon schrieb:

    Naja, so faszinierend ist das jetzt auch nicht. Beim ersten mal ist i=1, da stellt sich die Frage nicht. Beim zweiten mal ist i = 2, und n - i + 1 ist entweder in diesem oder war im letzten Schleifendurchlauf durch zwei teilbar. Beim nächsten mal ist i = 3, und in einem der drei Durchläufe war der Zähler durch drei teilbar. Und so weiter.

    Ich halte es da wie elise und kann mich über Kleinigkeiten total freuen.


Log in to reply