Türme von Hanoi

Aufrufe: 521     Aktiv: 24.11.2020 um 16:10

0

Hallo ich habe ein Problem mit der Folgenden Aufgabe ich soll die Korrektheit des folgenden rekusiv definierten Algorithmus zeigen zum lösen der Türme von Hanoi alle scheiben sollen am ende auf stab C liegen ich weiß das man dies am besten mit Induktion zeigen kann jedoch habe ich keine Ahnung wie Induktion bei einem Algorithmus aussieht kann mir jemand dabei helfen denn beweis für die korrektheit hinzubekommen?

 

Eingabe :Anzahlnder zu verschiebenden Scheiben
1MOVE(n,A,B,C)
2FunctionMOVE(i, StabA, StabB, StabC):
3   if i >0then
4       MOVE(i−1,A,C,B)
5       Verschiebe oberste Scheibe von A nach C
6       MOVE(i−1,B,A,C)
7   end
8end

Diese Frage melden
gefragt

Punkte: 16

 
Kommentar schreiben
1 Antwort
0

Du solltest dir zuerst überlegen, ob der Algorithmus für \(n=0\) (1 Scheibe) korrekt funktioniert. Das ist der Induktionsanfang.

Nimm dann an, dass der Algorithmus für \(n\) Scheiben korrekt funktioniert (Induktionsvoraussetzung). Nun musst du zeigen, dass dies auch für \(n+1\) Scheiben gilt (Induktionsschritt).  Dazu verwendest du in Zeilen 4 und Zeile 6 die Induktionsvoraussetzung, da ja hier jeweils \(n+1-1=n\) Scheiben bewegt werden. Du weißt also, dass der Algorithmus damit beginnt, \(\mathtt{MOVE(n,A,C,B)}\) aufzurufen. Nach Induktionsvoraussetzung funktioniert das korrekt, d.h. \(n\) Scheiben werden von \(A\) über \(C\) nach \(B\) verschoben. Was bewirken die restlichen Schritte? Kommt dann das richtige Ergebnis heraus?

Diese Antwort melden
geantwortet

Punkte: 11.27K

 

Kommentar schreiben