0 Daumen
302 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

von

1 Antwort

+1 Punkt

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)\)

von 8,4 k

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...