|
|
|
|
|
|
|
It's hard to believe that such a simple algorithm actually works, but we'll prove it to you. Following is a driver program that calls the DoTowers function. Output statements have been added so you can see the values of the actual parameters with each recursive call. Because there are two recursive calls within the function, we have indicated which recursive statement issued the call. |
|
|
|
|
|
|
|
|
//******************************************************************
// TestTowers program
// This program, a test driver for the DoTowers function, reads in
// a value from standard input and passes this value to DoTowers
//******************************************************************
#include <iostream.h>
#include <iomanip.h> // For setw()
void DoTowers( int, int, int, int );
int main()
{
int circleCount; // Number of circles on starting peg
cout << Input number of circles: ;
cin >> circleCount;
cout << OUTPUT WITH << circleCount << CIRCLES << endl
<< endl;
cout << CALLED FROM #CIRCLES << setw(8) << BEGIN
<< setw(8) << AUXIL. << setw(5) << END
<< INSTRUCTIONS << endl
<< endl;
cout << Original :;
DoTowers(circleCount, 1, 2, 3);
return 0;
}
//******************************************************************
void DoTowers(
/* in */ int circleCount, // Number of circles to move
/* in */ int beginPeg, // Peg containing circles to move
/* in */ int auxPeg, // Peg holding circles temporarily
/* in */ int endPeg ) // Peg receiving circles being moved
// This recursive function moves circleCount circles from beginPeg
// to endPeg. All but one of the circles are moved from beginPeg
// to auxPeg, then the last circle is moved from beginPeg to endPeg,
// and then the circles are moved from auxPeg to endPeg.
// The subgoals of moving circles to and from auxPeg are what
// involve recursion |
|
|
|
|
|