This program implements the “classical” recursive algorithm that
solves the Towers of Hanoi problem. The recursive algorithm
is based on the observation that moving a tower of height h
from
pole A to pole
B is equivalent to moving a tower of height
h-1
to pole C,
them moving the last disk from pole A to
pole B, and finally
moving the the tower from pole C to
B. So the problem of moving a tower
of height h
, has been reduced to the one of moving a tower of height
h-1
.
The following Java application uses only one class variable, moves
,
which holds the number of moves so far. The variable is used only for
formating purposes.
<*>= import java.io.*; public class hanoiA { static int moves=0; //number of moves so far <method getInt> <method hanoi> <method moveDisk> <method main> }
This code is written to a file (or else not used).
Method getInt
is used to read an integer from the user terminal.
The method is based on the new API therefore the whole program cannot
be executed with an old JDK. Its functionality is very simple: it reads
an input line which is supposed to contain only one integer. If the line
contains what should contain it transforms the line into a valid integer and
return it, otherwise it returns the number 1 and print an error message.
<method getInt>= static int getInt() { String line; BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); try { line = in.readLine(); int i = Integer.valueOf(line).intValue(); return i; } catch (Exception e) { System.err.println("***Error: Input is not a number.\n" + "Input assumed to be the number 1"); return 1; } }
Used above.
Method hanoi
is the fromPole
, the toPole
and the withPole
. Initially the tower
has height, say n
. Then we must move a tower of height n-1
from fromPole
to withPole
, move the biggest disk from
fromPole
to toPole
and finally move the tower of height n-1
to pole toPole
from withPole
. The first step is implemented as a
call to the method itself (procedures are called methods in Java),
the second to a call to method moveDisk
, and finally the third step
to a call to the itself. Particularly, the withPole
is the pole we
move the tower of height n-1
.
Each recursive method must have a termination condition, i.e., a condition that signals the termination of the method, or else it will never terminate! In our case this condition is reached when the height of the tower is zero.
<method hanoi>= static void hanoi(int height, char fromPole, char toPole, char withPole) { if (height >= 1) { hanoi(height-1, fromPole, withPole, toPole); moveDisk(fromPole, toPole); hanoi(height-1, withPole, toPole, fromPole); } }
Used above.
Method moveDisk
simply print on the terminal each move. A “move”
is defined by the orientation pole and the destination pole, each
represented by a character. The method prints a string of the form
“FT” where “F” denotes the orientation pole and “T” the destination
pole. Moreover, it tries to make the output readable. So, it prints only
twenty moves per line, by detecting multiples of the number 20.
<method moveDisk>= static void moveDisk(char fromPole, char toPole) { moves++; System.out.print(fromPole); System.out.print(toPole); System.out.print(((moves % 20)==0) ? '\n' : ' '); }
Used above.
Method main
is there where the whole action is. The first thing is
to define the poles as characters and to the height of the tower as
an integer. Next, it reads the height of the tower (in case we
type some rubbish or a negative number, the height is assumed equal to 1).
Finally, it prints out the solution. The last aspect of this program is
that it print its execution time in milliseconds.
<method main>= public static void main(String[] args) { long time1, time2; //for benchmarking int TowerHeight; char FromPole='A', ToPole='B', WithPole='C'; System.out.println("Enter Tower height..."); System.out.print("?"); TowerHeight = getInt(); time1 = System.currentTimeMillis(); hanoi(TowerHeight, FromPole, ToPole, WithPole); time2 = System.currentTimeMillis(); System.out.println(); System.out.print(time2-time1); //print execution time in msec System.out.println(" msec execution time"); }
Used above.
*Back to the main page
Get the source code
Code Chunk Index