“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 *S _{i}*, then its

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: