Tower of Hanoi is one of the most popular recursive problems that everyone practices when they start learning the recursion concept. In this problem, we have three pillars and we have to move some disks from one pillar to another pillar.
Let say, we have three pillars named A as source pillar, B as a temporary pillar, and C as a destination pillar. Pillar A has a finite number of disks and these disks are arranged in decreasing order of their size. We have to move all the disks from source pillar A to destination pillar C using temporary pillar B but you have to follow two conditions while doing this-
- You can move only one disk from one pillar to another at a time.
- A larger disk cannot be placed on a smaller disk.
The approach of solving tower of Hanoi problem recursively,
- Move upper (n-1) disks from A to B using C as the temporary pillar.
- Move nth disk from A to C.
- Move (n-1) disks from B to C using A as the temporary pillar.
The base condition of our recursive approach is when we have to move only one disk from source to destination pillar and return.
C++ Program to Tower of Hanoi Problem.
#include <iostream>
using namespace std;
void tofh(int ndisk, char source, char temp, char dest)
{
if(ndisk == 1)
{
cout<<"Move disk "<<ndisk<<" from "<<source<<" to "<<dest<<endl;
return;
}
tofh(ndisk-1, source, dest, temp);
cout<<"Move disk "<<ndisk<<" from "<<source<<" to "<<dest<<endl;
tofh(ndisk-1, temp, source, dest);
}
int main() {
char source = 'A', temp = 'B', dest = 'C';
int ndisk;
cout<<"\nEnter the number of disks: ";
cin>>ndisk;
cout<<"\nSequence of steps: \n";
tofh(ndisk, source, temp, dest);
return 0;
}
Output:
Enter the number of disks: 3
Sequence of steps:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
No comments:
Post a Comment