Introduction
============
In this lab we will be working with arrays. In the guided part, you
will be implementing an array sort of your choice. In the self lab
part you will be modifying the tower of Hanoi problem. The guided
lab is pretty easy, as you just have to translate a little
pseudocode into C++. The second part will seem very simple, however,
you have to do a fair bit of thinking and design to make it work.
This is one of those "easy" problems that have lots of details, so
take your time and be careful. Most of all, as always, have fun
getting the machines to do your bidding!
Lab 7.1 (Guided) Counting Sheep
===============================
Having discovered how to count numbers and convert currency the
world over, Reg and Stan have become fabulously wealthy. Not only
have they managed to turn the patent settlement with Rome into the
largest Etruscan sheep farm ever seen before or since, but they have
also made many friends and enemies throughout the whole ancient
world. Realizing that the Italian peninsula does not have enough
need of sheep to sustain their vast fields, they have decided to
branch out, and ship sheep with ships to foreign shores. (Try to
say that 3 times fast!) However, they have hit a bit of a problem.
"Stan, I am having trouble determining the best order to send the
sheep out in." Reg lamented one day. "We have dozens of orders
leaving every day, and they are too vast to juggle around. Not to
mention that the crates are very heavy!"
"Hmmm..." Stan though. "Perhaps we should hand this off to the
boffins* down in the CS department."
"That sounds like a great idea! Maybe they'll have a way of
correctly sorting large lists of data!"
When Reg and Stan presented the problem to their crack team of
computer scientists (a group who was about 2500 years ahead of their
time), they decided that what Reg and Stan needed was a way to
sort orders by country and due date. They decided that they would
have to have some way to store an entire order, but that no such
method had been developed yet.
"Hey Stan, do you get the feeling we'll be showing up in a later
lab?" Reg asked. "Indeed I do!" said Stan.
So now, the CS department (that's you) set out to work on Stan and
Reg's problem. Because they didn't yet know how to store a whole
sheep in a computer, they decided instead to store a sequence number
and then sort those numbers. The idea being that if they develop
the sorting technique, they will then be able to apply it once they
know how to store complex objects.
* Note: "Boffin" is part of Anglican slang, and Reg and Stan are
modern British people who somehow live in ancient Tuscany. Look up
the meaning of "boffin" and amuse your friends!
Procedure
=========
We are going to develop a simple program that allows the user to
enter 20 items into an array. The program will then sort the items
and then print the sorted list. A skeleton of the code is provided
below:
--- begin array.cpp ---
#include <iostream>
#include "arrayFun.h"
using namespace std;
void sort(int ar[], int n);
int main(void) {
int ar[20];
int i;
//read in the values
cout << "Enter 20 values." << endl;
for(i=0; i<20; i++) {
cin >> ar[i];
}
//sort the values
sort(ar, 20);
//print the array
cout << endl << "The sorted array." << endl;
printArray(ar, 20);
return 0;
}
void sort(int ar[], int n) {
/* TODO: Write Sort */
}
--- end array.cpp ---
Clearly, a key piece is missing. Namely, we are not yet sorting
anything. So here's what I want you to do:
1. Copy the arrayFun.h and arrayFun.cpp files which we developed in
class into your working folder. These are in my home directory,
just do:
cp ~relowe/arrayFun.* .
To get them. If you typed along with me on Monday's class, you
already have them.
2. Enter the array.cpp code exactly as it is above.
3. Compile the program. You can either write a makefile or you can
just do the single line:
g++ -o array array.cpp arrayFun.cpp
4. Implement your favorite sort algorithm in the sort function,
replacing my "todo" comment. The pseudocode used in class is on
D2L, or you are welcome to look up and use other algorithms if
you are feeling adventurous. If you want to produce more than
one version of this program, I'll add some extra credit to your
lab 6.2 score! (you'll want to list multiple array.cpp files in
your turnin script file.)
5. Generate your script file showing a listing of array.cpp, your
compile line, and a single test.
Lab 7.2 (Self) Ending the World
===============================
In the far east, within the capital city of Vietnam stands the tower
of Hanoi. Within this tower monks work endlessly on a puzzle moving
golden disks between 3 pegs. When they started, the first peg
contained 64 golden disks. Each disk is of a unique size, and they
move them so that a large disk is never placed on a smaller disk.
They only move one at a time, and when they place the last disk on
the last peg, the world will end.
Ok, so as we discussed this story isn't real. There aren't any
Vietnamese monks counting down to the Earth's destruction, and even
if there were, solving this puzzle with 64 disks would take a
considerable amount of time. The puzzle was really created by a
French mathematician in the late 19th century, and whenever it was
published, it was given a tale of some far off exotic place where
an extreme version of the puzzle was being solved. Over the years,
Hanoi has emerged as the most likely place for the mythical tower,
and so we now know this problem as "The Tower of Hanoi". To refresh
your memory, here is the solution we discussed in class.
Suppose we start the puzzle with the following configuration:
| | |
# | |
### | |
##### | |
####### | |
A B C
Remember the basic strategy to move 4 disks to peg c is to first
move 3 to B, then 1 to C, then move 3 from B to C. This problem
was our demonstration of recursive thinking, and we wound up with
the following code:
-- Begin hanoi.cpp --
#include <iostream>
#include <cmath>
Note that I have modified it slightly so that instead of getting the
puzzle size from the user, it is statically defined to be 4. The
reason for this is we have not yet looked at how to dynamically
allocate an array, and so we're going to be modifying this program
to work with a fixed size puzzle.
Now, what your task is is to modify this program so that it draws
the board after each move. For instance, suppose we had the above
problem. The first move it makes is it moves 1 disk from A to C.
Thus the first move would look like this:
(A, C)
| | |
| | |
### | |
##### | |
####### | #
A B C
In order to this, you will need to keep track of the whereabouts of
all the disks in the puzzle. My setup does this by using 3 arrays,
one for each post, with 4 elements. These elements represent the
disk numbers which are on the post. So you can solve this using 3
arrays of integers. (Though that is certainly not the only way to
do it.)
You should design your code to neatly draw the posts and the disks.
I see a fair bit of iomanip in your future, but really aside from
setting widths and centering, it's really pretty simple. The hard
part will be in figuring out how to move the disks around. I
recommend that you implement a "moveDisk" function which does this,
as it will make your code easier to deal with. I also recommend
that you create a "printBoard" function to print based on your
arrays. You will also want to create an "initializeBoard" function
which initializes the arrays to the starting position of the
puzzle. Finally, you will need to modify the solve function to
accept your arrays as parameters, and use them when it actually
makes a move. Recall that the cout line is where the move is
actually made. This will be where you use your moveDisk and
printBoard functions.
The key to this program is having a good design. I will be
weighting the pseudocode more heavily this time, as I believe it
will take a fair bit of contemplation to get right. The pseudocode
will be worth 40% of the lab grade. In your psuedocode, I want to
see the following:
- How you plan to represent your posts. Remember there are 5
possibilities at each post position (one of the 4 disks, or an
empty spot).
- A design for your modified solve function.
- The design for your printBoard function.
- The design for your moveDisk function
- The design for your initializeBoard function
HINTS
- Modular decomposition is key to getting this program to work.
- Look at setw and how to center fields in the iomanip
documentation.
- You will not have to change the logic of solve, you will only be
adding to the function.
- Disks are easier to center if they have an odd number of
characters. Take a look at my disks above.
- I want you to think about this problem very hard as you design
it. Don't over think it though. Try working at a nice calm
pace, and if you get stuck, look at something else for a little
while. I am looking for the most elegant solution you can
create, and that means detailed pseudocode, and lots of time
spent in deep contemplation of the arrays on your board.
Extra Credit
------------
If you read ahead and figure out how to make a dynamically allocated
array, then you can write this program in a way that can accept any
number of disks. If you do this, then I will give you 10 points
extra credit. Note that this is tricky, and it has a far reaching
effect on your rendering and initialization functions. Get the
official lab done first, then do the challenge.
