Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Vom Algorithmus zur Rekursionsgleichung (http://www.informatikerboard.de/board/thread.php?threadid=4232)
Geschrieben von Miakosa am 18.10.2019 um 12:25:
Vom Algorithmus zur Rekursionsgleichung
Meine Frage:
Aufgabe:
Eingabe = n ? N (Natürliche Zahlen)
Ausgabe = keine
Algorithmus LINALG nicht rekursiv,liefert einen Wert vom Typ boolean und hat eine lineare Zeitkopmplexität
REKALG(n)
1 if n=1
2 then return
3 if LINALG(n)
4 then REKALG (?2n/3?)
5 else REKLAG(?n/3?)
a) Stellen Sie die Rekursionsgleichung zur Bestimmung der maximaleen Anzahl der rekursiven Auftrufe dieses Algorithmus mit dem Argument n auf. Zählen Sie die Auswertung der Anfangsbedinung auch als einen rekursiven Aufruf. ( Auf und Abrunden in der rekursionsgleichung vernachlässigen)
b) Lösen Sie die Rekursionsgleichung mit dem Master Theorems.
Meine Ideen:
mein Lösungsweg für a:
Ich habe erstmal für n ein paar werte eingesetzt:
n=1
Alg. beendet
n=2
LINALG (n)
then = 1
Alg. beendet
n=3
LINALG(3)
=2
Da n=2 und LINALG (3)
else = 1
Alg. beendet.
Ich bin mir nur jetzt unsicher ob ich den algorithmus so richtig verstanden habe und wie genau ich dadurch jetzt zur rekursionsgleichung komme.
Forensoftware: Burning Board, entwickelt von WoltLab GmbH