/* tower of hanoi using recursion */
#include<stdio.h>
int main(void)
{
unsigned int nvalue;
char snvalue = 'L' , invalue = 'C' , dnvalue = 'R' ;
void hanoi(unsigned int , char , char , char);
printf(" enter number of disks : ");
scanf("%u",&nvalue );
printf("\n\ntower of hanoi problem with %d disks \n ", nvalue )"
hanoi(nvalue , snvalue , invalue , dnvalue );
printf("\n");
return 0 ;
}
void hanoi(unsigned n , char snd1 , char ind1 , char dnd1 )
{
if(n!=0)
{
/* move n-1 disks from starting to intermadiate needles */
hanoi(n-1 , snd1 , dnd1 , ind1 );
/* move disk n from start to destination */
printf("move disk %d from %c to %c\n ", n , snd1 , dnd1);
/* move n-1 disks from intermediate to destination needle */
hanoi(n-1 , ind1 , snd1 , dnd1 );
}
}
#include <iostream.h> // a disk with a value , which is an element of the stack ,tower in this case class Disk { public: int value; Disk* next; }; class Tower //a stack data structure representing a tower { public: int size; Disk* current; Tower() { size=0; current=NULL; }//default constructor int peep(); bool push(int); bool pop(); bool isEmpty(); int getTowerSize(); void printTowerSize(); void printTowerDisks(); void printTowerMenu(); }; int Tower::peep() { return this->current->value; } bool Tower::push(int ele) { Disk* temp; temp=new Disk; if(current==NULL) { temp->next=NULL; } else { temp->next=current; } temp->value=ele; this->current=temp; size++; return false; } bool Tower::pop() { if(isEmpty()) { cout<<"\nTower is Empty\n"; return false; } else { current=current->next; size=size--; } return true; } bool Tower::isEmpty() { if(getTowerSize()==0) return true; return false; } int Tower::getTowerSize() { return size; }//returns size of the Tower void Tower::printTowerSize() { cout<<"\nThe Size of the Tower:"<<size<<"\n"; }//print the Tower size void Tower::printTowerDisks() { if(this->isEmpty()) { cout<<"-----\n"; cout<<" "<<endl; cout<<"-----\n"; return; } Disk *curr2; curr2=this->current ; cout<<"-----\n"; cout<<"Tower\n"; cout<<"-----\n"; int i=0; while(curr2 !=NULL) { if(i>4) break; i++; cout<<" |"<<curr2->value<<"|\n"; curr2=curr2->next; } }// print the Tower void createSourceTower(Tower *source,int numberOfDisks) { for(int i=numberOfDisks;i>0;i--) { source->push(i); } } void moveDisk(Tower *source,Tower *dest) // movinng a disk from source to destionation { dest->push(source->current->value ); source->pop(); } void hanoi( int N, Tower *source, Tower *dest,Tower *aux ) // move N disks from source to destination { if (N > 0 ) { hanoi(N - 1, source, aux, dest); //move n-1 disks from source to auxxilary (sub problem) moveDisk(source,dest); //move nTH disk from source to destination hanoi(N - 1, aux, dest, source); //move n-1 disks from auxillary to destination (sub problem) } } void main() { Tower *source,*destination,*auxillary; //Towers required for the 3 towers source destination and auxillary source=new Tower; destination=new Tower; auxillary=new Tower; //take number of disks from user int numberOfDisks; cout<<"Enter number of Disks in the source Tower"; cin>>numberOfDisks; //inserting the disks into the source tower createSourceTower(source,numberOfDisks); cout<<"==============================================="<<endl; cout<<"Initial Scenario of the Towers "<<endl; cout<<"Source"<<endl; source->printTowerDisks (); cout<<"Auxillary"<<endl; auxillary->printTowerDisks (); cout<<"Destination"<<endl; destination->printTowerDisks (); hanoi( numberOfDisks,source, destination, auxillary ); cout<<"==============================================="<<endl; cout<<"Final Scenario of the Towers "<<endl; cout<<"Source"<<endl; source->printTowerDisks(); cout<<"Auxillary"<<endl; auxillary->printTowerDisks (); cout<<"Destination"<<endl; destination->printTowerDisks (); cout<<"==============================================="<<endl; }
/* hanoi.c */ #include <stdio.h> #include <stdlib.h> static long step; static void Hanoi (int n, int from, int to,int spare) { if (n>1) Hanoi (n-1,from,spare,to); printf ("Step %ld: move #%d %d-->%d\n", ++step, n, from, to); if (n>1) Hanoi (n-1,spare,to,from); } int main (int argc, char **argv) { int n; if (argc==1 (n= atoi(argv[1]))<=0) n= 5; step= 0; Hanoi (n, 1, 2, 3); return 0; }
Research Towers Of Hanoi http://en.wikipedia.org/wiki/Tower_of_Hanoi You will find your answer
// stack to contain content Stack sourceStack = new Stack(); // ... fill sourceStack with content // stack to contain reversed content Stack targetStack = new Stack(); while (!sourceStack.empty()) { targetStack.push(sourceStack.pop()); } // targetStack contains the reversed content of sourceStack
Many search algorithms are possible. Tree-based methods, in which all paths to all solutions are produced, is one option. Each node in the tree would represent a "state" or "configuration" of the problem, while an edge from one node to the next represents the "move" you make. Consequently, finding a solution to this problem is equivalent to building the tree while checking if each node is a valid solution. Another method, such the A* algorithm is a heuristic search algorithm. You would use a heuristic function that estimates the optimal path to the solution from the current node. It is the quickest, but since it is a heuristic algorithm, it is not guaranteed to always return the correct answer, since this is dependent on the heuristic function you use in your algorithm.
To move n disks, you need 2n-1moves. In this case, 31.
move from, to, spare, count: move from, spare, count-1 single_move from, to move spare, to, count-1
According to the legend, when the last move of the Tower of Hanoi puzzle is completed, the world will end.
That game with 5 or more rings and 3 posts is known as "the Towers of Hanoi".
#include#includevoid hanoi(int x, char from,char to,char aux){if(x==1){printf("Move Disk From %c to %c\n",from,to);}else{hanoi(x-1,from,aux,to);printf("Move Disk From %c to %c\n",from,to);hanoi(x-1,aux,to,from);}}int main(void){int disk;clrscr();printf("Enter the number of disks you want to play with:");scanf("%d",&disk);double moves=pow(2,disk)-1;printf("\nThe No of moves required is=%g \n",moves);hanoi(disk,'A','C','B');getch();}
To successfully solve the Tower of Hanoi puzzle and emerge victorious, one must follow a specific strategy of moving the disks from one peg to another while adhering to the rules of the game. The key is to always move the smallest disk first and to plan ahead to minimize the number of moves required. By carefully strategizing and being patient, one can solve the puzzle and achieve victory.
#include <iostream.h> // a disk with a value , which is an element of the stack ,tower in this case class Disk { public: int value; Disk* next; }; class Tower //a stack data structure representing a tower { public: int size; Disk* current; Tower() { size=0; current=NULL; }//default constructor int peep(); bool push(int); bool pop(); bool isEmpty(); int getTowerSize(); void printTowerSize(); void printTowerDisks(); void printTowerMenu(); }; int Tower::peep() { return this->current->value; } bool Tower::push(int ele) { Disk* temp; temp=new Disk; if(current==NULL) { temp->next=NULL; } else { temp->next=current; } temp->value=ele; this->current=temp; size++; return false; } bool Tower::pop() { if(isEmpty()) { cout<<"\nTower is Empty\n"; return false; } else { current=current->next; size=size--; } return true; } bool Tower::isEmpty() { if(getTowerSize()==0) return true; return false; } int Tower::getTowerSize() { return size; }//returns size of the Tower void Tower::printTowerSize() { cout<<"\nThe Size of the Tower:"<<size<<"\n"; }//print the Tower size void Tower::printTowerDisks() { if(this->isEmpty()) { cout<<"-----\n"; cout<<" "<<endl; cout<<"-----\n"; return; } Disk *curr2; curr2=this->current ; cout<<"-----\n"; cout<<"Tower\n"; cout<<"-----\n"; int i=0; while(curr2 !=NULL) { if(i>4) break; i++; cout<<" |"<<curr2->value<<"|\n"; curr2=curr2->next; } }// print the Tower void createSourceTower(Tower *source,int numberOfDisks) { for(int i=numberOfDisks;i>0;i--) { source->push(i); } } void moveDisk(Tower *source,Tower *dest) // movinng a disk from source to destionation { dest->push(source->current->value ); source->pop(); } void hanoi( int N, Tower *source, Tower *dest,Tower *aux ) // move N disks from source to destination { if (N > 0 ) { hanoi(N - 1, source, aux, dest); //move n-1 disks from source to auxxilary (sub problem) moveDisk(source,dest); //move nTH disk from source to destination hanoi(N - 1, aux, dest, source); //move n-1 disks from auxillary to destination (sub problem) } } void main() { Tower *source,*destination,*auxillary; //Towers required for the 3 towers source destination and auxillary source=new Tower; destination=new Tower; auxillary=new Tower; //take number of disks from user int numberOfDisks; cout<<"Enter number of Disks in the source Tower"; cin>>numberOfDisks; //inserting the disks into the source tower createSourceTower(source,numberOfDisks); cout<<"==============================================="<<endl; cout<<"Initial Scenario of the Towers "<<endl; cout<<"Source"<<endl; source->printTowerDisks (); cout<<"Auxillary"<<endl; auxillary->printTowerDisks (); cout<<"Destination"<<endl; destination->printTowerDisks (); hanoi( numberOfDisks,source, destination, auxillary ); cout<<"==============================================="<<endl; cout<<"Final Scenario of the Towers "<<endl; cout<<"Source"<<endl; source->printTowerDisks(); cout<<"Auxillary"<<endl; auxillary->printTowerDisks (); cout<<"Destination"<<endl; destination->printTowerDisks (); cout<<"==============================================="<<endl; }
/* hanoi.c */ #include <stdio.h> #include <stdlib.h> static long step; static void Hanoi (int n, int from, int to,int spare) { if (n>1) Hanoi (n-1,from,spare,to); printf ("Step %ld: move #%d %d-->%d\n", ++step, n, from, to); if (n>1) Hanoi (n-1,spare,to,from); } int main (int argc, char **argv) { int n; if (argc==1 (n= atoi(argv[1]))<=0) n= 5; step= 0; Hanoi (n, 1, 2, 3); return 0; }
void Hanoi (int n, int nfrom, int nto, int nspare) { if (n>1) Hanoi (n-1, nfrom, nspare, nto); printf ("Move from %d to %d\n", nfrom, nto); if (n>1) Hanoi (n-1, nspare, nto, nfrom); } int main (void) { Hanoi (6, 1, 2, 3); return 0; }
There is a formula for calculating the number of moves. The formula is 2^n-1. This means that to move one disk the number of moves can be calculated as 2^1-1. For two disks the calculation is 2^2-1. Using this formula the answer 1023 can be found
It would take 264 - 1 seconds or, at one move per second, approx 585 billion years.
It is called "Tower of Hanoi". See http://en.wikipedia.org/wiki/Tower_of_Hanoi for more info.