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!
Gausi hat folgendes geschrieben : |
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; 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..25] of LongInt;
procedure pasdreieck(L:longint); var j,k: longInt; begin a[0] := 1; j := 0; while (j<L) do begin inc(j); k := (j+1) div 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,'|'); For i := 13 to 25 do Write(i:3,a[25-i]:12,'|'); end. |
Natürlich ist die Variante, die
Gammatester 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
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!