Tower of Hanoi

Write a program to implement a Tower of Hanoi (Recursive implementation) in

C /C++ language.

To understand and implement Recursive algorithm using the Tower of Hanoi

problem and study Divide and Conquer strategy.

Divide: Divide the problem into a number of subproblem that are smaller instances of the same problem.

Conquer: Conquer the subproblem by solving them recursively. If the subproblem sizes are small enough, just solve the subproblems in a straight forward manner.

Combine: Combine the solutions to the sub problems into the solutions for the original problem.

When the subproblems are large enough to solve recursively, we call that the recursive case. Once the subprobles become small enough that we no longer recurse, recursion “bottoms out” and that we have gone down to the base case. In combine step, we solve subproblems that are quite not same as original.

Recurrences go hand in hand with divide-and-conquer paradigm, because they give us a natural way to characterize the running times of divide-and-conquer algorithms.

{

If small((P) then return S(P);

Else

{

Divide P into smaller instances say P1,P2,P3……….Pk ,

k>=1;

Apply DAndC to each of thse subproblems

Return Combine(DAndC(P1),DAndC(P2),……DAndC(Pk));

}

}

Assume that there are ‘n’ number of disks on tower A. The disks are of decreasing size and are stacked on the tower in decreasing order of size bottom to top. Besides this tower, there are two other towers labeled B and C. The disks from tower A are to be moved to tower B using tower C as intermediate storage. The disks are to be moved one at a time. In addition, at no time can a disk be on top of a smaller disk.

Assume that there are n number of disks on tower A. To get the largest disk to the bottom of tower B, we move the remaining n-1 disks to tower C and then move the largest disk to tower B. Now ,we are left with the task of moving the disks from tower C to tower B. To do this, we have tower A and B available. The fact that the tower B has a disk can be ignored as the disk is larger than the disks being moved from tower C and so any disk can be placed on top of it.

Algorithm TowerofHanoi(n,x,y,z)

//Move the top n disks from tower x to tower y

{

If(n >= 1)then

{

TowerofHanoi(n-1,x,z,y);

Write(“move top disk from tower”,x,”to top of tower”,y);

TowerofHanoi(n-1,z,y,x);

}

}

The recursive nature of the solution is apparent from the above algorithm. Our solution for an n-disk problem is formulated in terms of solutions to two(n-1)disk problems.

T(n)=g(n)…….. n is small

=T(n1)+T(n2)+……+T(nk)+f(n)

In general,

T(n)=T(1)

=aT(n/b)+f(n). n=2k

t_n = 0

=t_(n-1) + 1+t(n-1)

Where first t_{(n-1) =}movement of (n-1) disks from tower A to tower C. 1 is for the movement of the bottommost disk from tower A to tower B.

Second t_(n-1) = movement of the (n-1) disks from tower C to tower B.

t_{n =} 2t_(n-1) + 1

Thus,

t_n – 2t_n-1 = 1 b=1

p(n)=1

Characteristic polynomial is (x-2) (x-1)

t_n = c₁ 1ⁿ + c₂ 2n

t₁= 2t₀ + 1

t₀ = 0 …..Original recursive relation

t₁ = 1

when n=0

t_n = c₁ + c₂ = 0, t₀ is0

When n=1

t_n = c₁ + 2c₂ =1, t₁ is0

-c₂ = -1

c₂ = 1

c₁ = -1

t_n = 2ⁿ-1 ……tower of hanoi

t_{n =} number of disk movements.