The tower of Hanoi is a puzzle invented by E. Lucas in 1883. Given a stack of n
ID: 3121604 • Letter: T
Question
The tower of Hanoi is a puzzle invented by E. Lucas in 1883. Given a stack of n disks arranged from larger t on the bottom to smallest on top placed on a rod, together with two empty rods (Fig. 2). the towers of Hanoi puzzle asks for the minimum number of moves required to move the stack from one rod to another, where moves are allowed only if they place smaller disks on top of larger disks. For example, if n = 3, then one of the possible solutions is: 1) move disk 1 (the smallest) to rod B; 2) move disk 2 to rod C; 3) move disk 1 to rod C; 4) move disk 3 to rod B; 5) move disk 1 to rod A; 6 move disk 2 to rod B; 7 move disk i to rod B. After 7 steps all the disks are on rod B. Find the minimum number of moves required to move the stack from one rod to another, if n = 4: _____ Find the minimum number of moves required to move the stack from one rod to another, if n = 5: _____ Describe the algorithm (the sequence of steps) that solves the Tower of Hanoi puzzle for an arbitrary n.Explanation / Answer
The Tower of Hanoi problem asks us to move n disks from Tower A to Tower C. The steps involved in the algorithm are:
1. Move n-1 disks (all except the biggest disk) from tower A to tower B.
2. Move the nth (biggest disk) from tower A to tower C.
3. Move the n-1 disks from tower B to tower C.
Amazingly, 1 and 3 are identical to the problem itself, that is they ask us to move n-1 disks from one tower to another. In other words if we write the tower of hanoi function as F(A,B,C,n), then the solution would be:
F(A,B,C,n) = F(A,C,B,n-1) + F(A,B,C,1) + F(B,A,C,n-1)
If the number of iterations needed is taken as f(n) for n disks, we have
f(n) = f(n-1) + 1 + f(n-1)
=> f(n) = 2*f(n-1) +1 = 2*[2*f(n-2)+1]+1 and so on.
f(1) = 1
f(2) = 2*1 + 1 = 3
f(3) = 2*3 + 1 = 7
f(4) = 2*7 + 1 = 15
f(5) = 2*15 + 1 = 31.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.