0 Daumen
947 Aufrufe

Hey ich habe im Fach Algorithmen folgende Rekursionsaufgabe zu lösen, komme dabei jedoch nicht auf das Richtige Ergebniss. Kann mir jemand zeigen, wie das geht? Vielen Dank im Voraus!

Aufgabe:

Betrachte folgende Rekursiongleichung. Ist n eine Dreierpotenz, so ist

T(n) = 2 T(n/3) + 5n

T(1) =  5

Geben Sie eine geschlossene Form für T(n) an und benutzen Sie dabei nicht das Mastertheorem. Beweisen Sie die Korrektheit ihrer Antwort.

Avatar von

Betrachte folgende Rekursiongleichung. Ist n eine Dreierpotenz, so ist

T(n) = 2 T(n/3) + 5n

T(1) =  5

Ist n eine Dreierpotenz, so ist

D.h. n = 3^k 

n/3 = 3^{k-1}

Nun hast du T_(1) = T_(3^0) = 5

T_(3^1) = 2* T(3^0) + 5*3^1 = 2 * 5 + 15 = 25

T_(9) = T_(3^2) = 2 * T_(3^1) + 5* 3^2 = 50 + 45 = 95

T_(27) = T_(3^3) = 2 * T_(3^2) + 5* 3^3 = 190 + 5 * 27 = ...

usw. 

Könnte der Anfang der Rekursion so gemeint sein? 

Wenn nicht, wie lautet deine Rechnung für die ersten Paar T-Werte? 

ähnliche Frage hier: https://www.mathelounge.de/444608/zeige-dass-rekurrenz-t-n-in-der-o-notation-enthalten-ist-t-0-a-t

Ist es sinnvoll, dass die Frage von morrohype in die Stacklounge verschoben / in der Stacklounge gestellt wurde?

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community