This C++ program displays the solution to the Tower of Hanoi problem using the base-2 representation of the move number with the following rules:-
There is one binary digit (bit) for each disk.
The most significant (leftmost) bit represents the largest disk. A value of 0 indicates that the largest disk is on the initial peg, while a 1 indicates that it’s on the final peg.
The bitstring is read from left to right, and each bit can be used to determine the location of the corresponding disk.
A bit with the same value as the previous one means that the corresponding disk is stacked on top the previous disk on the same peg.
A bit with a different value to the previous one means that the corresponding disk is one position to the left or right of the previous one.
There is one binary digit (bit) for each disk.
The most significant (leftmost) bit represents the largest disk. A value of 0 indicates that the largest disk is on the initial peg, while a 1 indicates that it’s on the final peg.
The bitstring is read from left to right, and each bit can be used to determine the location of the corresponding disk.
A bit with the same value as the previous one means that the corresponding disk is stacked on top the previous disk on the same peg.
A bit with a different value to the previous one means that the corresponding disk is one position to the left or right of the previous one.
Here is the source code of the C++ program to display the movement of disks from one peg to the other. This C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is given below.
/*
* C++ program to Solve Tower of Hanoi Problem using Binary Value
*/
#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
int main()
{
int n, x;
cout<<"\nEnter the No. of Disks: ";
cin>>n;
for (x = 1; x < (1 << n); x++)
{
printf("\nMove from Peg %i to Peg %i", (x&x-1)%3+1, ((x|x-1)+1)%3+1);
}
cout<<"\n";
getch();
}
Output Enter the No. of Disks: 4 Move from Peg 1 to Peg 3 Move from Peg 1 to Peg 2 Move from Peg 3 to Peg 2 Move from Peg 1 to Peg 3 Move from Peg 2 to Peg 1 Move from Peg 2 to Peg 3 Move from Peg 1 to Peg 3 Move from Peg 1 to Peg 2 Move from Peg 3 to Peg 2 Move from Peg 3 to Peg 1 Move from Peg 2 to Peg 1 Move from Peg 3 to Peg 2 Move from Peg 1 to Peg 3 Move from Peg 1 to Peg 2 Move from Peg 3 to Peg 2
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Next Steps:
- Get Free Certificate of Merit in Data Structure I
- Participate in Data Structure I Certification Contest
- Become a Top Ranker in Data Structure I
- Take Data Structure I Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for Computer Science Internship
- Practice Programming MCQs
- Apply for Data Structure Internship
- Buy Computer Science Books
- Practice Design & Analysis of Algorithms MCQ