Autor Beitrag
Anika
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: Do 07.03.13 12:03 
Guten Tag,
zum Vorbereiten eines anderen Programms sollen wir Binominalkoeffizienten berechnen.
Mein Programm ist
ausblenden 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 653
Erhaltene Danke: 160



BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starofftopic starofftopic star
Beiträge: 8548
Erhaltene Danke: 477

Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
BeitragVerfasst: 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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: 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
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 328
Erhaltene Danke: 101



BeitragVerfasst: 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:
ausblenden 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.

Für diesen Beitrag haben gedankt: Anika, Martok
Horst_H
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 1654
Erhaltene Danke: 244

WIN10,PuppyLinux
FreePascal,Lazarus
BeitragVerfasst: 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
ausblenden 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.
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 Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Beiträge: 30
Erhaltene Danke: 2

Windows 7
Delphi 7
BeitragVerfasst: 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