Autor |
Beitrag |
Anika
      
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: Do 07.03.13 12:03
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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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.
_________________ We are, we were and will not be.
Für diesen Beitrag haben gedankt: Anika
|
|
WasWeißDennIch
      
Beiträge: 653
Erhaltene Danke: 160
|
Verfasst: 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]
Zuletzt bearbeitet von WasWeißDennIch am Do 07.03.13 12:36, insgesamt 1-mal bearbeitet
|
|
Anika 
      
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: 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
      
Beiträge: 8548
Erhaltene Danke: 477
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: 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.
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.
_________________ We are, we were and will not be.
Für diesen Beitrag haben gedankt: Anika
|
|
Anika 
      
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: 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
      
Beiträge: 328
Erhaltene Danke: 101
|
Verfasst: 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.
Für diesen Beitrag haben gedankt: Anika, Martok
|
|
Horst_H
      
Beiträge: 1654
Erhaltene Danke: 244
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: 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.
velociraptor.mni.fh-...00066300000000000000
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.
www.entwickler-ecke.....php?p=412914#412914
Zuletzt bearbeitet von Horst_H am Do 07.03.13 18:30, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Anika
|
|
Anika 
      
Beiträge: 30
Erhaltene Danke: 2
Windows 7
Delphi 7
|
Verfasst: 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
|
|