UMBC CMSC 201 Spring '07 CSEE | 201 | 201 S'07 | lectures | news | help |

The design document |

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., when the value is 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 '*3*n*+1
conjecture*', the Ulam conjecture, and the Syracuse problem. The sequence
is also commonly called the* hailstone sequence*.

John
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
found. Paul
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 between
1, MIN, and 9999, MAX, and your program will generate that number's
hailstone sequence.
- You will be using a menu system in your program to allow
the user to choose whether to:
**I**- view the hailstone sequence for an**I**ndividual value on the screen,**R**- view the sequences for a**R**ange of values on the screen,**H**- view the sequences for a range of values and their**H**istogram on the screen,**W**-**W**rite the sequences for a range of values and their histogram to a file, or**Q**-**Q**uit the program.**Further Menu Specifications:**- The menu must use the letters
**I, R, H, W**and**Q**for its choices. The user should be allowed to enter either the upper-case or lower-case versions of these letters. Other letters should be rejected and the user prompted for a new choice. - All menu choices except
**I**and**Q**deal with ranges of values. A range of values must be consecutive integers and must consist of at least 2 values. The beginning number of the range must be less than the ending number of the range. We are limiting a range to be no more that 13 values. For example, a range of values where the beginning value is 5 and the ending value is 7, contains three values: 5, 6, and 7. A range that has a beginning value of 400 and an ending value of 412 is allowed because there are 13 values in that range. A range of 400 to 413 would have too many values in it. **HINT:**Since you are using a menu 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 choice)

- The menu must use the letters

- 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. This can be accomplished
by keeping track of the number of times the function was called.
You
**must**use the following function prototype for this function:

#### void Hailstones ( FILE* stream, int num, int* timesPtr ) ;

- 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 that range as Hailstones() is being called. This can be done easily by dynamically allocating an array of structures of type HAIL, where each HAIL structure contains a value and the length of its sequence. After the Histogram() function finishes using the information in that array, it should be free()ed. Further specifications for the array of HAIL structures:
- You must use a dynamically allocated array to store the structs holding the values and the sequence lengths when printing a histogram. We want to give you some experience in dynamic memory allocation and use. While it's true that the ranges will be 13 or less and you therefore *could* use a preallocated array of length 13, you will not be allowed to do it this way. So for each range of values, you must allocate memory for an array of HAIL structures the exact size needed for the number of values in that range. You must also free the memory after it is no longer needed.
**NOTE**: We suggest that the array be an array of HAIL structures where each one holds two integers: a value and a sequence length. You can use a different design if you want, but you must use a dynamically allocated array just big enough for the current range.- You must 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. Some sample code that prints an
unscaled histogram can be found in the lecture notes: dice.c in Lecture 7.

**Scaling**- 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.

- 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
- 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 9999 must be named hail9988to9999.out. Obviously, your program must compose the filename using string manipulations and functions.

We want to give you a chance to use some of the string manipulation functions (e.g., strcat and friends). Recall what the problem is: given two integers for a range, say 9 and 18, construct the string**hail9to18.out**You can use strcat to concatenate strings, but how do you get the string "18" from the integer 18? You will have to write a function that takes an integer and returns a string of the digits that are in that integer.

**Hint**: You can get the right-most digit of integer**n**via (**n**% 10). You can map that to the appropriate string (e.g., "4") in any of several ways (ascii values of digits might be helpful). You can then extract that digit by dividing**n**by 10. This method can be repeated until the number,**n**, becomes 0.**System calls for renaming files are NOT ALLOWED****Do not use sprintf to construct the file name.**

- 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 appropriately. Make sure that you submit all files that are necessary for compilation, including all of your .h files.

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**

CSEE | 201 | 201 S'07 | lectures | news | resources | help | Tuesday, 17-Apr-2007 15:49:09 EDT