Fibonacci Zahlen Anzahl der Additionen

27.04.2013, 10:24	Matze9999	Auf diesen Beitrag antworten »
Fibonacci Zahlen Anzahl der Additionen Hallo, im Anhang befindet sich ein rekursiver Algorithmus der die n-te Fibonacci Zahl berechnet. Mein Problem ist, dass ich herausfinden soll, wie viele Additionen hierfür benötigt werden. Die Lösung für dieses Problem habe ich auch in den Anhang gepackt. Allerdings verstehe ich nicht, wie man von $\begin{eqnarray} n>1: A(n) = A(n-1)+A(n-2)+1 \end{eqnarray}$ auf $\begin{eqnarray} n>1: A(n) \leq 2A(n-1)+1 \end{eqnarray}$ kommt ist dieser Schritt lediglich eine Abschätzung, dass $\begin{eqnarray} A(n-1)\leq A(n-2) \end{eqnarray}$ ist oder wieso kann man aus A(n-2) ein weiteres A(n-1) machen?) Wieso folgt daraus dann $\begin{eqnarray} A(n) \leq 2^{n}-1 \end{eqnarray}$ dieses hier? Wäre schön, wenn mir das mal jemand erklären könnte. Vielen Dank.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »