Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!uunet!comp.vuw.ac.nz!cosc.canterbury.ac.nz!chisnall From: chisnall@cosc.canterbury.ac.nz (The Technicolour Throw-up) Newsgroups: comp.theory Subject: Re: Non recursive "Towers of Hanoi" Message-ID: Date: 27 Nov 90 20:59:13 GMT References: <1197@disuns2.epfl.ch> Reply-To: chisnall@cosc.canterbury.ac.nz Organization: Computer Science,University of Canterbury,New Zealand Lines: 24 From article <1197@disuns2.epfl.ch>, by diderich@disun17.epfl.ch (Claude Diderich): > I would like to know if anyone knows of an algorithm for solving the "Tower of > Hanoi" problem using the following constraints: > > 1. The algorithm is deterministic (no backtracking, etc...) > 2. The algorithm is iterative (no recursion) > 3. The algorithm uses at most O(1) extra storage in additon to the > storage required to modelize the three piles. > 4. The number of iterations can be determined a priori. It must be a > function of n, the number of disks. > 5. The algorithm may be non-polynomial. You can find such an algorithm in... "Towers of Hanoi and Analysis of Algorithms" by Paul Cull and E.F. Ecklund,Jr. American Math. Monthly 92 (1985), pp407-420 -- Name: M. D. Chisnall Address: chisnall@cosc.canterbury.ac.nz Fax: Just them, Ma'm, nothing else Quote: Are funky programming languages based on the lambada calculus?