Computer Science 2530
Fall 2019
Programming Assignment 2

Assigned: Wednesday, September 11
Due: Friday, September 20, 11:59pm
Points: 400

Table of Contents

  1. Purpose of this assignment
  2. What you will submit
  3. Background
  4. The assignment
  5. Additional requirements
  6. A function that you can use
  7. A refinement plan
  8. Compiling and running your program on xlogin
  9. Issues to be aware of
  10. Submitting your work
  11. Late submissions
  12. Asking questions

Purpose of This Assignment

This assignment is intended to give you experience with functions that use loops.


What You Will Submit

You will need to submit one file called hailstone.cpp.

Read the entire assignment before you start working on it. Be sure to follow the instructions.


Background

Given any positive integer n, the hailstone sequence starting at n is obtained as follows. You write a sequence of numbers, one after another. Start by writing n. If n is even, then the next number is n/2. If n is odd, then the next number is 3n + 1. Continue in this way until you write the number 1.

For example, if you start at 7, then the next number is 22 (3 × 7 + 1). The next number after 22 is 11.


The Assignment

Write and test a C++ program that reads a number n from the standard input (after giving a suitable prompt) and then writes the following information on the standard output:

  1. the entire hailstone sequence starting at n, all on one line, with the numbers separated by spaces;

  2. the length of the hailstone sequence that starts with n;

  3. the largest number in the hailstone sequence that starts with n;

  4. an indication of whether the hailstone sequence that starts with n contains a number that is greater than 1000.

  5. the length of the longest hailstone sequence that starts with a number from 1 to n;

  6. the starting number of the longest hailstone sequence that starts with a number from 1 to n;

  7. the largest number that occurs in any hailstone sequence that starts with a number from 1 to n.

  8. the start value, from 1 to n, of the hailstone sequence that contains largest number reported in the previous step.

The output needs to be sensible and easy to read, not just numbers. It must follow the general template below, with all numeric results lined up (approximately) vertically. Each part of the output should be on a separate line. Parts in black are written by the program. Parts in blue are typed by the user. 

  What number shall I start with?  7
  The hailstone sequence starting at 7 is:
  7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
  Sequence length:                                      17
  Largest number:                                       52
  Contains a number >1000?                              no
  Greatest length starting with 1 to 7:                 17
  Start value of sequence of length 17:                  7
  Largest value in a sequence starting with 1 to 7:     52
  Start value of sequence containing 52:                 7

Here some more examples. In the last one, the sequence is long, and lines have been broken to make it more readable. Your program should show it all on one line. 

  What number shall I start with?  1
  The hailstone sequence starting at 1 is:
  1
  Sequence length:                                       1
  Largest number:                                        1
  Contains a number >1000?                              no
  Greatest length starting with 1 to 1:                  1
  Start value of sequence of length 1:                   1
  Largest value in a sequence starting with 1 to 1:      1
  Start value of sequence containing 1:                  1

  What number shall I start with?  8
  The hailstone sequence starting at 8 is:
  8 4 2 1
  Sequence length:                                       4
  Largest number:                                        8
  Contains a number >1000?                              no
  Greatest length starting with 1 to 8:                 17
  Start value of sequence of length 17:                  7
  Largest value in a sequence starting with 1 to 8:     52
  Start value of sequence containing 52:                 7

  What number shall I start with?  27
  The hailstone sequence starting at 27 is:
  27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137
  412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445
  1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438
  719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154
  3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184
  92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
  Sequence length:                                     112
  Largest number:                                     9232
  Contains a number >1000?                             yes
  Greatest length starting with 1 to 27:               112
  Start value of sequence of length 112:                27
  Largest value in a sequence starting with 1 to 27:  9232
  Start value of sequence containing 9232:              27

Additional Requirements

It is important that you follow the instructions. Define exactly the functions that are listed in the next section. Do not try to improve on the design described here. Do not add extra responsibilities to functions.

For this program, use loops. Do not use recursion. Use type int for all of the integers. Do not use any of

for this assignment. The main function must not contain any loops. You can use the <cstdio>, <iostream> and <algorithm> libraries for this assignment.

All of the functions take exactly one parameter. If you write a function that does not take exactly one parameter of type int, other than a helper function that is not one of the required functions, then you will receive no credit for that function.

A program that wholly ignores the instructions will receive a grade of 0, even if it works correctly.


A Function That You Can Use

You might find the following function useful. You can include it in your program provided you also include its contract. The provision that you must not use recursion does not apply to this function. 

// numDigits(n) returns the number of decimal digits
// needed to write down n.  For example, numDigits(2) = 1,
// numDigits(53) = 2 and numDigits(7700) = 4.

int numDigits(int n)
{
  if(n < 10)
  {
    return 1;
  }
  else
  {
    return 1 + numDigits(n/10);
  }
}

A Refinement Plan

Create a directory to hold assignment 2. Download

into that directory.

Development plan
1. Use an editor to open a new file.

Copy and paste the template into it, and save it as hailstone.cpp.

Edit the hailstone.cpp. Add your name and the assignment number. The file is hailstone.cpp If you will use tabs, say how far apart the tab stops are. Even if you don't think that you will use tabs, it is a good idea to say how far apart they are, since many past students who have said that they do not use tabs have used them anyway.


2. Write a comment saying what the program will do when it is finished.

After the tabs line and a blank line, write a comment that clearly tells the following.

  1. Say what the program reads and where the input comes from (the standard input). Give a name (such as n) to the number that is read and refer to it as n wherever you refer to it.

  2. Say what information the program writes and where it writes to (the standard output). Use a numbered list of things to make your comment easy to read. You can take a sample from the assignment if that is helpful. But just showing an example without any discussion is not adequate.

Do not try to define what a hailstone sequence is. Assume that the reader knows that term. Use term "hailstone sequence" to make it clear what your program does. Don't talk about "the sequence" or "a sequence."

If you copy and paste from a browser, it will replace some symbols with sequences of special characters that do not belong in a program. Proofread your comment and make sure that it is readable. Check spelling and punctuation. Use complete sentences, except where you list things that the program shows. You can always use sensible lists.


3. Add a contract and heading for function next.

Copy the following contract and heading for function next(n) into your program. 

  // Next(n) returns the number that follows n
  // in a hailstone sequence.  For example, 
  // next(7) = 22 and next(8) = 4.
  //
  // Next requires n > 1, since there is no number
  // that follows 1.

  int next(int n)

4. Write a C++ definition of next.

The C++ definition is called the implementation of the function. Make sure the implementation is faithful to the contract. Function next must not read or write anything.

Be sure that the body of next does not change the value of n. The standards for this course require that no function changes the value of a (call-by-value) parameter. (All of the parameters in this assignment are call-by-value parameters.)

Function next is an expert on how to get the number that follows n in a hailstone sequence. If any function other than next needs to get the next number in a hailstone sequence, it must use next to get that next number.


5. Write a main function.

Write a main function that just reads an integer n and shows the value of next(n), so that you can test next.

Test your program on a few values to make sure that next works. Make sure that your tests include an even input and an odd input so that, taken together, your tests make use of every line of code that you have written.


6. Write a function that writes the entire hailstone sequence.

Write a heading and a contract for a function that takes an integer n and writes the entire hailstone sequence starting at n, all on one line, with the numbers separated by spaces. The heading must be 

  void writeHS(int n)

The contract should not explain information that is clear by looking at the heading. Don't say that writeHS takes a parameter n of type int. Don't say that writeHS does not return a value. Give useful information about what writeHS accomplishes.


7. Implement writeHS.

Make the function definition be faithful to the contract. WriteHS must not read anything from the standard input.


8. Modify main.

Make main no longer show next(n), but instead show the hailstone sequence starting at n. Be sure to label the hailstone sequence by what it is. Never write raw numbers.

Test your program on a few different values of n. Do not move on until this part works. See testing, below, for an automated tester.


9. Write a function that finds the length of a hailstone sequence.

Write a heading and contract, then the body, of a function that takes an integer n and returns the length of the hailstone sequence starting at n. The heading must be as follows. 

  int lengthHS(int n)

Function lengthHS must not read or write anything.


10. Modify main.

Make main write both the hailstone sequence and the length of the hailstone sequence starting at n.

Test your program on a few different starting values n before moving on. Make sure that the results are correct. If it does not work, fix it. Use the testingautomated tester.


11. Write a function that returns the largest value in a hailstone sequence.

Write a heading and contract, then the body, of a function that takes exactly one parameter, an integer n, and returns the largest value in the hailstone sequence starting at n. The heading must be as follows. 

  int largestInHS(int n)

This function must not read or write anything.

Modify your main function so that it also shows the largest value in the sequence. Test your program.


12. Write a function that tells whether a hailstone sequence contains a number that is greater than 1000.

Write a contract, then an implementation, of a function that takes exactly one parameter, an integer n, and returns true if the hailstone sequence starting with n contains a number that is greater than 1000, and returns false otherwise. The heading must be as follows. 

  bool bigHailstone(int n)

This function must not read or write anything.

Your algorithm for bigHailstone must be a search algorithm. As soon as it sees a number that is greater than 1000, bigHailstone must return true without looking at any more numbers in the hailstone sequence starting with n.

Modify your main function so that it also shows whether there is a number that is greater than 1000. Test your program.


13. Write a function that returns the length of the longest hailstone sequence starting with a number from 1 to n.

Write a heading and contract, then an implementation, of a function that takes exactly one parameter, an integer n, and returns the length of the longest hailstone sequence starting at a number from 1 to n. The heading must be 

  int longestHS(int n)

This function must not read or write anything.

Do not duplicate code to find the length of a hailstone sequence. Use lengthHS to compute the length of a hailstone sequence.

Modify your main function so that it also shows the result of the length of the longest sequence starting with a value from 1 to n. Test it.


14. Write a function that returns the start value of a longest hailstone sequence starting with a number from 1 to n.

Write a heading and contract, then the body, of a function that takes exactly one parameter, an integer n, and returns the start value of the longest hailstone sequence that starts on a value from 1 to n. The heading must be 

  int startOfLongestHS(int n)

This function must not read or write anything.

You might be tempted to combine this with the previous function. Do not do that. Write a separate function.

Modify your main function so that it also shows the result of this function. Test your program.


15. Write a function that returns the largest value that occurs in a hailstone sequence that starts with a number from 1 to n.

Write a contract, then an implementation, of a function that takes exactly one parameter, an integer n, and returns the largest value that occurs in a hailstone sequence that starts with a number from 1 to n. The heading must be 

  int largestInAnyHS(int n)

This function must not read or write anything.

Do not duplicate code to find the largest value in a hailstone sequence. Use largestInHS.

Modify your main function so that it also shows the result of this function. Test your program.


16. Write a function that returns the start value of a hailstone sequence that contains the largest value that was reported by largestInAnyHS(n).

Write a contract, then an implementation, of a function that takes exactly one parameter, an integer n, and returns the start value from 1 to n of the hailstone sequence that contains the largest value. The heading must be 

  int startHSWithLargest(int n)

This function must not read or write anything.

Do not duplicate code to find the largest value in a hailstone sequence. Use largestInHS.

Modify your main function so that it also shows the result of this function. Test your program.


17. Check your program.

Proofread your contracts. Look for spelling and grammatical errors. Ensure that you have followed the standards.


18. Submit your work.

Compiling and Testing Your Program

If you haven't already, get files Makefile and dotest and put them in the same directory as your program. Be sure that Makefile is called Makefile, not Makefile.txt or Makefile.cpp or MAKEFILE. Do command 

  ls
and check that Makefile and dotest are listed. Then you can use the following commands in a terminal window.

make
Compile hailstone.cpp and create an executable file called hailstone.

make run
Run executable file hailstone (compiling it first if it needs compiling).

make debug
Compile hailstone.cpp (if necessary), creating executable file hailstone. Run hailstone via the gdb debugger.

make test
Compile hailstone.cpp (if necessary), creating executable file hailstone. Run hailstone on some sample inputs that are provided. This does automated testing.

Note. To write the output from the tester into file testout.txt, use command 

  make test > testout.txt
Then you can look at the test results using a text editor.

make clean
Remove all machine-generated files. After you do this, the next time you do a make, hailstone.cpp will be recompiled.

Issues to Be Aware of

The program is required to follow the coding standards for this course. Pay attention to the following.

  1. Do not ignore compiler warnings. If you do not understand what a warning means, ask about it. Sending the text of the warning to Google will often give an explanation.

  2. Indent well throughout. A very poorly indented program will receive a failing score.

  3. Each function can have at most one loop in its body.

  4. No function body (not counting the heading) should have more than 16 noncomment lines. For this assignment, you can have slightly more than that in main.

  5. A function body must not change the value of a parameter. Pay attention to this one. In the past, many students have violated this requirement. If a function has a parameter called n, do not change the value of n anywhere in the function body.

  6. Do not have unnecessary special cases. If the general case works for n = 1, don't add a special case for n = 1.

  7. Pay attention to contracts. Documentation matters. Make sure that each function does what its contract says it does. If a function returns an integer, do not say that it returns a sequence. Mean what you say. Refer to the parameter by its name, not as "the number" or any similar phrase.

    Put a blank line before and after each function contract.

    Do not explain information that is clear in the heading.

  8. Two kinds of integers that this program uses are:

    1. integers that are start-values or members of hailstone sequences, and

    2. integers that are lengths of hailstone sequences.

    It makes no sense to compare a sequence member to a sequence length. It makes no sense to return a sequence length from a function that is supposed to return a sequence member or start-value.

    If a variable is a sequence member, make sure that you know that. If a variable is a sequence length, make sure that you know that too. Choosing variable names wisely can help. For example, include word length in each variable that is a sequence length.


Submitting Your Work

You must submit your program using the following method. Email submissions will not be accepted. An excuse that you do not know how to use Linux will not be accepted.

To turn in assignment 2, log into xlogin and change your directory to the one that holds assignment 2. Do the following command. 

  ~abrahamsonk/2530/bin/submit 2 hailstone.cpp
After submitting, you should receive confirmation that the submission was successful. If you do not receive confirmation, assume that the submission did not work. Command 
  ~abrahamsonk/2530/bin/submit 2
will show you what you have submitted for assignment 2.

You can do repeated submissions. New submissions will replace old ones.


Late Submissions

Late submissions will be accepted for 24 hours after the due date. If you miss a late submission deadline by a microsecond, your work will not be accepted.


Asking Questions

To ask a question about your program, first submit it, but use assignment name q2. For example, use command 

  ~abrahamsonk/2530/bin/submit q2 hailstone.cpp
Then send me an email with your question. Do not expect me to read your mind. Tell me what your questions are. I will look at the file that you have submitted as q2. If you have another question later, resubmit your new file as assignment q2 and send another email.