Contents Menu

An algorithm for tower of hanoi with four or more poles

Technology reports of the Yamaguchi University Volume 2 Issue 2 Page 173-180
published_at 1978-12
KJ00004350984.pdf
[fulltext] 305 KB
Title
An algorithm for tower of hanoi with four or more poles
Creators Takanami Itsuo
Creators Inoue Katsushi
Source Identifiers
For the case of four or more poles, we propose a recursive procedure not using the dynamic programmming technique. Then in a certain proposed algorithm we derive an explicit expression for the number of moves of disks as a function of N disks and m poles. In this algorithm the number of moves decreases monotoneously in terms of m but its limiting value is 3^<「log_2N」> although 2N+1 is the minimum number of moves for m≧N+1. So we give a modified algorithm and its associated recurrence equation for the number of moves. This equation is solved numerically since it is difficult to derive the explicit expression for its solution. This result shows that the modified algorithm is near optimal.
Subjects
工学 ( Other)
Languages eng
Resource Type departmental bulletin paper
Publishers 山口大学工学部
Date Issued 1978-12
File Version Version of Record
Access Rights open access
Relations
[ISSN]0386-3433
[NCID]AA0086073X
Schools 工学部