Das Open-Control-Projekt - Die Alternative zur C-Control-I


Das Forum zur C-Control-1
Welche C-Control-Varianten existieren?
Übersicht - Suchen - Neueste 50 Beiträge - Neuer Beitrag - Login - Registrieren
INFO - FAQ - CC2-Forum - CCPro-Forum 

 Turm von Hanoi Kategorie: Open-Micro/Open-Mini/Open-Midi/Open-Macro/Open-Maxi (von Dietmar, Homepage - 29.01.2022 11:17)
Dietmar nutzt:  Open-Micro, Open-Mini, Open-Midi, Open-Macro, Open-Maxi, Open-Mini Station
Hallo zusammen,

in den letzten Tagen habe ich vier Sourcecodes zum Softwareproblem "Turm von Hanoi" auf der Open-Maxi implementiert. Dieser Algorithmus wird häufig als Benchmarktest verwendet.

Das Spiel "Turm von Hanoi" besteht aus drei gleich großen Stäben A, B und C, auf die mehrere gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf Stab A, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel von A nach C (oder A nach B) zu versetzen. Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes unter der Voraussetzung, daß sich dort nicht schon eine kleinere Scheibe befindet, auf einen der beiden anderen Stäbe gelegt werden. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Stapel der Größe nach geordnet.

Um das Spiel zu lösen, gibt es rekursive und iterative Algorithmen. Es werden 2^n-1 Züge, bzw. Verschiebungen benötigt, um alle Scheiben von einem Stab auf einen anderen zu transferieren. Ich habe auf der Open-Maxi ein Programm mit iterativem und drei Programme mit rekursivem Algorithmus umgesetzt und deren Geschwindigkeit ermittelt. Es wurden der OCBASIC- und der OCBASR32-Compiler verwendet.

Hier die Tabelle mit allen Meßergebnissen:

Programminterpretiertmit OCBASR32 kompiliert
Iterativer Algorithmus2925 Verschiebungen/s6825 Verschiebungen/s
Rekursiver Algorithmus3863 Verschiebungen/s8902 Verschiebungen/s
Rekursiv mit etwas Assembler7313 Verschiebungen/s18614 Verschiebungen/s
Rekursiv in Assembler234050 Verschiebungen/s---

Und hier ein Bild vom Terminalprogramm:



In den Folgebeiträgen sind die vier Sourcecodes zu finden.

Viel Spaß und Erfolg mit den OM-Mikrocontrollern!

Dietmar

Passender Link: Offizielle Infosite zu den OM-Mikrocontrollern

Meine Homepage: http://ccintern.dharlos.de

 Antwort schreiben

Bisherige Antworten:

Demoprogramm: Turm von Hanoi - Rekursiver Algorithmus in Assembler (von Dietmar - 29.01.2022 11:27)
Demoprogramm: Turm von Hanoi - Rekursiver Algorithmus mit etwas Assembler (von Dietmar - 29.01.2022 11:25)
Demoprogramm: Turm von Hanoi - Rekursiver Algorithmus (von Dietmar - 29.01.2022 11:23)
Demoprogramm: Turm von Hanoi - Iterativer Algorithmus (von Dietmar - 29.01.2022 11:20)