tower of honai

#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;
}
Upload