|
|
|
|
|
|
|
rithm: to free the nth circle, we have to move n - 1 circles. Each stage can be thought of as beginning again with three pegs, but with one less circle each time. Let's see if we can summarize this process, using n instead of an actual number. |
|
|
|
|
|
|
|
|
Get N Circles Moved from Peg 1 to Peg 3 |
|
|
|
|
|
|
|
|
Get n - 1 circles moved from peg 1 to peg 2
Move nth circle from peg 1 to peg 3
Get n - 1 circles moved from peg 2 to peg 3 |
|
|
|
|
|
|
|
|
|
This algorithm certainly sounds simple; surely there must be more. But this really is all there is to it. |
|
|
|
|
|
|
|
|
Let's write a recursive function that implements this algorithm. We can't actually move disks, of course, but we can print out a message to do so. Notice that the beginning peg, the ending peg, and the auxiliary peg keep changing during the algorithm. To make the algorithm easier to follow, we call the pegs beginPeg, endPeg, and auxPeg. These three pegs, along with the number of circles on the beginning peg, are the parameters of the function. |
|
|
|
|
|
|
|
|
We have the recursive or general case, but what about a base case? How do we know when to stop the recursive process? The clue is in the expression Get n circles moved. If we don't have any circles to move, we don't have anything to do. We are finished with that stage. Therefore, when the number of circles equals 0, we do nothing (that is, we return). |
|
|
|
|
|
|
|
|
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
{
if (circleCount > 0)
{
// Move n - 1 circles from beginning peg to auxiliary peg
DoTowers(circleCount - 1, beginPeg, endPeg, auxPeg);
cout << Move circle from peg << beginPeg
<< to peg << endPeg << endl;
// Move n - 1 circles from auxiliary peg to ending peg
DoTowers(circleCount - 1, auxPeg, beginPeg, endPeg);
}
} |
|
|
|
|
|