• Register
100 points
5 1

Problem

Tower of Hanoi, is a mathematical and most popular problem which has been asked in many interviews. It consists of three rods and multiple disks. Initially, all the disks are placed on one rod, one over the other in ascending order of size similar to a cone-shaped tower.

The objective of this problem is to move the stack of disks from the initial rod to another rod, following these rules:

  • A disk cannot be placed on top of a smaller disk
  • You can pick only one disk at a time.

Approach

There are many approaches to solve this particular question but I am sharing recursive approach which amaze me very much.I seen this approach on net that taught by Prateek sir.

  • Consider one base case like n==0 or n==1 disk.
  • Then write recursive case which will solve the problem for n-1 by calling the function recursively.
  • Sove the problem for n-1 disk by first move the n-1 disks from source to helper stand.
  • After that take the last disk and move from source to destination.
  • At last,take n-1 disks from helper to destination using source rod.

Code

​#include <iostream>

using namespace std;
void towerOfHanoi(int n,char src,char dest,char helper){
    if(n==0){
        return;//base case
    }
    
    towerOfHanoi(n-1,src,helper,dest);//Recursive call  //first N-1 disks move from src to helper using dest(destination)
    cout<<"Move"<<n<<"disk from"<<src<<"to"<<dest<<endl;
    towerOfHanoi(n-1,helper,dest,src);
}
int main()
{
    int n;
    cin>>n;// enter n=3
    towerOfHanoi(n,'X','Z','Y');
    return 0;
}


​

Output

Move1disk fromXtoZ
Move2disk fromXtoY
Move1disk fromZtoY
Move3disk fromXtoZ
Move1disk fromYtoX
Move2disk fromYtoZ
Move1disk fromXtoZ

 

1 Comment

This very helpful article!