Entwickler-Ecke

Sonstiges (Delphi) - Fehler bei Binomialkoeffizient


Anika - Do 07.03.13 12:03
Titel: Fehler bei Binomialkoeffizient
Guten Tag,
zum Vorbereiten eines anderen Programms sollen wir Binominalkoeffizienten berechnen.
Mein Programm ist

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
procedure TForm1.Button1Click(Sender: TObject);
var n,i:integer;
    binomialkoeffizient:int64;
function fak(n:integer):int64;
var f:int64;
    i:integer;
begin
    f:=1;
    for i:=1 to n do f:=f*i;
    fak:=f;
end;
begin
    n:=strtoint(edit1.Text);
    memo1.Clear;
    for i:=1 to n do
    begin
      binomialkoeffizient:=fak(n) div fak(n-i) div fak(i);
      memo1.lines.add(inttostr(n)+#9+inttostr(i)+#9+inttostr(binomialkoeffizient));
    end;
end;

Das klappt auch gut, aber bei 21 bekomme ich negative Zahlen. Zum Beispiel 21 über 9 ist -24446.
Das verstehe ich nicht. Das Ergebnis ist richtig falsch.
Kann mir jemand helfen.

Danke Anika


Gausi - Do 07.03.13 12:15

21! als Zwischenergebnis bei der BK-Berechnung passt schon nicht mehr in einen Int64. Dann kommt es zu einem Überlauf, und die Ergebnisse werden falsch.

Wenn du den BK auch für größere Werte berechnen willst, muss du auf alternative Methoden umsteigen, z.B. über das Pascalsche Dreieck.


WasWeißDennIch - Do 07.03.13 12:16

Kann es sein, dass Du mit Deinen Variablen/Parametern durcheinander geraten bist? Wo wird in fak denn der Parameter n benutzt?

[edit] Ah, OK, jetzt habe ich es entdeckt [/edit]


Anika - Do 07.03.13 12:27

Vielen Dank Gausi!
user profile iconGausi hat folgendes geschrieben Zum zitierten Posting springen:
Wenn du den BK auch für größere Werte berechnen willst, muss du auf alternative Methoden umsteigen, z.B. über das Pascalsche Dreieck.

Tut mir leid, das verstehe ich nicht. Bei Wikipedia steht das im pascalschen Dreieck die Binominalkoeffizinten sind. Wie kann ich das denn anders machen?
Ich habe von einem efizienten Algorithmus gelesen mit einem Produkt (n-k+i)/i. Da braucht man aber keine Fakultät.

Danke Anika


Gausi - Do 07.03.13 12:35

Die schnellste Methode kenn ich jetzt auswendig auch nicht. Zum Pascalschen Dreieck: Ja, darin stehen die Binomialkoeffizienten. Aber man bekommt die Werte in diesem Dreieck durch einfache Additionen heraus, schau dir mal das animierte Gif oben rechts an - da wird das Prinzip recht deutlich.

http://de.wikipedia.org/wiki/Pascalsches_Dreieck

Um dann n über k zu berechnen, muss man das das Dreieck bis zur Ebene n aufbauen - dabei reichen auf jeder Stufe die ersten k Einträge. Die Werte weiter rechts braucht man nicht.

Man braucht dann ein Array der Länge k, initial alle 0 bis auf das erste (das ist 1) und dann in einer doppelten for-Schleife die Werte berechnen. Dabei aufpassen, welche Werte man aus der Zeile davor noch braucht, bevor man die überschreibt - das sollte mit ein oder zwei Hilfsvariablen gehen.


Anika - Do 07.03.13 12:46

Danke Gausi,
das habe ich verstanden. Ich werde mein Programm ändern und mich dann wieder melden.

Danke Anika


Gammatester - Do 07.03.13 12:50

Du kannst für größere n den Binomal-Koeffizient auch direkt berechnen ohne Fakultäten: Es gilt doch n!/k!/(n-k)! = (n*(n-1)...(n+1-k))/(1*2...k) = (n/1)*((n-1)/2) ... ((n+1-k)/k). Interessant ist, daß wenn Du die Reihenfolge einhältst, alle Divisionen ohne Rest aufgehen. Als Pascal-Funktion:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
function bin(n,k: longint): longint;
  { binomial(n,k) = n!/k!/(n-k)! = n*(n-1).../k!}
var
  b, i: longint;
begin
  b := n;
  for i:=2 to k do b := b*(n+1-i) div i;
  bin := b;
end;

begin
  writeln(bin(25,9));
end.

liefert den richtigen Wert binomial(25,9) = 2042975.


Horst_H - Do 07.03.13 15:32

Hallo,

das Pascal'sche Dreieck muss man ja nicht als Dreieck nehmen, sondern kann getrost in einer Zeile der maximalen_Länge/2 +1 rechnen und es kommen nur Additionen vor.
http://velociraptor.mni.fh-giessen.de/Programmierung/progI-html-dir/node6.html#SECTION00066300000000000000

Delphi-Quelltext
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:
var
  a : array[0..25of LongInt;

procedure pasdreieck(L:longint);
var
  j,k: longInt;
begin
  a[0] := 1;
  j    := 0;
  while (j<L) do begin
    inc(j);
    k := (j+1div 2;
    a[k] :=a[k-1];
    For k := k downto 1 do
      a[k] := a[k-1] + a[k];
    end;
end;

var
  i: longint;
Begin
  pasdreieck(25);
  For i := 0 to 12 do
    Write(i:3,a[i]:12,'|');
  // Wegen Symmetrie    
  For i := 13 to 25 do
    Write(i:3,a[25-i]:12,'|');
end.

Natürlich ist die Variante, die user profile iconGammatester vorschlägt, schneller und kompakter.

Gruß Horst
Ein kleines EDIT:
Die Version von Gammatester kann man etwas beschleunigen, wenn bei das k bei (n über n) > (n div 2) ist.
Denn (n über k) = (n über (n-k)), sieht man anschaulich an der Symmetrie des Pascal'schen Dreiecks.
http://www.entwickler-ecke.de/viewtopic.php?p=412914#412914


Anika - Do 07.03.13 16:15

Hallo Gammatester,
Hallo Horst_H,
vielen Dank für Eure Hilfe. Ich werde beide Lösungen ausprobieren und versuchen zu verstehen.

Danke
Anika