Computer Science 2530
Spring 2019
Programming Assignment 2

Assigned: Friday, January 25
Due: Monday, February 4, 11:59pm
Points: 400

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;

  6. the largest number that occurs in any 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 part 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.
The largest value in any hailstone sequence starting with a number up to 7 is 52.

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.
The largest value in any hailstone sequence starting with a number up to 1 is 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.
The largest value in any hailstone sequence starting with a number up to 8 is 52.


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

for this assignment. 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 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. Start by getting files Makefile and dotest and put them 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.


3. 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 someone can read to determine

  1. 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. what information the program writes and where it writes to (the standard output). Show a sample output. You can take a sample from the assignment.

  3. Show a sample output. what information the program writes and where it writes to (the standard output).

Do not try to define a hailstone sequence. 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."

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

  1. Use complete sentences.

  2. Check spelling and punctuation.


4. Add a contract for function 'next'.

Copy the following contract 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.

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 heading for 'next' must be int next(int n)

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

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


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


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

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

  void writeHailstoneSequence(int n)

The contract should not explain information that is clear by looking at the heading. Don't say that it takes a parameter n of type int. Don't say that it returns a value of type int. Give useful information.


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


10. 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 lengthHailstone(int n)

Function lengthHailstone 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. Use the testingautomated tester.


12. Write 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.

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.


13. Write a function that returns the longest hailstone sequence starting 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 length of the longest hailstone sequence starting at a number from 1 to n.

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

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.

This function must not read or write anything.

Do not duplicate code to find the largest value in a hailstone sequence. Use your function from step 12.

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


16. Check your program.

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


17. Submit your work.

Compiling and Testing Your Program

If you haven't already, 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 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. 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.

    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.

  9. Do not use any global or static variables.


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.