Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Probeklausur - A1
/EDIT: Ich hab die Zeitanalyse verändert. 10.10.2012 12:01/
Erst einmal schnell meine Programmidee, auch wenn mir später dann die Zeit Probleme bereitet:
Vorraussetzungen: Das niederwertigste Bit der Binärkodierung auf Band i stehe am linken Ende der Zahl. Die Binärkodierung wird links und rechts von mindestens einem Blank begrenzt. Die Kopfposition auf Band i sei zu Beginn links vom niederwertigsten Bit.
left_ik:
BEGIN: right_i;
if_i B goto END;
if_i 0 goto DEKREMENT;
(*falls 1*) write_i 0;
left_k;
GO_LEFT: left_i;
if_i B goto BEGIN else GO_LEFT;
DEKREMENT: write_i 1;
goto BEGIN;
END: Soweit, so gut. Jetzt stellt sich mir nur noch die Frage nach der Laufzeit, bei der ich mir nicht sicher bin. Meine Grundgedanken sind:
Eine Zahl n wird durch log_2(n) (aufgerundet) Ziffern binär kodiert. Für das Dekrementieren gilt: Wir gehen jeden ersten Schritt ein Bit weit, jeden zweiten Schritt einen weiteren, alle 4 Dekrementierungen noch einen zusätzlich… Das lässt sich beschreiben als 1 + 1/2 + 1/4 + 1/8 … was nach allen Kenntnissen der Mathematik 2 wird, wenn man die Summe ins unendliche Fortsetzt. Um die Zahl n in einser-Schritten gegen 0 zu dekrementieren, brauchen wir n Schritte. O(2*n) = O(n).
Was denkt ihr dazu?
Sieht auf den ersten Blick gut aus.
Die Reihe die du beschrieben hast steht auf dem Uebungsblatt 9 und stellt die Laufzeit des decrease-Makros dar.