Computer Science 2530
Spring 2020
Programming Assignment 2

Table of Contents

1. Purpose of this assignment
2. What you will submit
3. Requirements
4. Background
5. The assignment
6. Functions
7. Getting started
8. A refinement plan
9. Successive refinement and refinement barriers
10. Compiling and testing your program
11. Issues to be aware of
12. Submitting your work
13. Late submissions
14. 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. Be sure to follow the instructions.

What You Will Submit

---

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

Requirements

---

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

• arrays.
• call-by-reference,
• any features of the C++ Standard Template Library,
• default parameters,
• global or static variables

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

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 hailstone sequence starting at 7 is [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] and its length is 17.

• The hailstone sequence starting at 6 is [6, 3, 10, 5, 16, 8, 4, 2, 1] and its length is 9.

• The hailstone sequence starting at 1 is [1] and its length is 1.

The Assignment

---

Write and test a C++ program that reads a positive integer 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. A longest hailstone sequence that starts with a number from 1 to n. (There might be two or more equally long sequences. Only one of those should be shown.)

5. The length of the hailstone sequence shown in part 4.

6. A hailstone sequence that starts with a number from 1 to n that contains the largest number.

7. The largest number in the hailstone sequence shown in part 6.

The output must be in the following format, illustrated for n = 16.

  What number shall I start with?  16
  sequence: 16 8 4 2 1
  length: 5
  largest: 16

  For start values from 1 to 16:

  longest: 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
  length: 20

  containing largest: 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
  largest: 160

Functions

---

Define the following functions. Use exactly the function headings shown.

int next(int n)

Next(n) returns the number that follows n in a hailstone sequence.

Any time any function other than next needs to find the value that follows another, it must use next to get that number.

No function in this program should ask for next(1) ever, under any circumstances.

Next must not read anything from the standard input or write anything to the standard output.

void PrintSequence(int n)

PrintSequence(n) writes the entire hailstone sequence that starts with n.

PrintSequence must not read anything from the standard input.

int length(int n)

Length(n) returns the length of the hailstone sequence that starts with n.

Length must not read anything from the standard input or write anything to the standard output.

int largest(int n)

Largest(n) returns the largest value in the hailstone sequence that starts with n.

Largest must not read anything from the standard input or write anything to the standard output.

int longestStart(int n)

LongestStart(n) returns the start value of the longest hailstone sequence that starts with an integer from 1 to n.

LongestStart must not read anything from the standard input or write anything to the standard output.

int largestStart(int n)

LargestStart(n) returns the start value of the hailstone sequence starting with an integer from 1 to n that contains the largest value.

LargestStart must not read anything from the standard input or write anything to the standard output.

Getting Started

---

Create a directory to hold assignment 2. Download

• Makefile
• dotest

into that directory.

Create file hailstone.cpp. Copy and paste the template into it. Edit the comment at the top of the file to show your name, the assignment number, the file name (hailstone.cpp) and the distance between tab stops. (If you don't know where the tab stops are, you can edit that part later when you know.)

A Refinement Plan

---

Write this program in the following steps. Do not skip any steps, and do not move on to step k + 1 until you have completed step k successfully.

1. Write a comment (the program comment) near the beginning of the program that tells what this program will do when it is finished. Write the program comment after the initial information (your name, etc.) and with a blank line between the initial information and the program comment.

   If you copy and paste from a browser, the browser 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 in a sensible, numbered list.

   Put a blank line between paragraphs. If you use a numbered list, put a blank line before each item in the list.

2. Write a contract for next. In the contract, do not say anything that is obvious from the heading.

   Then write a definition of next in C++.

3. Write a main function that reads an integer n and shows next(n). Test what you have. Test an even input and an odd input. Do not move on until next works.

4. Write a contract for PrintSequence. Then write a definition of PrintSequence.

5. Modify main. Remove the test of next. Make main so that it reads n and shows the hailstone sequence that starts with n. Use the output format shown above.

6. Write a contract for length. Then write a definition of length.

7. Modify main so that it also shows the length of the hailstone sequence. Test your program. Do not move on until length works.

8. Write a contract for largest. Then write a definition of largest.

9. Modify main so that it also shows the largest value in the hailstone sequence. Test your program. Do not move on until largest works.

10. Write a contract for longestStart. Then write a definition of longestStart.

11. Modify main so that it also shows an entire longest hailstone sequence starting with a number from 1 to n and the length of that sequence. Test your program. Do not move on until longestStart works.

12. Write a contract for largestStart. Then write a definition of largestStart.

13. Modify main so that it also shows an entire hailstone sequence starting with a number from 1 to n that contains the largest number, and the largest number in that sequence. Test your program. Do not move on until largestStart works.

14. When you are satisified that your program works and is well written, submit your work.

Successive Refinement and Refinement Barriers

---

The refinement plan above is more than a suggestion. Follow it. Do not write all of the functions then begin testing.

By the refinement barrier rule:

1. If next does not work, you will receive no credit for any other functions.

2. If length does not work, you will receive no credit for longestStart.

3. If largest does not work, you will receive no credit for largestStart.

Compiling and Testing Your Program

---

Use the following commands to compile and test your program.

make

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

make run

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

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 hailstone. 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. Remember that main must not contain a loop.

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

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

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

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

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

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

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

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

  ~abrahamsonk/2530/bin/submit 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