``Towers of Hanoi'': French Solution
Java implementation by Apostolos Syropoulos
The French solution is given in the form of pseudo-code in
[4]. The code shown below is an adaption of
that code to Java:
PEG x, y, z;
boolean current_even, previous_even;
x = B; y = C; z = A;
previous_even = "n is even";
for (i=1; i<=(Math.pow(2, n)-1); i++)
{
current_even = "the rightmost 1 in the binary representation
of i has an even index";
if (current_even)
{
swap(y, z);
}
else if (!current_even && previous_even)
{
swap(x, z);
}
else if (current_even && !previous_even)
{
swap(x, z);
swap(y, z);
}
move(x, y);
previous_even = current_even;
}
The first problem we must tackle is a way to determine whether the rightmost
1 in the binary representation of i has an even index. Let's
suppose we have at our disposal Si, then its i-th
element is the index of the rightmost 1 in the binary representation of
i. Computing Si is not difficult, if we think
that the elements of Si are symmetric, i.e.,
there is a middle element at position m and for any k,
elements at positions m-k and m+k are equal.
Using this remark we can easily derive the following code:
S[0] = 0; S[1] = 1;
for (i=2; i <= height; i++)
{
middle = (int)Math.pow(2, i-1);
S[middle] = i;
for (j=middle+1; j <= 2*middle-1; j++)
{
S[j] = S[j-middle];
}
}
The rest of the pseudo-code can be straightforward implemented in Java. The only
problem may a way to determine whether an integer is even or odd. We can
simply check the expression i mod 2, if it is equal to zero, then
i is even, otherwise it is odd. The following Java code does the job:
(i % 2 == 0) ? true : false
Back to main page
Get the source code