Post Reply 
Weakest calculator/pocket computer that can do Tower of Hanoi?
08-12-2018, 07:16 AM (This post was last modified: 08-12-2018 01:19 PM by Thomas Klemm.)
Post: #7
RE: Weakest calculator/pocket computer that can do Tower of Hanoi?
This program for the HP-11C implements A001511:
Code:
01▸LBL A
02 1
03▸LBL 0
04 x<>y
05 2
06 ÷
07 FRAC
08 x≠0
09 GTO 1
10 R↓
11 LSTx
12 x<>y
13 1
14 +
15 GTO 0
16▸LBL 1
17 R↓
18 RTN

Quote:a(n) = number of disk to be moved at n-th step of optimal solution to Towers of Hanoi problem

It uses the following method to calculate \(a(n)\):
Quote:a(n) is the number of digits that must be counted from right to left to reach the first 1 in the binary representation of n.

Example with 3 disks

Hint: Move odd disks to the right and even disks to the left.

1 [A] → 1 ; move disk 1 to the right
2 [A] → 2 ; move disk 2 to the left
3 [A] → 1 ; move disk 1 to the right
4 [A] → 3 ; move disk 3 to the right
5 [A] → 1 ; (…)
6 [A] → 2
7 [A] → 1


(08-11-2018 08:35 PM)Thomas Okken Wrote:  Doing it on the 25 does seem a bit ambitious.

It should be possible to convert this program for the HP-25.

Cheers
Thomas


Edit: Fixed typo in line 08 of the program.
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Weakest calculator/pocket computer that can do Tower of Hanoi? - Thomas Klemm - 08-12-2018 07:16 AM



User(s) browsing this thread: 2 Guest(s)