...Binomialkoeffizienten schnell berechnnen

hitstec · Beiträge: 295

Der folgende Algorithmus berechnet den Binomialkoeffizienten "n über k".
Diese Lösung entstand aus dem Umstand, dass beispielsweise schon "1000 über 10" mit gewöhnlichen Zahlen auf dem Computer nicht darstellbar ist. Selbst mächtige Mathematikprogramme - an dieser Stelle möchte ich keine Namen nennen - beherrschen die Berechnung von "n über k" nur mangelhaft bis gar nicht.
Ziel war es einen schnellen Algorithmus, sowie eine Datenstruktur, die mit riesigen Zahlen umgehen kann, zu entwerfen.

Hinweis: Zwar ist die Berechnung des Binomialkoeffizienten mit diesem Algorithmus sehr gut möglich, nur ist die Weiterverwendung der berechneten Zahlen mit dem Umstand verbunden, dass sie oft zu groß sind, um sie in gewöhnliche Integer zu konvertieren.
Um mit den berechneten Zahlen weiterarbeiten zu können, müsste man auf die verwendete Datenstruktur zurückgreifen. Eine Addition und Multiplikation ist schon Bestandteil der Datenstruktur, sodass es sicherlich nicht schwer sein wird, weitere notwendige Methoden zur Behandlung der Zahlen zu entwerfen.

Falls also jemand Verbesserungsvorschläge hat oder Probleme identifizieren konnte, so möge er sich mit mir in Verbindung setzen.

RECHTLICHES:
Sie können diese Implementierung für Ihren persönlichen Zweck nach belieben erweitern und verändern. Haben Sie den Wunsch Ihre Modifikation dieser Liste zu veröffentlichen, so müssen Sie sicherstellen, dass Sie den Hinweis "Copyright (c) 2004 Alexander Schimpf" sowie die oben genannte Homepage- und Emailadresse im Kopf der Unit sichtbar unterbringen.
Haben Sie vor, diese Implementierung oder eine Modifikation davon in einer öffentlich zugänglichen Software zu verwenden, so teilen Sie mir das bitte umgehend mit.

Vielen Dank!

---

So, hier ist der Code. Zu dieser Unit gehören eigentlich noch zwei weitere Units. MyBigInt und Funct. Diese befinden sich im Dateianhang.
Sicherlich kann man auch seine eigenen Funktionen für die Berechnung des ggT sowie für die Behandlung großer Zahlen programmieren.
Die Idee ist fast schon simpel: kürze solange du kannst und multipliziere den Rest auf!

markieren

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:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:

{******************************************************************************}
{                                                                              }
{                 CalcBinomKoeff - Version 1.0 (2005-01-17)                    }
{                                                                              }
{                   Copyright (c) 2005 Alexander Schimpf                       }
{                                                                              }
{                              www.hitstec.de                                  }
{                             info@hitstec.de                                  }
{                                                                              }
{******************************************************************************}
unit CalcBinomKoeff;

interface

uses Sysutils, Funct, MyBigInt;

function CalculateBinomKoeff(n,k: Integer): String;

implementation

function CalculateBinomKoeff(n,k: Integer): String;
const zaehler=0; nenner=1; pos=0;
var m,i,j,iGgT: Integer; arBruch: Array [0..1] of Array of Integer;
    mbResult: TMyBigInt;
begin
 // "n-k" soll kleiner als "k" sein, gilt wegen Symmetrie des BinomKoeff. im Nenner
 if (n-k)>k then k:=n-k;
 m:=n-k;

 // Initialisierung der Variablen
 for i:=Low(arBruch) to High(arBruch) do SetLength(arBruch[i],m+1);
 // Setzen der gebliebenen Faktoren, "nur" n-k Faktoren sind wichtig
 for i:=1 to m do begin
  arBruch[zaehler][i]:=i+k;
  arBruch[nenner][i]:=i;
 end;

 arBruch[zaehler][pos]:=1; // max{m+1: arBruch[zaehler][i]=1 für alle i=1...m}
 arBruch[nenner][pos]:=2; // max{m+1: arBruch[nenner][i]=1 für alle i=1...m}
 while arBruch[nenner][pos]<=m do begin
  for i:=m downto arBruch[nenner][pos] do begin
   for j:=m downto arBruch[zaehler][pos] do begin
    // Bestimmung des ggTs
    iGgT:=ggT(arBruch[nenner][i],arBruch[zaehler][j]);
    if iGgT>1 then begin
     // Kürzen
     arBruch[zaehler][j]:=Round(arBruch[zaehler][j]/iGgT);
     arBruch[nenner][i]:=Round(arBruch[nenner][i]/iGgT);
     if arBruch[nenner][i]=1 then break;
    end;
   end;
   // Verschieben der Position im Zaehler
   for j:=arBruch[zaehler][pos] to m do
    if arBruch[zaehler][j]=1 then arBruch[zaehler][pos]:=j+1
    else break;
  end;
  // Verschieben der Position im Nenner
  for i:=arBruch[nenner][pos] to m do
   if arBruch[nenner][i]=1 then arBruch[nenner][pos]:=i+1
   else break;
 end;

 mbResult:=TMyBigInt.Create(1);
 try
  // Faktoren im Zaehler aufmultiplizieren
  for i:=arBruch[zaehler][pos] to m do mbResult.Multiply(mbResult,arBruch[zaehler][i]);
  Result:=mbResult.ToString;
 finally FreeAndNil(mbResult);
 end;
end;

end.

Moderiert von jasocul: Link gelöscht und Units als Dateianhang angefügt

(Schnelle) Berechnung des Binomialkoeffizienten.zip (3.65 KB)		Download (Rev 0) (728x, 728x gesamt)
Beschreibung:	Die notwendigen Units zur Berechnung

inselberg · Beiträge: 458

Zitat:

Selbst mächtige Mathematikprogramme - an dieser Stelle möchte ich keine Namen nennen - beherrschen die Berechnung von "n über k" nur mangelhaft bis gar nicht.

das meinst du doch nicht ernst ... muss ich wirklich maple starten

_________________
hans bist du das ?

hitstec · Beiträge: 295

Der Windows-Taschenrechner ist doch ein mächtiges Mathematik-Programm - finde ich. :wink:

Maple und Derive können das natürlich mit links - sind aber nicht umsonst.

Aber MathCad kann es soweit ich weiß nicht. Und MathCad kann man schon als mächtiges Mathematik-Programm bezeichnen. Nun, jetzt habe ich doch Namen genannt. :oops:

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme