Computer Science 2530
Fall 2018
Programming Assignment 2

Assigned: Monday, September 10
Due: Monday, September 24, 11:59pm

Table of Contents

  1. Purpose of this assignment
  2. Background
  3. The assignment
  4. Additional requirements
  5. A refinement plan
  6. Compiling and running your program on xlogin
  7. Issues to be aware of
  8. Submitting your work
  9. Late submissions
  10. Asking questions

Purpose of This Assignment

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

Read the entire assignment before you start working on it.


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. the length of the longest hailstone sequence that starts with a number from 1 to n;

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

The output needs to be sensible and easy to read, not just numbers. Each piece of information should be on a separate line. For example, a session with this program might look as follows. 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
  The length of the sequence is 17.
  The largest number in the sequence is 52.
  The longest hailstone sequence starting with a number up to 7 has length 17.
  The longest hailstone sequence starting with a number up to 7 begins with 7.

Here is another example. 

  What number shall I start with?  1
  The hailstone sequence starting at 1 is:
  1
  The length of the sequence is 1.
  The largest number in the sequence is 1.
  The longest hailstone sequence starting with a number up to 1 has length 1.
  The longest hailstone sequence starting with a number up to 1 begins with 1.

And here is another. 

  What number shall I start with?  8
  The hailstone sequence starting at 8 is:
  8 4 2 1
  The length of the sequence is 4.
  The largest number in the sequence is 8.
  The longest hailstone sequence starting with a number up to 8 has length 17.
  The longest hailstone sequence starting with a number up to 8 begins with 7.


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.call-by-reference for this assignment. Do not use any features of the C++ Standard Template Library. 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, other than a helper function that is not one of the required functions, then you will receive no credit for that function

Do not use arrays in this assignment. Do not use default parameters.

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


A Refinement Plan

Development plan
1. Create a directory (folder) to hold assignment 2.

Put all of the files for this assignment in that directory.

2. Use an editor to open a file.

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

Edit the file. Add your name and the assignment number. If you will use tabs, say how far apart the tab stops are. (If you don't know, type a line of about 8 x's. Then, in the line beneath that line, type a tab. How many x's were skipped over? Just write a number.)

3. Write a comment telling what the program will do when you are finished writing it.

Say what the input is and give an example of the output. Avoid talking about how the program works.

4. Write a heading and contract for a function next(n).

This function must take exactly one integer n and return the number that follows n in a hailstone sequence. Follow the guidelines for function contracts.

Examples of what 'next' does are: next(7) = 22 and next(22) = 11.

Since there is no number that follows 1 in a hailstone sequence, 'next' requires its parameter n to be greater than 1. State that in the contract. Your program must never compute next(1).

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 C++ definition of 'next'.

The C++ definition is called the implementation of the function. Make sure the implementation is faithful to the contract.

6. Write a main function that reads an integer n and shows the value of next(n).

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.

7. Write a heading and a contract for a function that takes an integer n and writes the entire hailstone sequence starting at n.

This function must take exactly one parameter of type int and it must have a void return-type. It must write the entire sequence on one line, with the numbers separated by spaces. Say so in the contract.

Follow the guidelines for contracts.

8. Implement the function described in step 7.

Make the function definition be faithful to the contract.

9. Modify main.

Make main no longer show next(n), but show the hailstone sequence starting at n.

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.

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

This function must take exactly one parameter of type int and it must return a value of type int. This function must not read or write anything.

11. Modify main.

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

Test your on a few different starting values n before moving on. If it does not work, fix it.

12. Write a heading and contract, then the body, of a function that takes an integer n and returns the largest value in the hailstone sequence starting at n.

This function must take exactly one parameter of type int and it must return a value of type int. 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 on a few different start values before moving on.

13. Write a contract, then an implementation, of a function that takes an integer n and returns the length of the longest hailstone sequence starting at a number from 1 to n.

This function must take exactly one parameter of type int and it must return a result of type int. This function must not read or write anything.

Do not duplicate code to find the length of a hailstone sequence. Use your function from step 10 for that.

Modify your main function so that it also shows the result of this function. Test it on a few different start values before moving on.

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

This function must take exactly one parameter of type int and it must return a result of type int. 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 on a few different start values.

15. Check your program.

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

16. Submit your work.

Compiling and Testing Your Program

Get files Makefile and 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 do command 
  chmod u+x dotest
to make dotest executable. Then you can use the following commands in a terminal window.

make
Just 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 for debugging (if necessary), creating executable file hailstoned. Run hailstoned via the gdb debugger.

make test
Compile hailstone.cpp for debugging (if necessary), creating executable file hailstoned. Run hailstoned 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.

  2. Indent well throughout.

  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. When easy to do so, avoid calling the same function with the same parameter more than once. Store a result into a variable to compute it once and use it twice. But stick with the overall design; don't alter the design to make it more efficient.

  7. If a particular statement is done at the beginning of both branches of an if-statement, move that statement before the if-statement, where it only needs to be written once. A similar rule applies to a statement that occurs at the end of both branches of an if-statement.

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

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

    Put a blank line before and after each function contract.

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

  11. Do not use any global or static variables. This is another one to watch out for. Using global or static variables will cost you a very large number of points.

  12. If code is only performed at the end of the last iteration of a loop, then it should be written after the loop, not inside the loop.


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.