ISSN:
1436-5057
Keywords:
05A99
;
68Q20
;
Tower of Hanoi
;
The Reve's Puzzle
;
algorithm
;
iteration
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Der Turm von Hanoi (TH) mitm+3 Stangen undn Scheiben ist ein hundert Jahre altes mathematisches Spiel, das augenblicklich eine bemerkenswerte Wiederbelebung in der Informatik erfährt, wo es z. B. im Zusammenhang mit Produktionsplänen und Materialverwaltung diskutiert worden ist. Er wird üblicherweise durch doppelte Rekursion überm undn gelöst. In dieser Arbeit wird eine Lösung gleicher Länge vorgestellt, die rekursiv inm, aber iterativ inn ist und so zu einem rein iterativen Algorithmus für den Vier-Stangen-TH führt, aufbauend auf den wohlbekannten iterativen Lösungen des klassischen Drei-Stangen-TH. Diese Algorithmen hatten sich in Untersuchungen über Komplexitätsabschätzungen als viel leistungsfähiger erwiesen als die rekursiven und könnten von Interesse bei problemen des Sortierens angeordneter Befehle in Parallelrechnern sein. Einige mathematische Hilfsmittel werden hergeleitet oder aus der Literatur zitiert, um die Korrektheit des Algorithmus beweisen zu können.
Notes:
Abstract The Tower of Hanoi (TH) withm+3 pegs andn discs is a one hundred years old mathematical puzzle which is now experiencing a remarkable revival in computer science, where it has been discussed e.g. in connection with production scheduling and material handling. It is usually solved by double recursion onm andn. In this paper, a solution with the same length is provided which is recursive inm, but iterative inn, thus leading to a purely iterative algorithm for the four pegs TH, based on the well-known iterative solutions of the classical three pegs TH. These algorithms had turned out to be much more efficient than the recursive ones in studies of performance evaluations and might be of some interest in problems of sorting ordered instructions in a parallel computer. Some mathematical tools are derived or cited from literature in order to prove correctness of the algorithm.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02239743
Permalink
