|
| | Program 1 - January 15
Note: Programming solutions to this problem are now available for download
in the samples
directory of the FTP site.
This assignment involves programming to solve a classic problem, The Towers
of Hanoi. The problem is described in your text on page 217 - problem 3.42. For
extra credit, solve problem 3.43as well.
Clarification of the Problem
In discussing the problem, I may have caused some confusion. In case of
doubt, use the problem statement in the text. Here is a summary:
- Three pegs are available.
- At the start of the problem, from 1 to 64 disks of different sizes are
placed on the first peg. They are all different sizes and are placed on the
peg in order of size - smaller on larger.
- To solve the problem, move all the disks to the third peg.
- You are allowed to move only one disk at a time.
- You can never place a larger disk on a smaller one but you may place any
disk on an empty peg.
Hints
- Note that you are required to solve this recursively. That means that you
will write a function which - at any stage - either makes a move or calls
itself recursively or both.
- The method outlined in the text is ideal. If you want you can improve it
by not specifying the work peg (if you know the from disk and the to disk,
then you can figure out the work peg)
- Remember that to use a peg as a work peg, it must either be empty or
contain only larger disks than those you will place on it. If you do things
in the right order, you will guarantee this and no checking will be needed.
- Be sure you check that the user input (number of disks) is a valid number
that your program can deal with.
Extra Credit
- Problem 3.43 does the same thing without recursion. When we don't recurse,
we iterate - that is we loop. You will have lots more stuff to keep track
of.
- Recursion is hard to think about but easy to program once you get it.
- The iterative solution is even harder to think about and also hard to
program.
For Class Discussion
- What does this exercise tell you about the usefullness of recursion versus
iteration?
- How does use of recursion impact program performance?
- How does use of recursion impact development time?
|
