This day's activities build a foundation for subsequent work with C++ in
Advanced Placement Computer Science (APCS) courses. You'll pick up the
syntactic differences in the control constructs (e.g., if, while)
between Pascal and C++ from almost any C++ text, but the use of classes
is something covered in varying degrees. To become comfortable with
classes and encapsulation of state and behavior, several classes will be
used during the lab and group work.
This document is meant be be read both as a stand-alone document and as a
hypertext document. Thus some of the code will be
accessible in an appendix to the material you receive, but will also be
immediately accessible by following links if the document is viewed
Classes and libraries used include:
- apstring The AP string class, based on the
standard C++ string class, declared in
apstring.h and implemented in
- apvector The AP vector/array class, a
safely indexable class, based on the standard C++/STL
(standard template library) vector class, declared in
apvector.h and implemented in
- Dice A class that encapsulates simple random
number generation (between 1 and the number of 'sides' on a
die), declared in dice.h and
implemented in dice.cpp.
- RandGen A class used by the Dice class, that
generates random integers and reals (int and double),
declared in rando.h and
implemented in the rando.cpp
- A standard library of functions to manipulate characters
declared in <ctype.h> (this library is
not part of the APCS subset.)
- A library of prompting functions declared in prompt.h and defined in prompt.cpp
Vectors, Strings, Dice, and C++
We'll discuss two programs as a springboard to the syntax and semantics
of C++. These two programs are:
a program to roll two
dice thousands of times and track the number of times each
for tracking how many times every alphabetic character occurs
in a text file.
Here's a run of the dicevec.cpp program:
how many rolls 10000
roll # of occurrences
Here is a run of letters.cpp
using a data file that stores The Scarlet Letter by Nathaniel
enter name of input file: data\hawthorne.txt
a 29380 7.6%
b 5672 1.5%
c 9571 2.5%
d 15972 4.2%
e 50853 13.2%
f 9317 2.4%
g 7091 1.8%
h 26624 6.9%
i 26445 6.9%
j 282 0.1%
k 2351 0.6%
l 16336 4.2%
m 10312 2.7%
n 25435 6.6%
o 27513 7.2%
p 6840 1.8%
q 337 0.1%
r 24075 6.3%
s 24265 6.3%
t 36509 9.5%
u 9861 2.6%
v 3680 1.0%
w 8839 2.3%
x 461 0.1%
y 6534 1.7%
z 152 0.0%
In small groups (size determined in real time at the workshop) you
should develop solutions to the following problems. You should work
these out on paper and raise questions as you have them. Some of the
problems are identified as show-me problems (pretend
you're from Missouri). Each group should write a solution to the
show-me problems on a transparency so that we can view the solutions as
a large group.
- Modify letters.cpp
so that a vector of 26 entries is used rather than a vector of
CHAR_MAX entries. Try to isolate dependencies on a
particular character set, e.g., ASCII, Unicode, etc.
- Modify letters.cpp
so that different word-lengths are tracked rather than
character occurrences. The output of the program should be
the number of 2 letter words, 3 letter words, etc.
to track how many times each sum occurs when three
twelve-sided dice are rolled. Try to design the program to
make it simple to change the number of sides and the number of
The goal in the morning lab activity is to become accustomed to using
projects in which the AP classes are used (only apstring and apvector).
Instructions for using projects with
Metrowerks and using projects with
Turbo 4.5 are provided as separate documents.
Because this first morning's lab may be short, we suggest picking a
small program to start with from among the group programs above
(suggestions are given below). An additional problem is also suggested.
- You should first use one of the project templates (see the
write-up for your system) to get the program dicevec.cpp running.
- When you've figured out how to make dicevec.cpp
run, modify the program to roll three 12-sided dice and print
the number of times each possible sum occurs.
- Change the program used in the project so that letters.cpp is the
active program. Run the program on poe.txt and
hawthorne.txt (both in the subdirectory
Modify the program so that it tracks both lower case
letters and upper case letters separately. Print the output
in a format like the one below (or use another format if you
enter name of input file: data/hawthorne.txt
a 28647 7.4% A 733 0.2%
b 5350 1.4% B 322 0.1%
c 9119 2.4% C 452 0.1%
d 15697 4.1% D 275 0.1%
e 49691 12.9% E 1162 0.3%
f 9212 2.4% F 105 0.0%
- In the dice game Yahtzee, five 6-sided dice are rolled (in
the actual game the player can re-roll some of the dice during
each "turn".) Write a program that simulates the rolling of
five six-sided dice and determines how many times all five dice
show the same number --- five of a kind --- in a large number of
rolls (entered by the user). Think (you don't write code, think
of how) about how you could modify the program to track how many
times 3 of a kind, 4 of a kind, and a full house (2 of one kind,
3 of another) occur in addition to five of a kind.
Random Walks, Dice, Classes, and C++
We'll go over any issues that came up from the morning lab session.
Then we'll begin to work on turning the random walk program frogwalk.cpp into a class-based
program. In addition to providing experience with classes, this will
let you modify the program to have several "frogs" walking randomly at
the same time. The group activities will center on language issues and
class issues (changing a program to be class-based).
The program frogwalk.cpp
simulates a one-dimensional random walk. The output is the final
position of a "frog" that takes n steps (where n is a
value entered by the user).
The class Frog is declared (the declaration is not complete) in
the header file frog.h.
Three member functions are
declared (in addition to the constructor) and no private instance
variables are included in the declaration.
- Modify frogwalk.cpp so that
instead of walking for a fixed number of steps, the user is
prompted for a distance from the origin. The frog
should walk until it is that distance from the origin (in
either the positive or negative direction). The output of the
program is the total number of steps taken by the frog.
- Track how many times all locations from -15 to +15 are
visited, and use two extra variables to represent negative and
positive infinity (all locations less than -15 and greater than
+15, respectively.) Think about how you'd modify the program to
track all locations, not just those in the range [-15 .. 15].
When the random walk is finished, print/graph/output the
number of times each location is visited.
- Using the class Frog declared in frog.h, decide what
additional member functions (if any) are needed and what private
variables are needed to implement the member functions. You
should think about how the Frog class will be used in programs.
At the very least, it should be possible to have two Frog
objects "walking" in one program, with the program tracking how
many times the frogs occupy the same location during the walk.
The member functions you specify will depend to a large extent
on how you envision the Frog class being used. You should also
think about what modifications are needed to have a Frog class
that walks in two dimensions (x and y) but that is restricted to
staying on lattice points, i.e., points with integer
You may design a basic Frog class that can be extended for
particular frog "experiments". You might consider, for example,
how a frog could be constrained to engage in a random walk in
the range [-N..N], and walk until all 2N+1 locations have been
visited, reporting the time needed until this happens.
public and private member functions and private/instance
variables for a complete Frog class. Provide
the implementation of member function Frog::TakeTurn
that tracks at least the locations in the range [-N..N] (for
some constant N) visited by a Frog object.
As a first step, implement your frog class by creating a frog.h
header file and a frog.cpp implementation file (make sure that
frog.cpp is in your project.) You can include a main
function in frog.cpp as a first step, but you'll need to create
a separate file/program at some point so that frog.cpp consists
only of member functions of the class Frog. However,
for many of the problems below, it will be easier to include the Frog
member functions and main (and supporting functions) in the
Your Frog class may have more functionality than needed to work on the
problems below. Please feel free to embellish these exercises using
your fertile imagination. No order is implied after the first of the
programs outlined below, you can implement those that seem intriguing or
- Write a program that creates two frog objects, both of
which walk for some specified number of steps. The output of
the program should be the final position of both frogs and the
number times the two frogs occupy the same position.
- Write a program that creates three frogs and tracks how
many times all three frogs occupy the same location as well as
how many times two frogs occupy the same location.
- Modify the Frog class and write supporting functions to
derive a relationship for how many steps are needed for
one frog to visit all
2n+1 locations where a walk is constrained to take place in the
range [-n .. n] on the x-axis. When a frog hits an endpoint
(-n or n) you should try a few alternatives and see if the
different behavior affects the relationship you derive from
- A frog at an endpoint steps around to the other end as
needed, e.g., the walk is a circle with 2n+1 points on the
circle (think how integers wrap from INT_MIN to
- A frog at an endpoint always moves in the other
direction (away from the endpoint) when taking a step.
- A frog either moves back (away from the endpoint) or
stays where it is, with equal probability.
- Repeat the previous experiments, but for two-dimensional
walking frogs where the frogs are constrained to walk on a
square (2N+1) x (2N+1) grid, e.g., x and y coordinates might be
restricted to be between -10 and 10 for a 21 x 21 grid. Use
one (or all three) of the options in the previous problem for
when a frog reaches an "edge" of the world. You'll probably
want to use the apmatrix.h class.
- Write the results of a one, two, or three frog walk to a
file in a format that can be easily graphed using Excel (or
some other spreadsheet). Generate colorful and illuminating
(both physically and intellectually) graphs for the walk.
These exercises are programming problems that may require extra time to
- Write a program to play a non-graphical, interactive
version of the word-game hangman. The user should guess a word
"picked" by the computer. You can start by storing a few words
as constants in an array initialized when the program is run,
or read words from a file (or just use one word to get the
program running, then add more words).
- Write a program (using a class-based or non-class based)
approach to solve the flatworld problem from the
internet programming contest. A
description of flatworld is accessible. You'll want to
develop your own test files, but you an also test and verify
with the files used in the internet contest.
- flat.dat the data file
- flat.out the output file for
Owen L. Astrachan
Last modified: Thu Jun 12 09:44:54 EDT