讲解 CS 20A: Data Structures with C++讲解 留学生C/C++语言

CS 20A: Data Structures with C++

Project 2 : Tower of Hanoi

Due: Friday, 4/ 19/2024 @ 11:59PM

Goal

Use the graphical capabilities of the ITP library to animate a recursive solution to the Tower of Hanoi problem. You will find a description, and a small animation, of the Tower of Hanoi in Wikipedia. The link ishttp://en.wikipedia.org/wiki/Tower_of_Hanoi.

Setup

.    The project already has a main.cpp file with almost no code in it. For this project you will need to complete main.cpp and complete 6 files (these are three sets of .h and matching .cpp files):

o Disk – This class will represent an individual Disk in the simulation

o Peg – This class will represent an individual Peg in the simulation

o Tower – These files contain

.    The ITP library uses pixels to measure all graphics. Therefore, almost everything on the screen is measured as whole numbers (or integers). Be sure to use integers when dealing with graphics and on screen objects.

.     Function headers are missing for this assignment. You must complete them for full style credit. You must also complete the function signatures with the variable names, based on how you code these functions.

.    While my demonstration shows several colors, this isn’t required for full credit. You may use a single color for all your disks and it will be considered correct.

.    There are no tests for the assignment. Your code will be graded based on its graphical output and the code itself.

Part 1: Disk class

.    We will be moving Disks around or window for this assignment. For our purposes, a Disk is just a rectangle.

.    Your Disk class must have at least the following member variables. You may store more data with each Disk, but the following list is required at a minimum:

o The Disks x and y coordinates. It is a GoodIdea™ to have coordinates be the bottom

center of the Disk. This will make centering different size Disks much easier. The size is in pixels.

o The width and height of the Disk, in pixels

o The color of the Disk (stored as a string). I suggest starting with a single color for all your disks – but you can eventually generate random colors if you like.

.    Your Disk class is to have at least the following member functions. You may have more, but this list is the minimum:

o A default constructor and a parameterized constructor that sets x, y, width, and height for the Disk.

o Setter functions for the x and y coordinates.

o Getter function for the height of a Disk.

o A draw function that accepts a GWindow (by reference). This function will use the

GWindow and the member variables to create the colored rectangles that represent your Disks.

.     It is a GoodIdea® to test your Disk class by creating a few Disks around the main window. Then call the draw function to have them drawn. Make sure your Disk class and draw function work properly before going to part 2. You do not need to keep this test code in main once you start  part 2.

Part 2: Peg class

.     Pegs are the other visual component of our simulation. A Peg consists of a thin, black, vertical rectangle with zero, or more Disks.

.    A Peg must have at least the following member variables. You may store more data with each Peg, but the following list is required at a minimum:

o Vector of Disks member variable which will contain all the Disk objects that are “on” that Peg.

o The Peg’s x and y coordinates. It is a GoodIdea© to have coordinates be the bottom center of the Peg. The Peg is a tall, skinny rectangle.

o The width and height of the Peg, in pixels

o The color of the Peg (stored as a string). I set all my peg colors to the same value “BLACK” .

.    Your Peg class is to have at least the following member functions. You may have more, but this list is the minimum:

o A default constructor and a parameterized constructor that sets the x, y, width, and height for the Peg.

o A draw function that draws the Peg and all of the Disks that are “on” that Peg. The Disks  are to be drawn centered on their Peg. To display the Peg, create the rectangle using the GWindow to represent the Peg. Then call the draw function for each Disk on the Peg

(using the items in the Disk Vector)

o An addDisk member function. This function takes a Disk object as input. The Disk object that is passed into this function is to be added at the end of the Vector (for

performance). This means that the first Disk in a Vector (at index 0) is the bottom Disk on that Peg. The Disk object that is last in the Vector is the top Disk on that Peg. It is a  GoodIdea™ to set the x and y of the incoming disk to be at the right coordinates when adding a Disk to a Peg.

o A removeDisk member function. This function is to remove the last Disk on that Peg and return it.

.    As with Part 1, it is highly recommended that you modify main to test your Peg class code.

Create a few Peg objects, add Disks to them, remove Disks from them, drawing your Peg objects after each change. Make sure your code works before continuing the next step.

Part 3 : Towers of Hanoi setup

.     Before we can implement the recursive solution, we must prompt the user for input and setup the objects. We will always have three Pegs, but the user can specify the number of Disks, as well as the starting and ending Pegs.

.     Inside of the Towers file, create the following functions:

o promptForDisks. This function uses std::cout to prompt the user for the number of Disks to start with. The valid range is 2 to 10 (inclusive) Disks – use the constants defined in towers.h. Anything else is to be rejected. Continue to prompt the user until they enter a valid number of Disks. Use std::cin to read user input. It will return the number of Disks  the user requested.

o promptForPegs. It receives 2 integers (by reference) as input. Using std::cout, prompt   the user for a starting Peg and ending Peg numbers. The valid values are 1, 2, or 3. You are to reject anything else. You are also to ensure that the starting and ending Peg numbers are not the same. Use std::cin to read user input. Store the starting Peg value in the 1st  input and the ending Peg value in the 2nd  input. The function returns nothing.

o promptForPause. This function uses std::cout to prompt the user for the number

milliseconds to pause between images in the animation. The valid range is 1 to 1000000 (inclusive) – use the constant defined in towers.h. Anything else is to be rejected.

Continue to prompt the user until they enter a valid number of milliseconds. Use std::cin to read user input. It will return the number entered by the user.

o promptForWindowSize. It receives 2 integers (by reference) as input. Using std::cout, prompt the user for a width and height for the graphics window. The range of valid values is defined as constants in the towers.h file. You are to reject anything else. Use std::cin to read user input. Store the width in the 1st  input and the height in the 2nd input. The function returns nothing.

o draw. It accepts a GWindow (by reference), the vector of Pegs (by reference), and an

integer. Use the clear function from GWindow to clear the graphics currently in the window. Then write your draw function to draw all the Pegs (and therefore all the Disks on the Pegs). Then use the pause function (with the last input) at the end of draw. This   can simulate animation, eventually. The function returns nothing.

.     Once you have read in all the user input, create the GWindow with the 3 Peg objects. It is a

GoodIdea© to store them in a Vector, as it makes drawing all of them easier than having three separate variable names.

.    Create the appropriate number of Disk objects and place them on the correct starting Peg.

.    Test your code before going to Part 4. Now your code in main will not be replaced in Part 4, so testing at this point isn’t “a waste of time”. It doesn’t matter if your recursive solution works if you can’t draw Pegs and Disks properly.

Part 4 : Implement the recursive solution

.    The key to solving this puzzle is to recognize that it can be solved by breaking the problem down into a collection of smaller problems and further breaking those problems down into even

smaller problems until a solution is reached. One description of the solution might be:

1.1.  Label the Pegs “start”, “temp”, “end” — these labels may change at different steps

1.2.  Let N be the total number of Disks

1.3.  Number the Disks from N-1 (smallest, topmost) to 0 (largest, bottommost) 1.4.  Move N Disks from “start” to “end” :

1.4.1.  Transfer N−1 Disks from “start” to “temp”. This leaves Disk 0 alone on “start”

1.4.2.   Move Disk 0 from “start” to “end”

1.4.3.  Transfer N−1 Disks from “temp” to “end” so they sit on Disk 0

.     Inside of Tower, create a moveDisk function that accepts the GWindow object (by reference),

the Peg collection (by reference), the starting Peg (represented with an int), the destination Peg (represented with an int), and the pause length (represented by an int). It must remove the top  most Disk from the start Peg, add it to the destination Peg, and then call the draw function.

.     Inside of Tower, create a towerSolver function. This function is to take six arguments: the

GWindow object (by reference), the Peg collection (by reference), the starting Peg (represented  with an int), the destination Peg (represented with an int), the number of disks to move, and the pause duration.

.    The towerSolver is to use recursion and the moveDisk function to recursively move all the Disks from the source Peg to the target Peg.

.     Remove your testing code from main and modify towerRun to call all the needed functions from Part 3 and Part 4 then call towerSolver one time in towerRun to start the recursive solution.

A Note on Style

Be sure to comment your code.

As we discussed in lecture, it is extremely important that your code is properly indented as it greatly  adds to readability. Because of this, if you submit a code file that is not reasonably indented, you will have points deducted.

Likewise, you will lose points if your variable names are not meaningful. Make sure you use variable names that correspond to what you are actually storing in the variables.

Sample output

A sample execution of the assignment, with 7 Disks with a start Peg of 1 and an end Peg of 3 might look like this. NOTE: For full credit, you do not have to color each disk a different color – but it’s nice to look  at this way, isn’t it?

Submission

You must push your code to the GitHub assignment to submit your solution.

Grading

Item Points

Total                                                                                        100