Programming Project Four
Out: Saturday 4/16/05
Due Date: Friday 4/29/05, before midnight
The design document for this project, design4.txt, is due:
Before Midnight, Friday 4/22/05
note for clarification. 4/21
The purpose of this assignment is to give you practice with
recursion, strings and chars, allocating memory dynamically,
and writing to files.
Consider the following problem:
Choose a positive integer and repeatedly
do the following: if the number is 1, quit; if the number is even, cut
it in half; and if the number is odd, multiply it by 3 and add 1. For
example, if you start with the number 17, you get the sequence: 17
52 26 13 40 20 10 5 16 8 4 2 1. Generate the sequence from a starting
number and you'll find the numbers go up and down like a hailstone in
a cloud before it plummets to earth (e.g., one).
Does this procedure eventually reach 1 and stop for every choice
of starting number? So far, this is an unsolved problem -- no one has
yet proved that the process always results in 1, and no one has yet found
a counterexample. This problem was first posed by L. Collatz in 1937 and
goes under several names: the Collatz conjecture, the '3n+1
conjecture', the Ulam conjecture, and the Syracuse problem. The sequence
is also commonly called the hailstone sequence.
Conway proved that the original Collatz problem has no nontrivial
cycles of length less than 400. Lagarias (1985)
showed that there are no nontrivial cycles with length less than 275,000.
Conway (1972) also proved that Collatz-type problems can be formally undecidable.
The conjecture has been check by computer for all start values up to 1.2
× 10**12, but a proof of the conjecture has not been
Erdös said about the Collatz conjecture: "Mathematics is not
yet ready for such problems." He offered $500 for its solution. There
are some heuristic, statistical arguments supporting the conjecture: if
one considers only the odd numbers in the sequence generated
by the Collatz process, then one can argue that on average the next odd
number should be about 3/4 of the previous one, which suggests that they
eventually hit the bottom.
- You are to write a program that will allow the user to explore
hailstone sequences. S/he may enter any positive integer within the
range of 1, MIN, to 10000, MAX, and your program will generate that
number's hailstone sequence.
- You will be using a two-level menu system in your program to first
allow the user to choose whether to view the hailstone sequence for
an individual value, a range of values, or to quit the program.
If the user is interested in viewing the hailstones for a range
of values, a second menu is presented that will allow the user
to choose to: view the hailstone sequences on the screen,
view the sequences and a histogram of those sequences on the screen,
write the sequences and their histogram to a file, or return to the
- The 1st-level menu must use the letters S, R and Q for
its choices, where S stands for Single Sequence, R stands for
a Range of Sequences and Q is for Quit. The user should be
allowed to enter either the upper-case or lower-case versions
of these letters. Other letters should be rejected.
- The 2nd-level menu displays a menu of choices that deal
with a range of sequences. As with the 1st-level menu, you are
REQUIRED to use single-character input, and the choices are
P to print a range of sequences to the screen
H to print a range of sequences and their histogram to
W to write the sequences and their histogram to a
M to return to the main menu
This menu must accept both lower and upper case entries of
these letters and reject all others.
- HINT:Since you are using menus that must accept
character input, you must make sure that you have read all
of the characters from stdin before trying to read the
character the user has just entered. (this means the newline
character the user has entered after entering digits
as well as the newline character entered after each character
- Obviously, after the user has chosen from the 2nd-level menu,
you should perform the necessary operation and report the
result and again display the 2nd-level menu until the user
chooses M or m, which returns him to the 1st-level menu. At
that time the user may choose another sequence or range of
sequences to examine or choose Q or q to end the program.
- You must have a recursive function called Hailstones() which will print
the hailstone sequence for a value passed in. It must work recursively
by calling itself with different arguments each time. Since this
function will have to write either to the screen or to a file, it
should take a stream as one of its arguments. Since it is also
important for the sequence to be readable in an 80-character wide
screen (standard width), you should use print formatting to allow a
fixed number of values per line where each value is displayed in a
fixed-width field. See the sample output. This function must also
determine how many values are in a sequence.
- If the user has chosen an option that must print a histogram, whether
it be to the screen or to a file, then you must capture the length of
each sequence in the range as Hailstones() is being called. This can be
done easily by dynamically allocating an array of HAIL structures,
where each HAIL contains the value and the length of its sequence.
After the Histogram() function finishes using the information in that
array, it should be freed.
- You must also have a function, Histogram(), that will print the
histogram for a range of values. It should take an array of HAIL
structures described above as one of its arguments.
- Width - Since this histogram must be labelled with the values at
the bottom and each of the values can be as many as 4 digits wide, you
will only be able to fit 13 values on a histogram. For that reason, you
must restrict the user to a range of no more than 13 values
(determined by the 80-char width of a standard screen).
- Height - When viewing a histogram, the entire histogram must fit
on the screen. The height of a screen will allow us to print as many as
25 stars vertically and still have room for the title and scaling
information above it and the value labels beneath it. Since some values
have very long sequences, if we printed one star for each value in the
sequence, our histogram would be many pages tall. For that reason, your
histograms must be scaled.
(HINT: When plotting a histogram for a range of values, you should first
determine which of the sequences in that range is the longest. Then
you should determine how many terms of the sequence one star should
represent. For example, if the longest sequence in the range of sequences
is 114, then each star should represent 5 values in the sequence and the
scaling is then 5 to 1.
- If you open a file for writing, then you must also close it. You
should do this as soon as you are finished writing to it.
- Filename -
Since when running the program, a user may actually generate several
output files, each for a different range of values, each of the files
must be named to indicate the range of values it contains. Specifically,
a file that contains the sequences and histogram for the values 20 through
27 must be named hail20to27.out and a file containing the
range 9988 through 10000 must be named hail9988to10000.out. Obviously,
your program must compose the filename using string manipulations and
functions. System calls for renaming files are NOT ALLOWED
- You must use separate compilation for this project. You must have a
file called proj4.c which contains main(). You may have as many .c and .h
files as you see fit for a good design. Name them appropriatly. Make
sure that you submit all files that are necessary for compilation, including
all of your .h files.
We guarantee that the graders will enter only integers as their response
to prompts for values and only single characters as response to the menus.
Here is a link to the sample output of this
Submitting the Program
To submit your program, type the following command at the Unix prompt
submit cs201 Proj4 followed by the .c and .h files necessary for compilation
To verify that your project was submitted, you can execute the
following command at the Unix prompt. It will show all files that
you submitted in a format similar to the Unix 'ls' command.
submitls cs201 Proj4