Towers of Hanoi problems: deriving iterative solutions by program transformations

DOI10.1007/BF01934378MaRDI QIDQ1067772zbMATH OpenOpenAlexFDO

Authors Alberto Pettorossi

Publication date 1985

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934378

zbMATH Keywords

correctnessiterationprogram transformationrecursionrecursive solutionsTowers of Hanoi problems

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Specification and verification (program logics, model checking, etc.) (68Q60) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Review text

The author presents the derivation of the iterative solutions for the Towers of Hanoi problems starting from the recursive solutions. Various kinds of problems are considered: the standard one, the clockwise and the anticlockwise one, and the generalized one. The derived algorithms have optimal time x space performances. Their derivation implicitly gives the proof of their correctness.

Recommendations

• Pour en finir avec la dérécursivation du problème des tours de Hanoï
• An iterative optimal algorithm for the generalized tower of hanoi problem
• An iterative algorithm for the cyclic Towers of Hanoi problem
• Performance evaluations of recursive and iterative algorithms for the Towers of Hanoi Problem
• A generalization of the cyclic towers of hanoi: an iterative solution

Cites work

• A Transformation System for Developing Recursive Programs
• An iterative solution to the generalized Towers of Hanoi problem
• Characterization of flowchartable recursions
• Discussion and correspondence: A note on the Towers of Hanoi problem
• Iteration strikes back - at the cyclic Towers of Hanoi
• The cyclic towers of Hanoi
• The Generalized Towers of Hanoi Problem
• The Towers of Hanoi Problem

Cited in

(10)

• Performance evaluations of recursive and iterative algorithms for the Towers of Hanoi Problem
• Derivation of efficient programs for computing sequences of actions
• Modeling recursion with the aid of iterative algorithms
• A linear space algorithm for solving the Towers of Hanoi problem by using a virtual disc
• Shortest paths between regular states of the Tower of Hanoi
• An iterative algorithm for the cyclic Towers of Hanoi problem
• Computational solution of an old tower of Hanoi problem
• Pour en finir avec la dérécursivation du problème des tours de Hanoï
• scientific article; zbMATH DE number 3947600 (Why is no real title available?)
• scientific article; zbMATH DE number 7453187 (Why is no real title available?)

This page was built for publication: Towers of Hanoi problems: deriving iterative solutions by program transformations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1067772)