CMSC 201 Programming Project Four Hailstone Sequences 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 See this note for clarification. 4/21

The Objective

Consider the following problem:

Background

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.

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.

The Task

• 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 main menu.
  

  Menu specifications:

  • 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 to be:
    P to print a range of sequences to the screen
    H to print a range of sequences and their histogram to the screen
    W to write the sequences and their histogram to a file
    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 choice)

  • 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.
  

  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.

• 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.

Guarantees