#include <iostream.h> 
#include <math.h> 
#define ARRAYSIZE 100 
/************************************************************************************************* 
PROGRAMMED BY : REHAN AHMED KHAN 
PAKISTAN- KARACHI 
BS student in FAST University 
(foundation for advancement of science and technology) 
this program is free ware and anyone can use it. 
/************************************************************************************************/ 
/************************************************************************************************* 
* THE ALGORITHM USED IS AS FOLLOWS * 
* * 
* Because the tree is complete it can be stored in an array of 2^n-1. * 
* The root of the tree is in position 2^(n-1)-1 * 
* for any level j, the first node at that level is in position 2^(n-1-j)-1 * 
* and each successive node at that level is 2^(n-j) elements beyond the previous element * 
* at that level * 
* So the sequential traversal of the array produces the solution of Towers of Hanoi Problem * 
* * 
*************************************************************************************************/ 
class TowersHanoi 

    { 
     private: 
     struct //node structure 

         { 
         char chToPeg; 
         char chFromPeg; 
         int iDiskNo; 
         }node[ARRAYSIZE]; //Array of Nodes 
         
         char except(char chFromPeg, char chToPeg); //returns peg other than provided as parameter 
         public: 
         TowersHanoi(); //constructor 
         //generates the tree 
         void generateTree(char chFromPeg,char chToPeg, int iDiskNo); 
    }; 

    ////////////////////////////////////////////////////////////////////////////////////////////////// 
    TowersHanoi::TowersHanoi() 

        { 
         int iDiskNo; 
         cout << "\nENTER THE NUMBER OF DISKS >> "; 
         cin >> iDiskNo; 
         
         generateTree('A','B',iDiskNo); 
         int cMoves=(int)pow(2,iDiskNo)-1; 
         
         cout << "THE MOVES ARE AS FOLLOWS\n"; 
         for(int i=0;i<cMoves;i++) 
         cout << i+1 << ": " <<"Move Disk " << node[i].iDiskNo << " From " << node[i].chFromPeg 
         << " To " << node[i].chToPeg << endl; 
    } 

    ////////////////////////////////////////////////////////////////////////////////////////////////// 
    void TowersHanoi::generateTree(char chFromPeg, char chToPeg, int iDiskNo) 

        { 
         int j, iLevel=1, iDistance, iDistance2; 
         int iNodeIndex; 
         
         node[(int)pow(2,iDiskNo-1)-1].chToPeg=chToPeg; 
         node[(int)pow(2,iDiskNo-1)-1].chFromPeg=chFromPeg; 
         node[(int)pow(2,iDiskNo-1)-1].iDiskNo=iDiskNo; 
         for(int i=1;i<=iDiskNo-1;i++) 

             { 
             iDistance=0; 
             iDistance2=(int)pow(2,iDiskNo-i); 
             for(j=0;j<(int)pow(2,i);j++) 

                 { 
                 if(j%2==0) 

                     { 
                     iNodeIndex=iDistance+(int)pow(2,iDiskNo-1-i)-1; 
                     node[iNodeIndex].chToPeg= 
                     except(node[iNodeIndex+iDistance2/2].chFromPeg, 
                     node[iNodeIndex+iDistance2/2].chToPeg); 
                     
                     node[iNodeIndex].chFromPeg= 
                     node[iNodeIndex+iDistance2/2].chFromPeg; 
                     node[iNodeIndex].iDiskNo=iDiskNo-iLevel; 
                     } 
                     else 

                         { 
                         iNodeIndex=iDistance+(int)pow(2,iDiskNo-1-i)-1; 
                         node[iNodeIndex].chFromPeg= 
                         except(node[iNodeIndex-iDistance2/2].chFromPeg, 
                         node[iNodeIndex-iDistance2/2].chToPeg); 
                         
                         node[iNodeIndex].chToPeg= 
                         node[iNodeIndex-iDistance2/2].chToPeg; 
                         node[iNodeIndex].iDiskNo=iDiskNo-iLevel; 
                         } 
                         iDistance+=(int)pow(2,iDiskNo-i); 
                         } 
                         iLevel++; 
                         } 
                    } 

                    ////////////////////////////////////////////////////////////////////////////////////////////////// 
                    char TowersHanoi::except(char chFromPeg, char chToPeg) 

                        { 
                         if(chFromPeg=='A' && chToPeg=='B' || chFromPeg=='B' && chToPeg=='A') 
                         return 'C'; 
                         if(chFromPeg=='A' && chToPeg=='C' || chFromPeg=='C' && chToPeg=='A') 
                         return 'B'; 
                         if(chFromPeg=='B' && chToPeg=='C' || chFromPeg=='C' && chToPeg=='B') 
                         return 'A'; 
                    } 

                    ////////////////////////////////////////////////////////////////////////////////////////////////// 
                    /*ostream& operator << (ostream& s,nodeHanoi node) 

                        { 
                         return s <<"Move Disk " << node.iDiskNo << " From " << node.chFromPeg 
                         << " To " << node.chToPeg << endl; 
                    }*/ 

                    ////////////////////////////////////////////////////////////////////////////////////////////////// 
                    void main(void) 

                        { 
                         cout << "A represents FROM PEG,\nB represents TO PEG,\nC represents AUXILLARY PEG\n"; 
                         TowersHanoi towersHanoi; 
                    }