``Towers of Hanoi'': Fourth Grade Solution
Java implementation by Apostolos Syropoulos
The FGS uses a bit-string (BitStr)
to determine which disk to move. Initially this bit-string is set to
zero, i.e., all of its elements are zero. Hold is an array
that holds the position of disk with index i. The number of
TotalMoves is equal to 2height-1. Incrementing the
bit-string by one is equal to changing the first least significant zero
with one. Then we apply the technique described in the main text.
Please note that this implementation differs from the one presented
in [3], just because in FORTRAN the
lower bound of an array is 1, while in Java it is 0.
static void hanoi(int height)
{
int fromPole, toPole, Disk;
int[] BitStr = new int[height],
Hold = new int[height];
char[] Place = {'A', 'C', 'B'};
int i, j, temp;
for (i=0; i < height; i++)
{
BitStr[i] = 0;
Hold[i] = 1;
}
temp = 3 - (height % 2);
int TotalMoves = (int) Math.pow(2, height) - 1;
for (i=1; i <= TotalMoves; i++)
{
for (j=0 ; BitStr[j] != 0; j++)
BitStr[j] = 0;
BitStr[j] = 1;
Disk = j+1;
if (Disk == 1)
{
fromPole = Hold[0];
toPole = 6 - fromPole - temp;
temp = fromPole;
}
else
{
fromPole = Hold[Disk-1];
toPole = 6 - Hold[0] - Hold[Disk-1];
}
moveDisk(Place[fromPole-1], Place[toPole-1]);
Hold[Disk-1] = toPole;
}
}
Back to main page
Get the source code