/*
* hanoi.c
* This program solves the problem of the
towers of
*/
#include <stdio.h>
#define MAX_LINE 80
/* Prototypes:
*/
int move_tower (int n, int from, int to);
int main ()
{
char in[MAX_LINE];
int n;
int n_moves;
/* Read the height
of the tower. */
do
{
printf ("Please enter the height of the tower: ");
scanf ("%s", in);
n = atoi(in);
} while (n
<= 0);
/* Move a tower of
height n from the first pole to the second pole. */
n_moves = move_tower (n, 1, 2);
printf ("The solution requires %d moves.\n",
n_moves);
return
(0);
}
/*
------------------------------------------------------------------------
* Function: move_tower
* Purpose : Move a
tower from one pole to the other.
* Input
: n - The height of the tower
(number of rings in it).
*
from - The source pole.
*
to -
The target pole.
* Returns : The
number of moves required.
*/
int move_tower (int n, int from, int to)
{
int aux;
int n_moves;
/* In case of a
single ring, just move it from the source to the target. */
if
(n == 1)
{
printf ("Move ring [1] from pole no. %d to
pole no. %d\n", from, to);
return
(1);
}
/* Since the three poles are indexed 1, 2 and 3 we can easily
find the index
of the free
auxiliary pole using (1 + 2 + 3 = 6): */
aux = 6 - from - to;
/* Move the top
(n-1) rings from the source pole to the auxiliary pole. */
n_moves = move_tower (n - 1, from, aux);
/* Move the buttom
ring from the source pole to the target pole. */
printf ("Move ring [%d] from pole no. %d to
pole no. %d\n", n, from, to);
n_moves++;
/* Move the top
(n-1) rings from the auxiliary pole to the target pole. */
n_moves += move_tower (n - 1, aux, to);
return
(n_moves);
}