A linear space algorithm for solving the Towers of Hanoi problem by using a virtual disc (Q1116691)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear space algorithm for solving the Towers of Hanoi problem by using a virtual disc |
scientific article |
Statements
A linear space algorithm for solving the Towers of Hanoi problem by using a virtual disc (English)
0 references
1989
0 references
A space efficient algorithm for solving the Towers of Hanoi problem is presented in this paper. The algorithm utilizes the concept of virtual disc, which is an artificial disc smaller than the smallest real disc. The purpose of introduing such a virtual disc is to enforce a unique disc move at each step. As peg information is not represented, the space complexity of the algorithm is reduced to \(\sim n\) bits, where n is the number of discs in the tower.
0 references
iterative algorithm
0 references
Towers of Hanoi
0 references
space complexity
0 references
0 references
0 references