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!
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:
|
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 if (n-k)>k then k:=n-k; m:=n-k;
for i:=Low(arBruch) to High(arBruch) do SetLength(arBruch[i],m+1); for i:=1 to m do begin arBruch[zaehler][i]:=i+k; arBruch[nenner][i]:=i; end;
arBruch[zaehler][pos]:=1; arBruch[nenner][pos]:=2; 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 iGgT:=ggT(arBruch[nenner][i],arBruch[zaehler][j]); if iGgT>1 then begin 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; for j:=arBruch[zaehler][pos] to m do if arBruch[zaehler][j]=1 then arBruch[zaehler][pos]:=j+1 else break; end; 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 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