4. Binomialkoeffizent auch ohne Fakultät?

Binomialkoeffizent auch ohne Fakultät?

  • M

    Hallöchen.

    Ich programmiere grad an einem kleinen Programm über die Summenfunktion einer binomialverteilten Zufallsgröße.
    Am Programmcode liegt es nicht, da klappt auch alles:

    for(i=1;i<=k;i++)
 wahrscheinlichkeit+= fakultaet(n) / (fakultaet(i)*fakultaet(n-i)) * pow(p,i) * pow(1-p,n-i);  

wahrscheinlichkeit+=pow(1-p,n);

    Das Problem ist, wenn n=100 ist, kommt für n fakultaet eine riesige Zahl raus, die zu viel Rechenleistung in anspruch nimmt und aufgrund des Datentyps zu viel Speicher wegnimmt.

    Gibt es vielleicht noch eine andere Methode, um den Binomialkoeffizenten auszudrücken?

    fakultaet(n) / (fakultaet(i)*fakultaet(n-i))

    Das ist eindeutig nicht elegant genug

    0
  • H

    Ja, das gibt es.
    Ist aber dann eine baumartige Iteration:

    binom n k = (binom n-1 k-1) + (binom n-1 k) #für 1 <= k <= n
    1 #für k == 0 und n >= 0
    0 #sonst

    int binom (int n, int k) {
  if( k == 0 && n >= 0)
    return 1;
  else if(k >= 1 && k <= n) 
    return binom(n-1, k-1) + binom(n-1, k);
  return 0;
}
    0
  • D

    Klar, Du kannst doch kürzen. Außerdem kannst Du auch die Einzelausdrücke so umgruppieren, daß die Ergebnisse klein bleiben.

    Beispiel: bin(49, 6) = 49!/(6!*(49-6)!) = (49*48*47*46*45*44) / (1*2*3*4*5*6) = 49 / 1 * 48 / 2 * 47 / 3 ... / 6

    Dabei geht, wenn man von links nach rechts rechnet, jede Division glatt auf, also kann man ein iteratives Verfahren dafür hinschreiben.

    0
  • M

    Danke für die rasche Antwort.
    Jetzt klappt alles bestens.

    0
  • M

    Sorry hehejo, aber ich muss doch nochmal nachhaken.
    Für n=30 geht das ja noch aber wenn ich was höheres einsetze macht der nix mehr.
    Da rechnet der irgendwie so lange, bis ich das Programm selbst abbreche.
    Hab deinen Code genau übernommen.

    0
  • S

    Ist bei 'ner Baumrekursion nunmal so, die hat eben exponentielle Laufzeit. Man koennte da jetzt noch dran optimieren, so dass man auf O(n^2) kommt, oder gleich die Variante von Daniel E. nehmen. Die hat naemlich O(n)

    0
  • ?

    Du kannst die Fakultät auch mit der Stirling-Formel annähern.

    0
  • M

    Ich habe versucht diesen Vorschlag umzusetzen, aber irgendwo hab ich einen Fehler den ich absolut nicht finde.

    int binomkoeff(int n, int k) { 
    int i, koeff=1;
    if((k==0)&&(n>=0)) 
        return 1; 
    else if((k>=1)&&(k<=n)){
        for(i=1;i<=k;i++)
                koeff*=(n-i+1)/i;
        printf("\n%i",koeff);
        return koeff; 
    };           
  return 0; 
};

    Der Debugger meldet nichts und für i=1 stimmt der koeffizent.
    Nur für die anderen ist er falsch.

    0
  • M

    Sorry wenn ich hier einen Mist schreibe.
    Bei genauem Nachdenken hab ich gemerkt, dass da auch mal ein Bruch als zwischenergeniss rauskommt.

    Vielmals Entschuldigung

    0
  • D

    Max3000 schrieb:

    Ich habe versucht diesen Vorschlag umzusetzen, aber irgendwo hab ich einen Fehler den ich absolut nicht finde.

    int binomkoeff(int n, int k) { 
    int i, koeff=1;
    if((k==0)&&(n>=0)) 
        return 1; 
    else if((k>=1)&&(k<=n)){
        for(i=1;i<=k;i++)
                koeff*=(n-i+1)/i;

    Diese Zeile ist falsch, *weil* so Brüche rauskommen. Ich habe gesagt, Du sollst von links nach rechts rechnen, also:
    koeff = (koeff*(n-i+1))/i

    oder so

    0
Anmelden zum Antworten