Computer Science 2530
Fall 2017
Programming Assignment 2

Assigned: Wednesday, September 13
Due: Monday, September 25, 11:59pm

Table of Contents

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

Purpose of This Assignment

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

It is important that you follow the instructions. Define exactly the functions that are listed. Do not try to improve on the design described here. 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.


A Refinement Plan and Additional Requirements

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

Development plan

1. Create a directory (folder) to hold assignment 2. Put all of the files for this assignment in that directory.

2. Create a file called hailstone.cpp. Copy and paste the template into it. 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?)

3. Write a comment telling what the program will do when finished. Say what the input is and give an example of the output.

4. Write a contract for a function that takes an integer value n and returns the number that follows n in a hailstone sequence. If you call this function next, then next(7) = 22 and next(22) = 11.

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

Any time you want to get the next number in the sequence, you must use this function.

5. Write a C++ definition of the function that you have described in step 4. 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 it on a few values to make sure that next works. Make sure that your tests, taken together, make use of every line of code that you have written.

7. Write a contract, then an implementation, of a function that takes an integer n and writes the entire hailstone sequence starting at n. This function has a void return type.

Modify your main function so that it no longer shows next(n), but shows the hailstone sequence starting at n. Test it on a few different values of n. Do not move on until this part works.

8. Write a contract, then an implementation, of a function that takes an integer n and returns the length of the hailstone sequence starting at n. This function must not read or write anything.

Modify your main function so that it shows both the hailstone sequence and the length of the hailstone sequence starting at n. Test it on a few different starting values n before moving on. If it does not work, fix it.

9. Write a contract, then an implementation, of a function that takes 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 it on a few different start values before moving on.

10. 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 not read or write anything.

Do not duplicate code to find the length of a hailstone sequence. Use your function from step 7 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.

11. Write a contract, then an implementation, 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 not read or write anything.

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

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

12. Check your program. Proofread your contracts. Look for spelling and grammatical errors. Ensure that you have followed the standards and additional requirements.

13. Submit your work.


Compiling and Testing Your Program

Get file Makefile and put it in the same directory as your program. Then use the following commands.

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
Run hailstone.cpp via the gdb debugger. See below for a brief description of gdb.

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. Follow the instructions. Do not write this as a single monolithic main function. The design is not optional. You are required to write and use the indicated functions. A program that has only a main function will receive a grade of 0.

  2. Do not ignore compiler warnings. If you do not understand what a warning means, ask about it.

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

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

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

  6. Pay attention to contracts. Read about the requirements for them. Documentation matters. Make sure that each function does what its contract says it does. Put a blank line before and after each function contract.

  7. The last character that your program writes should be an end-of-line character ('\n').

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

  9. Do not use call-by-reference for this assignment.

  10. The body of every if-statement, loop, etc. must be a compound statement. That is, it must be surrounded by braces.

  11. Each pair of matching braces must be in the same column, with the right brace immediately below the matching left brace, and with no characters on or to the left of a line segment between the braces. An if-statement would be something like the following. 

      if(…)
  {
    …
  }

  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.