0 Daumen
2,7k Aufrufe

Hey Leute,

ich und meine Übungspartner sind total Ratlos. Es geht um folgende Frage:

In der Voerlesung wurde der Rechenaufwand für die rekursive Berechnung der Fibonaccizahlen ermittelt. Versuchen Sie nun einen Ausdruck An,k zur Beschreibung der Komplexität der rekursiven Berechnung des Binomialkoeffizienten zu finden.

Formel zur Berechnung des Binomialkoeffizienten.
Bn,k = (n über k) = n! / (k!(n-k)!)
Weiterhin gilt Bn,0 = Bn,n = 1 für n größer gleich 0
Sowie Bn,k = Bn-1,k-1 + Bn-1,k für 0 < k < n

Morgen ist bereits schon die Abgabe, daher wäre eine Lösung super, damit man das Ganze wenigstens nachvollziehen kann.

Viele Grüße

Avatar von

1 Antwort

+1 Daumen

Ich hoffe, dass Du die Abgabe noch erfolgreich fertigstellen konntest! Die folgende (Java) Funktion berechnet den Binomialkoeffizient rekursiv:

 public static int binom(final int n, final int k) {
if (n == k || k == 0) {
return 1;
}
return binom(n - 1, k) + binom(n - 1, k - 1);
}

Es ist 

\(B_{n,k}=\begin{cases}1,&n=k\vee k=0\\B_{n-1,k-1}+B_{n-1,k}, \mathrm{sonst}\end{cases}\)

die rekursive Definition des Binomialkoeffizienten. Die dazugehörige Rekurrenzgleichung lautet:

\(T(n,k) = T(n-1,k) + T(n-1,k-1) + \mathcal{O}(1) \) mit \(T(n,n) = T(n,0) = \mathcal{O}(1)\)

Daraus folgt:

\(T(n) = \mathcal{O}(2^n)\)

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community