Lab Four: Recursion, part 2
Purpose:
This
lab will get you further acquainted with the concept of recursion. You will do this by writing a program to
simulate the Towers of
Prerequisites:
You
should understand recursion and be able to apply it to new problems.
Introduction:
The
Towers of Hanoi is a game that is not played much any more, but is frequently
used as a classic example of recursion.
The game consists of three posts and some number of disks (the number
varies between games, but it usually five or six). One of these posts begins with a stack containing
all of the disks. Each disk is a
different size, and the stack is in order from the largest disk on the bottom
to the smallest disk on the top.
The
goal of the game is to move the disks so that the entire stack is moved to
another post. The rules are simple: you may only move one disk at a time, and you
may never place a disk on top of another disk that is smaller than it is. These rules are simple, but they make the
game fairly complex.
Procedure:
1. Open a web browser (Internet Explorer or something
similar), and go to the web page http://jupiter.csc.depauw.edu/~sthede/hanoi/hanoi.html. This page
will display a version of the Towers of Hanoi where the disks begin in the
center post. You must move all the
pieces to either empty post, following the rules of the game.
2. Experiment with the game. Try a small number of disks at first. Can you see a pattern to the game? Can you explain the method of solution in a
brief, concise way? Keep trying until
you can solve the game consistently, then continue.
3. Do not read this until you have successfully solved
the Towers of
But, we can’t move the largest disk unless there are
no other disks on top of it. We also
cannot put the largest disk on top of any other disk. So, two things have to be true before we can
move the largest disk:
This means that the other four disks must be on post
B, and they must be in proper order.
Once all the disks but the largest have been moved to post B, then we
can move the largest from post A to post C.
After that, we just need to move the pile on post B on top of the
largest disk on post C, and we are done.
So, we can write a “solution” to the problem of moving
five disks from post A to post C like this:
·
Move four disks
from post A to post B.
·
Move one disk
from post A to post C.
·
Move four disks
from post B to post C.
Notice that we are not allowed to move a stack of four
disks in one move – does this mean that our solution is invalid?
No, not at all. How would we
move four disks from post A to post B?
We can use similar logic to define an algorithm for that as well:
·
Move three disks
from post A to post C.
·
Move one disk
from post A to post B.
·
Move three disks
from post C to post B.
Notice the recursive element of the solutions. If we want to generalize, we can form an
official algorithm for solving the Towers of Hanoi:
Assume we have a Towers of Hanoi game with posts A,
B, and C. To move n
disks from post x to post y, do the following:
·
Move n – 1 disks from post x to post z.
·
Move 1 disk from post x to post y.
·
Move n – 1 disks from post z to post
y.
There is one thing missing from this recursive
solution – a base case. What would be a
good base case for this solution?
Moving one disk is a good base case (moving zero disks
is not – why not?).
In the case where we are asked to move one disk from post x to post
y, we simply move it – there is no need for the recursive solution.
Given this, we should be able to write our own Towers
of Hanoi program, to give us the solution (at least in a text-based way).
4. Load the project file for lab 4.
5. In this lab, we are labelling
the posts 1, 2, and 3, for the left, middle, and right posts respectively. The first thing you need to do is add code in
the main function to get a number from the user and verify that the
number is larger than 0. This is the
number of disks that will be represented in the Towers of Hanoi game.
6.
Complete the
definition of the moveDisks function so
that the program prints out the correct solution for the Towers of Hanoi with
any number of disks (only try up to about 10 or so, more than that will take
way too long). You can test it by using
the solution to solve the Towers of Hanoi on the web page. A hint
about post numbers: if you have two post numbers x and y, you can get the
number of the third post by calculating 6 – x – y.
7. Extra Challenge: What is the running time for a
solution to Towers of Hanoi? In other
words, how many moves will it take to solve a Towers of Hanoi with n
disks?
8. Congratulations,
you’ve solved the Towers of Hanoi! Save
your work and get it checked off.
/* lab4.cpp - This file is a program that prints a
solution to the
Towers of
This numbers the posts such that the left post is number
1, the middle post is number 2, and the right post is
number 3.
Author: Scott Thede
Date:
*/
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
// Parameters:
Three integers - n is the number of disks to move, from
//
is the post from which we are moving the disks, and
//
to is the post to which the disks are moving.
// Pre: n
> 0, and that the disks being moved are smaller than any
//
other disks on the Towers.
// Post: The
instructions for moving n disks from from to to are printed.
void moveDisks(
int n, int from, int to ) {
// You write this
function.
}
// Parameters:
An integer n, which represents the number of disks
//
in the Towers of
// Pre:
None.
// Post: A
solution to the Towers of Hanoi with n disks has been printed,
//
if n > 0. Otherwise an error
message is printed.
void solveTowers(
int n ) {
if ( n <= 0 ) {
cout << "Error -
invalid number of disks. Aborting." << endl;
exit( 0 );
}
else {
// Assume moving from left post (post 1) to right post (post
3).
moveDisks(
n, 1, 3 );
}
}
// Main program.
void main( ) {
int n;
// Get the
number of disks.
cout << "Welcome to the
Towers of Hanoi!" << endl;
// Fill in code to make sure that the user
enters a
// number that is not negative.
// Solve the problem.
solveTowers(
n );
// Exit the
program.
cout << "Thanks for
playing!" << endl;
cout << "Press any key
to exit." << endl;
getch();
}