Binomialkoeffizient

LinuxC_newbie

Bekanntlich ist der Binomialkoeffizient n über k definiert als

n!((n-k)!k!)

Wegen des Zahlenüberlaufs bei der Berechnung ab 16! lässt sich der Binomialkoeffizient nicht mehr als Quotient aus Fakultäten berechnen.

Kürzen Sie und schreiben Sie dann eine Funktion int binomial(int n, int k), um den Binomialkoeffizienten gekürzt zu berechnen.

Überprüfen Sie, ob sie 49 über 6 richtig berechnen können.

-------

Also ich würde zum Beispiel 16 über 3 so gekürzt berechnen:

(16*15*14)/(3*2*1)

Als Code habe ich dies hier:

#include <iostream>
using namespace std;

int binomial(int n,int k){
  int m=n;
  int p=1;
  for(int i=1; i<k; i++){
    m *= (n-i);
    p *= (i+1);
  }
 return m/p;
}

int main(){
  cout << "(16 3)=" << binomial(16,3) << endl;
  cout << "(16 7)=" << binomial(16,7) << endl;
  cout << "(49 6)=" << binomial(49,6) << endl;
}

Dies liefert

(16 3)=4368
(16 7)=11440
(49 6)=2053351

Die ersten beiden Ergebnisse stimmen, das letzte nicht.
Was habe ich falsch gemacht?

Tipp: Du kannst

(16*15*14)/(3*2*1)

als

((((16/1)*15)/2)*14)/3 berechnen

volkard

LinuxC_newbie schrieb:

(16*15*14)/(3*2*1)

16/1*15/2*14/3
Überzeuge Dich davon, daß die Division immer glatt aufgeht, tut sie nämlich.

LinuxC_newbie

Hm, da kommt dann für 16 über 3 aber auch nicht das Richtiges heraus.

volkard

LinuxC_newbie schrieb:

Hm, da kommt dann für 16 über 3 aber auch nicht das Richtiges heraus.

http://bit.ly/14eIicw

volkard

LinuxC_newbie schrieb:

Dies liefert

(16 3)=4368
(16 7)=11440
(49 6)=2053351

Die ersten beiden Ergebnisse stimmen,

In welchem Universum?

LinuxC_newbie schrieb:

Dies liefert

(16 3)=4368
(16 7)=11440
(49 6)=2053351

http://ideone.com/e2BM0nBei mir liefert das aber

(16 3)=560
(16 7)=11440
(49 6)=2053351

minastaros

universum nr. 42 schrieb:

LinuxC_newbie schrieb:

Dies liefert

(16 3)=4368
(16 7)=11440
(49 6)=2053351

http://ideone.com/e2BM0nBei mir liefert das aber
(16 3)=560
(16 7)=11440
(49 6)=2053351

http://www.wolframalpha.com/input/?i=binomial+coefficient+(49+6) liefert jedoch

(49 6) = 13983816

LinuxC_newbie

Nur verstehe ich nicht, was ich da falsch aufschreibe:

int binomial(int n,int k){
   int m=n;
   for(int i=1; i<k; i++){
       m *= ((n-i))/(i+1);
   }

return m;
}

SeppJ

Das ist nicht die Klammerung, die dir gezeigt wurde. Integerarithmetik ist nicht kommutativ.

LinuxC_newbie

Ich krieg das nicht allgemein aufgeschrieben

int binomial(int n,int k){

     int m=n;
     for(i=1; i<k; i++){
      m *= (m*(n-i))/(i+1);
     }
return m;
}

Stimmt auch nicht.

SeppJ

Versuch doch nicht zwanghaft alles in eine Zeile zu schreiben. Und denk nach, anstatt zufällig Klammern zu verteilen.

Weißt du inzwischen, warum die Reihenfolge wichtig ist?

Weißt du überhaupt, was *= und Konsorten genau machen? Was ist folgendes?

int i = 5;
i *= 4 - 3;
// i?

LinuxC_newbie

Ich habe es nun hinbekommen, danke.

Nochmal folgende Frage:

Wieso macht es einen Unterschied, ob man

16/1 * 15/2 * 14/3

rechnet oder

(16*15*14)/(3*2*1)

?

Weil man im ersten Fall immer nur relativ kleine Faktoren multipliziert, während man im zweiten Fall ziemlich große Zähler und Nenner bekommen kann und die dann nicht mehr genau dargestellt werden können?

volkard

Weil man im ersten Fall immer nur relativ kleine Faktoren multipliziert, während man im zweiten Fall ziemlich große Zähler und Nenner bekommen kann und die dann nicht mehr genau dargestellt werden können?

Nein.

Wieso macht es einen Unterschied, ob man

16/1 * 15/2 * 14/3

rechnet oder

(16*15*14)/(3*2*1)

Du hast es IMMER NOCH NICHT kapiert.

Du rechnest NICHT (16/1) * (15/2) * (14/3). Deswegen schreib das auch nicht so hin. Du hast auch NICHT lauter kleine Faktoren 16 * 7.5 * 4.666

Rechne mal mit dem Taschenrechner selber nach.
1
*16=
/1=
*15=
/2=
*14=
/3=

LinuxC_newbie

Ich weiß, dass man es anders klammern muss.

Aber ich verstehe eben nicht, wieso und wieso dann klappt.

SeppJ

Die Frage mag dir jetzt vielleicht doof vorkommen^*, ist sie aber nicht. Daher beantworte sie bitte:

Wie viel ist 7/2?

Zusatzfragen: Wie viel ist (4 * 7) / 2? 4 * (7 / 2)?
Krönungsfrage: Wie viel ist 4 * 7 / 2?

Am besten alle Antworten mit Begründung, nicht einfach nur raten (oder gar ausprobieren).

^*: Falls die Frage dir doof vorkommt, ist es sogar ein ziemlich sicheres Zeichen, dass du die Antwort nicht kennst.

volkard

LinuxC_newbie schrieb:

Ich weiß, dass man es anders klammern muss.

Aber ich verstehe eben nicht, wieso und wieso dann klappt.

Wieso? Um möglichst früh zu teilen, damit die Zwischenergebnisse möglichst klein bleiben. "Möglichst früh" heißt dabei aber trotzdem so spät, daß man garantieren kann, daß keine Kommazahl passiert. Es muss alles mit ganzen Zahlen klappen. Auch jedes Zwischenergebnis.

Wieso klappts? Da hilft zum Begreifen die Beobachtung, daß unter fünf aufeinanderfolgenden Zahlen sicher wenigstens eine dabei ist, die durch fünf teilbar ist. Oder einfach hinnehmen, daß bei deser Schleife die Zwischenergebnisse die Zahlen sind, die im Pascalschen Dreieck links vom Ergebnis stehen und die sind alle ganzzahlig.

camper

(n k) = ((n k-1) * (n-k+1)) / k
und (n k-1) ist nat. auch eine ganze Zahl
Mit ein bisschen Aufwand kann man noch ein paar größere Binomialkoeefizienten ausrechnen.

#include <iostream>

using namespace std;

typedef unsigned long long int_type;

int_type gcd(int_type a, int_type b){
  return a ? gcd( b % a, a ) : b;
}

int_type binomial_(int_type n,int_type k){
  int_type x = k > 1 ? binomial_( n, k-1 ) : 1;
  int_type gcd_ = gcd( n-k+1, k );
  return x / ( k / gcd_ ) * ( (n-k+1) / gcd_ );
}
int_type binomial(int_type n,int_type k){
  return 2*k<=n ? binomial_( n, k ) : binomial_( n, n-k );
}

int main(){
  cout << "(6 3)=" << binomial(6,3) << endl;
  cout << "(6 2)=" << binomial(6,2) << endl;
  cout << "(49 6)=" << binomial(10,5) << endl;
  cout << "(66 33)=" << binomial(66,33) << endl;
}