Algorithmensammlung: Kombinatorik: Binomialkoeffizient
Algorithmensammlung: Kombinatorik
Fakultät
[Bearbeiten]Der Artikel beschreibt die für die Kombinatorik wichtige Fakultätsfunktion. Direkt verwendet wird sie, um die Anzahl der Möglichkeiten zu berechnen, alle n Kugeln aus einer Urne ohne Zurücklegen unter Beachtung der Reihenfolge anzuordnen. Ferner spielt sie u. a. bei der Definition des Binomialkoeffizienten eine wichtige Rolle.
Basic C64
[Bearbeiten]F! = 1*2*3*4*5* ......*F
Die Fakultät einer natürlichen Zahl wird berechnet.
10 INPUT F
12 S = 1
20 FOR N = 1 TO F
30 S = S*N
50 NEXT
60 PRINT "die Fakultaet von ";F;" = ";S
Die ganze Reihe aller Fakultäten von 1 bis 100 wird berechnet.
F = 1
For k = 1 To 100
F = F * k
Print "Die Fakultät von "; k; " = ", F
Next k
Java
[Bearbeiten]Die folgende Java-Methode zur Berechnung der Fakultät verwendet die Klasse BigInteger, die sich mit der Zeile
import java.math.BigInteger;
am Anfang des Programms einbinden lässt.
public static BigInteger factorial (int n) {
if (n < 0) {
System.out.println("Argument negativ!");
return null;
}
BigInteger f = BigInteger.ONE;
for (int i=2; i<=n; i++)
f = f.multiply(BigInteger.valueOf(i));
return f;
}
Python
[Bearbeiten]Die Funktion bekommt eine Ganzzahl größer 0 als Parameter übergeben und gibt den Wert der Fakultätsfunktion zurück.
# Getestet unter Python 3.4, sollte aber unter allen 3.x-Versionen laufen
def fakultaet(n):
f = 1
for i in range(1, n + 1):
f = f * i
return f
Ab Python2.6 gibt es dafür die Funktion math.factorial.
Für sehr große n kann die Fakultät näherungsweise mit der Stirling-Formel berechnet werden.
FreePascal
[Bearbeiten]Der Vollständigkeit halber sei die rekursive Implementation gezeigt:
{**
recursively calculates factorial of given n
\param n the factorial to calculate of
\returns factorial of n
*}
function factorial(const n: longword): qword;
begin
// optimization: then-branch is executed most of the time
if n > 1 then
begin
factorial := factorial(n - 1) * n;
end
else
begin
factorial := 1;
end;
end;
Interessanter ist die iterative Implementation. Hier eine, die sowohl x86-64-assembler und Pascal kombiniert:
{**
iteratively calculates factorial of n
\param n the upper limit
\return the factorial of n,
unless the result is out of range of the function's domain
}
function factorial(const n: longint): qword;
{$ifdef CPUx86_64}
assembler;
{$goto on}
label
factorial_iterate, factorial_done;
{$asmMode intel}
asm
// ecx is used by loop instruction as counter variable
mov ecx, n // ecx := n
// rax is where we calculate our product
mov rax, 1 // rax := 1
test rcx, rcx // commonBits := rcx
// don't enter loop, since ecx = 0 it loops over all integers
jz factorial_done // if commonBits = 0 then goto done
// load r13 with failure value, bc cmov can't process immediates
xor r13, r13 // r13 := 0
factorial_iterate:
mul rcx // rdx:rax := rax * rcx
test rdx, rdx // commonBits := rdx and rdx
// commonBits only has a positive magnitude if rdx is non-zero
// continue looping while rdx remains zero
loopz factorial_iterate // dec(ecx)
// if ecx <> 0 and ZF = 0 then goto iterate
// void result, if we need the "high" register
cmovnz rax, r13 // if not ZF then rax := 0
factorial_done:
// the @result macro represents the function's return value
mov @result, rax // result := rax
end;
{$else}
var
/// temporary iterator variable
i: longint;
/// space to calculate the product in
product: qword;
begin
product := 1;
// note: for-loop limits are in Pascal inclusive
// limit two, because multiplying by one is neutral
for i := n downto 2 do
begin
product := product * n;
end;
factorial := product;
end;
{$endif}
Binomialkoeffizient (Kombination ohne Zurücklegen)
[Bearbeiten]Der Artikel beschreibt die Algorithmen zu den Artikeln Binomialkoeffizient und Abzählende Kombinatorik.
Der folgende Algorithmus berechnet den Binomialkoeffizienten, der in der abzählenden Kombinatorik die Anzahl verschiedener Ergebnisse berechnet, wenn in einer Ziehung die gezogenen Elemente nicht zurückgelegt wurden, aber die Reihenfolge bei der Ziehung keine Bedeutung hat. Dies liefert beispielsweise beim Lotto 6 aus 49 die Anzahl der verschiedenen Möglichkeiten, ein Zahlenfeld auf dem Tippschein auszufüllen.
Pseudocode
[Bearbeiten]n und k seien natürliche Zahlen oder gleich 0. Außerdem gelte 0 ≤ k ≤ n.
function binomialkoeffizient (n, k)
if k > n - k then k ← n - k
b ← 1
for i ← 1 to k do
b ← b * (n + 1 - i) / i
return b
Java
[Bearbeiten]Wie bei der Fakultät muss am Anfang des Programms mit
import java.math.BigInteger;
die Klasse BigInteger eingebunden werden.
public static BigInteger binomialCoefficient (int n, int k) {
if (n < 0 || k < 0) {
System.out.println("Argument negativ!");
return null;
}
if (k > n) return BigInteger.ZERO;
k = Math.min(k,n-k);
BigInteger bc = BigInteger.ONE;
for (int i=1; i<=k; i++) {
bc = bc.multiply(BigInteger.valueOf(n+1-i));
bc = bc.divide(BigInteger.valueOf(i));
}
return bc;
}
Python
[Bearbeiten]Im folgenden Quelltext wurde die normalerweise im Mathematikunterricht vermittelte Definition des Binomialkoeffizienten unter Verwendung der Implementierung der Fakultät von oben implementiert. Die Parameter müssen ganzzahlig sein.
# Getestet unter Python 3.4, sollte aber unter allen 3.x-Versionen laufen
def binomialkoeffizient(n, k):
return fakultaet(n) // (fakultaet(k)*fakultaet(n-k)) # integer-Division, da Binominalkoeffizienten bekanntlich ganze Zahlen sind
Der folgende Algorithmus ist um einiges effizienter.
# Getestet unter Python 3.4, sollte aber unter allen 3.x-Versionen laufen
def binomialkoeffizient(n, k):
if k == 0: return 1
if 2*k > n:
ergebnis = binomialkoeffizient(n, n-k)
else:
ergebnis = n-k+1
for i in range(2, k+1): # 2 <= i <= k
ergebnis *= (n-k+i) # Selbstmultiplikation
ergebnis //= i
return ergebnis
# (ergebnis * (n-k+i)) / i ist bei jedem Schritt ganzzahlig,
# daher kann Integer-Division verwendet werden;
# die Größe von int ist in Python nur durch den Speicherplatz begrenzt.
Visual Basic for Applications
[Bearbeiten]Der Algorithmus hat folgende Merkmale:
- Im Laufe der Berechnung wird kein Zwischenergebnis größer als das Endergebnis, so dass ein Überlauf nur dann eintritt, wenn auch das Endergebnis einen Überlauf auslösen würde
- Divisionen werden meist so ausgeführt, dass das Ergebnis ganzzahlig bleibt.
Grundsätzlich lässt sich der Bereich der Ergebnisse mit voller Genauigkeit erweitern, wenn als Rückgabewert der Funktion der VBA-Datentyp Currency (größter ganzzahlig darstellbarer Wert 922.337.203.685.477) statt Long (größter ganzzahlig darstellbarer Wert 2.147.483.647) verwendet wird. Speziell bei der Verwendung als Excel-Tabellenfunktion muss dann das Zahlenformat manuell vorgegeben werden, da sonst automatisch die Zelle das Zahlenformat Währung erhält. Die Datentypen der Argumente n und k können nicht geändert werden, da die Mod-Funktion mit Argumenten vom Datentyp Long (oder kleiner) arbeitet.
Public Function BinomialKoeffizient(n As Long, ByVal k As Long) As Long
Dim i As Long, s As Long
' Vergrößerung der Geschwindigkeit
If n < k + k Then k = n - k
' Startwerte setzen
s = n - k + 1
BinomialKoeffizient = 1
For i = 1 To k
If s Mod i = 0 Then ' Teilbarkeit prüfen
BinomialKoeffizient = BinomialKoeffizient * (s / i)
Else
BinomialKoeffizient = (BinomialKoeffizient / i) * s
End If
s = s + 1
Next
End Function
Wenn n und k Dezimalzahlen sind, werden sie bei der Übergabe an die Funktion auf ganzzahlige Werte gerundet (impliziter typecast durch VBA), dabei wird nach IEEE-754 ( mathematische Rundung) gerundet. Dadurch führt beispielsweise die Übergabe von k = 0,5 zur Abrundung auf k = 0.
Die Funktion enthält keine Fehlerbehandlung, da die erforderlichen Programmzeilen und Rückgabewerte programmspezifisch für Excel, Access und andere Office-Programme anzupassen wären. Verwendung als Funktion in Visual Basic:
- Ergebnis = BinomialKoeffizient(49, 6)
Anwendung als Excel-Tabellenfunktion:
- =BinomialKoeffizient(49;6)
Das Ergebnis ist in beiden Fällen 13 983 816; Excel bietet auch die Tabellenfunktion Kombinationen() an, die gelegentlich ungenaue Ergebnisse liefert, beispielsweise ein Rundungsartefakt für =BinomialKoeffizient(40;17)
Tipps
[Bearbeiten]Bitte ausbauen
Mit Python 3.4 wurde erstmals ein Statistik-Modul, statistics, ausgeliefert, das gängige statistische Methoden wie Mittelwert- und Streumaßberechnung anbietet.