code:
Can't Copy and Paste this?
Click here for a copy-and-paste friendly version of this code!
Terms of Agreement:
By using this code, you agree to the following terms...
1) You may use this code in your own programs (and may compile it into a program and distribute it in compiled format for langauges that allow it) freely and with no charge.
2) You MAY NOT redistribute this code (for example to a web site) without written permission from the original author. Failure to do so is a violation of copyright laws.
3) You may link to this code from another website, but ONLY if it is not wrapped in a frame.
4) You will abide by any additional copyright restrictions which the author may have placed in the code or code's description.
// Program: General Tower of Hanoi
#include
#include
#include
// Pole location
enum POLE { left = 1, middle, right };
// intialize the original loaction of ea
// ch disk
// disks' sizes depends on their index
// higher the index is, larger the disk
// is.
void InitializeDisk(POLE*, const int&);
// return a Pole randomly
POLE RandomLocation();
// function to solve general Tower of Ha
// noi problem
void GeneralTOH(POLE*, const int&);
// function to solve basic Tower of Hano
// i problem,
// which is used by GeneralTOH to help s
// olve
// general Tower of Hanoi problem
void BasicTOH(const int&, const POLE&, const POLE&, const POLE&);
// move disk information
// display the moves and count the moves
//
void MoveDisk(const int&, const POLE&, const POLE&);
// move count
static int MoveCount = 0;
void main()
{
int n;
cout << "Please enter the number of disks: ";
cin >> n;
POLE* DiskLocation;
DiskLocation = new POLE[n];
srand(int(time(NULL)));
InitializeDisk(DiskLocation, n);
GeneralTOH(DiskLocation, n);
delete[] DiskLocation;
DiskLocation = NULL;
return;
}
void GeneralTOH(POLE* DiskLocation, const int& total)
{
POLE temp;
int current;
for (current = 0; current < total; current++)
{
// when current disk is not the largest disk....
if (current < total - 1)
{
if (current < total - 2)
{
// To save moves, move the next one on the top of the next next one
// before move the smallest one to current one to next one
// only if current, next and next next are located on the different Poles.
if (DiskLocation[current + 2] != DiskLocation[current + 1]
&& DiskLocation[current + 2] != DiskLocation[current]
&& DiskLocation[current + 1] != DiskLocation[current])
{
MoveDisk(current + 1, DiskLocation[current + 1], DiskLocation[current + 2]);
DiskLocation[current + 1] = DiskLocation[current + 2];
}
}
else // case: (current == total - 2)
{
// move the largest one to the right
// if the largest and others are not located on the same Poles,
// and the right Pole is empty.
// this step will save a lot of moves for the situation that
// the sencond largest and the largest are not located on the same Poles
// and neither of them located on the right Pole oringinally.
if (DiskLocation[current] != right
&& DiskLocation[current + 1] != right
&& DiskLocation[current] != DiskLocation[current + 1])
{
MoveDisk(current + 1, DiskLocation[current + 1], right);
DiskLocation[current + 1] = right;
}
}
if (DiskLocation[current + 1] != DiskLocation[current])
{
// find the Pole which are not used by current and next disks
temp = POLE((left + middle + right)
- (DiskLocation[current] + DiskLocation[current + 1]));
BasicTOH(current + 1, DiskLocation[current],
DiskLocation[current + 1], temp);
}
}
else
{
// check if the largest one is located at right Pole.
// if so, stop, otherwise, move all disks to the right Pole.
if (DiskLocation[current] != right)
{
temp = POLE(left + middle - DiskLocation[current]);
BasicTOH(total, DiskLocation[current], right, temp);
}
}
}
cout << endl << "Total Moves: " << MoveCount << endl;
return;
}
void BasicTOH(const int& n, const POLE& Start, const POLE& Goal, const POLE& Temp)
{
if (n == 0)
return;
BasicTOH(n - 1, Start, Temp, Goal);
MoveDisk(n, Start, Goal);
BasicTOH(n - 1, Temp, Goal, Start);
}
void MoveDisk(const int& n, const POLE& Start, const POLE& Goal)
{
cout << "Disk[" << n << "]:" << Start << "-->" << Goal << "";
MoveCount++;
return;
}
void InitializeDisk(POLE* DiskLocation, const int& n)
{
int i;
for (i = 0; i < n; i++)
{
DiskLocation[i] = RandomLocation();
cout << "Disk[" << i + 1 << "]: " << DiskLocation[i] << endl;
}
}
POLE RandomLocation()
{
return POLE(rand() % (right -left + 1) + left);
}