CMSC 201 Programming Project Four Hailstone Sequences Out: Monday 4/16/07 Due Date: Sunday 4/29/07, before midnight The design document for this project, design4.txt, is due: Before Midnight, Sunday 4/22/07

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 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 Individual value on the screen,
  • R - view the sequences for a Range of values on the screen,
  • H - view the sequences for a range of values and their Histogram on the screen,
  • W - Write the sequences for a range of values and their histogram to a file, or
  • Q - Quit 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)

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

Guarantees