Rekursionsgleichung lösen. T(n):= 1, falls n=1,T(n):= T(n-2)+n, falls n>1

Question

Aufgabe:

T(n) =              1, falls n=1

           T(n-2)+n, falls n>1

(Nehmen Sie an , n sei ungerade)

Problem/Ansatz

Ich habe leider wenig Ahnung von Rekursionsgleichungen und weiß deshalb auch nicht wirklich wie ich mit der Lösung anfangen soll. Ich weiß, dass sie sich quasi selbst wieder aufruft.

Ich weiß schon mal das T(1) = 1 ist ( Rekursionsbasis), ich habe beim Rekursionsaufruf, also dem unteren Teil große Probleme.

Ich habe damit begonnen sie aufzustellen und einzusetzen:

T(n)=T(n-2)+n

T(1)=1

T(n-2)= T(n-4)+n+n

T(n-3) = T(n-5)+n+n+n

Ist der Ansatz richtig ? und kann mir jemand vielleicht den korrekten rechenweg sagen ? Von da an weiß ioch nicht weiter.

Comments

T(n) =              1, falls n=1

          T(n-2)+n, falls n>1

Sagt ihr hierzu wirklich:

"Rekursionsgleichung lösen?"

Wonach soll die Gleichung denn aufgelöst werden?
Tipp: Achte auf die Fachbegriffe und verwende sie so, wie du das gerade lernen sollst.

Answer 1

Berechne doch einfach mal die ersten Werte von \(T(n)\) für ungerade \(n\). Dann erhält man:$$\begin{array}{r|r}n& T(n)\\ \hline 1& 1\\ 3& 4\\ 5& 9\\ 7& 16\\ 9& 25\\ 11& 36\\ 13& 49\\ 15& 64\\ 17& 81\end{array}$$Die rechte Spalte sollte Dir bekannt vorkommen

[spoiler]

Das sind die Quadratzahlen! Bleibt nur noch zu klären, wie man von \(n\) zu \(\sqrt{T(n)}\) kommt. Schreibe die auch noch mal hin:$$\begin{array}{r|rr}n& T(n)& \sqrt{T(n)}\\ \hline 1& 1& 1\\ 3& 4& 2\\ 5& 9& 3\\ 7& 16& 4\\ 9& 25& 5\\ 11& 36& 6\\ 13& 49& 7\\ 15& 64& 8\\ 17& 81& 9\end{array}$$In der Spalte mit \(n\) werden die Zahlen immer um 2 erhöht. In der der Spalte mit \(\sqrt{T(n)}\) immer um 1. Da steckt schon mal der Faktor 2 drin. Mit ein wenig Nachdenken kann man dann darauf kommen, dass \(n+1\) genau das doppelte von \(\sqrt{T(n)}\) ist. Daraus folgt$$T(n) = \left( \frac {n+1}2\right)^2$$

[/spoiler]

Comments

Werner, vergleiche bitte deine explizite Lösung mit meiner.

---

Werner, vergleiche bitte deine explizite Lösung mit meiner.

war'n Copy&Paste Fehler; jetzt ist es wieder richtig

---

Sollte bei n=5 nicht 8 rauskommen? und bei 7 12?

---

Dein Anfang war falsch:

Ich habe damit begonnen sie aufzustellen und einzusetzen:
T(n-2)= T(n-4)+n+n
T(n-3) = T(n-5)+n+n+n

Es geht so:

n=3 dann: T(3)=T(3-2)+3=T(1)+3=1+3=4

n=5 dann: T(5)=T(5-2)+5=T(3)+5=4+5=9

---

Vielen Dank für die Hilfe ! :)

---

Sollte bei n=5 nicht 8 rauskommen? und bei 7 12?

Nein - nicht, wenn \(T(1)=1\) und \(T(n)=T(n-2)+n\) ist. Nochmal ausführlich: $$\begin{array}{r|r}n& T(n)\\ \hline 1& \colorbox{#ffff00}{1}\\ \colorbox{#ff88ff}{3}& \colorbox{#ffff00}{1}+\colorbox{#ff88ff}{3} = \colorbox{#88ffff}{4}\\ \colorbox{#88ff88}{5}& \colorbox{#88ff88}{5}+\colorbox{#88ffff}{4}=9\\ 7& 9+7=16\\ 9& \text{usw.} \space 25\\ 11& 36\\ 13& 49\\ 15& 64\\ 17& 81\end{array}$$

---

Vielen Dank ich denke ich habe es nun verstanden :)

Ich hätte da noch eine andere Frage zur Aufgabe:

Wäre die asymptotische notation Groß O so richtig:

T(n) ∈ Θ(n^2) ?

---

Wäre die asymptotische notation Groß O so richtig:
T(n) ∈ Θ(n2) ?

Nein, wenn man die Rekursionsformel benutzt, dann wächst die Laufzeit um ein \(T(n)\)  zu berechnen genauso schnell wie \(n\), da mit jedem Inkrement von \(n\) um 2 genau eine Addition mehr ausgeführt werden muss . Also ist$$T(n) \in \Theta(n)$$benutzt man die Gleichung $$T(n) = \left( \frac {n+1}2\right)^2$$ so ist \(T(n)= O(1)\). Wobei ich bei der genauen Syntax nicht sicher bin.

Wichtig ist, im Falle der Rekursion wächst die Laufzeit mit \(n\) (nicht mit \(n^2\)) und bei Verwendung der geschlossenen Gleichung ist sie konstant.

---

ich habe noch eine frage gepostet, Sie wurde aber auf Stacklounge verschoben..

Leider konnte mir bisher keiner Helfen. https://www.stacklounge.de/4941/vom-algorithmus-zur-rekursionsgleichung?show=4945#c4945

Ich hoffe das einer von Ihnen zeit findet um mir zu helfen.

Vielen Dank.

Nikola Kurzac

---

Hallo Nikola,

ich glaube nicht, dass ich Dir da wirklich helfen kann. Dafür fehlt mir das Know How in theoretischer Informatik. Sorry ...

---

Kein Problem :)

WEißt du denn vielleicht ob mein Gedankengang bei einsetzen von n in den algortihmus so richtig ist'?

n =1

REKLAG Alg. beendet

n=2

LINALG(2)

 then 2*2/3 = Abgerundet 1

dann springt der algortihums wieder zur ersten schleife REKALG wo der algortihmus dann wieder beendet wird oder bleibt man in der schleife und LINALG (2) wird mit n=1 geprüft und dann folgt die else 1/3 aufgerundet zu 1 und das dann endlos ?

---

ich habe Dir unter Deiner Frage geantwortet

Answer 2

T(n) mit n ungerade liefert die Folge der Quadratzahlen. T(2m-1)=m² oder T(k)=\( (\frac{k+1}{2})^{2} \)