Assigned: | Tuesday, January 28 |
First version due: | Tuesday, February 4, 11:59pm |
Second version due: | Tuesday, February 18, 11:59pm |
This assignment is intended to familiarize you with C++, loops, functions and contracts.
It is important that you follow the instructions. Do not try to improve on the design described here. Read the entire assignment before you start working on it.
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 times 7 plus 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 it contains 17 numbers. The hailstone sequence starting at 6 is [6, 3, 10, 5, 16, 8, 4, 2, 1], and the hailstone sequence starting at 1 is [1].
The functional requirements tell what the program is supposed to do.
Write a C++ program that reads a number n from the user (after giving a suitable prompt) and then tells the user four things:
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. 6 of the numbers are odd. The largest number in the sequence is 52. The longest hailstone sequence starting with a number up to 7 has length 17
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.
1 of the numbers are odd.
The largest number in the sequence is 1.
The longest hailstone sequence starting with a number up to 1 has length 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.
1 of the numbers are odd.
The largest number in the sequence is 8.
The longest hailstone sequence starting with a number up to 8 has length 17
The nonfunctional requirements are additional requirements on how the program must be written, documented, etc.
The program is required to be written in accordance with the design issues discussed below.
The program is required to follow the coding standards for this course, which include the following.
The design of a program includes issues such as which functions it includes, how those functions are organized into modules, and what each function and module accomplishes. It does not include details of how each function works.
For this assignment, there should be only one file (or module). It should be called hailstone.cpp.
This is an exercise in using C++, not an attempt to design the most efficient possible solution to this problem. Your design is required to use the following functions. Do not try to fold all of these functions together into one. Do not modify what each function is supposed to do. Make it do what is called for.
Include a function that computes the value that follows a given value n in the hailstone sequence. If you call it next, then next(7) = 22 and next(22) = 11. Any time you want to get the next number in the sequence, you must use this function.
Include a function that takes an integer n and prints the hailstone sequence starting at n on one line, separating the numbers by spaces. This function should not print a newline character. Make the return type void, indicating that it does not yield an answer, it just does something.
Include a function that takes an integer n and returns the length of the hailstone sequence starting at n. For example, if this function is called hailstoneLength, then you will find that hailstoneLength(3) = 8, hailstoneLength(4) = 3 and hailstoneLength(1) = 1.
Include a function that takes an integer n and returns the largest number in the hailstone sequence starting at n. For example, if this function is called hailstoneLargest, then you should find that hailstoneLargest(3) = 16 and hailstoneLargest(4) = 4.
Include a function that takes an integer n and returns the number of odd numbers in the hailstone sequence starting at n. For example, if this function is called hailstoneOdds, then you should find that hailstoneOdds(3) = 3, hailstoneOddss(4) = 1 and hailstoneOdds(1) = 1.
Include a function that takes an integer n and returns the length of the longest hailstone sequence that starts with a number from 1 to n. For example, if this function is called hailstoneLargestLength, then hailstoneLargestLength(3) = 8 and hailstoneLargestLength(10) = 17.
Include a main program that interacts with the user, asking for the start number n, and then writing the results.
You can include any other functions that you find helpful.
For this program, use loops. Do not use recursion.
Get file Makefile and put it in the same directory as your program. Then, to compile your program, it suffices to perform command
makeTo run it, use command
make runTo run it via gdb, use command
make debugTo remove all machine-generated files, use
make clean
For a large piece of software, it is critical to have a development plan. You simply cannot write the whole thing and then begin testing. This assignment is not a large piece of software, but it is a good idea to become familiar with development plans on smaller programs rather than being thrown into them on your first large program.
Here is a suggestion for steps to get this done. It uses an approach called successive refinement, where you write a little bit, test it, write a little more, test that, and so on.
Write the design as a skeleton program.
Start from the template
and modifiy it.
If you use tabs, also include a comment telling how often there
is a tab stop. For example,
// tab stops: every 4 characters
says that a tab moves 4 characters.
Write a contract and heading for each function, with an empty body. For example, a contract and heading for function next could be as follows.
//====================================================================== // next(n) returns the number that follows n in the hailstone sequence. // For example, next(7) = 22 and next(22) = 11. //====================================================================== int next(int n) { }
Write the body of the next function. Make it do exactly what the contract says it does. Make sure this function definition is well indented before you test it. Keep every function well indented while you work on it.
Now test it. Write a main program that just computes next of a few values, and checks that they are right. Here is a sample main program.
#include <cstdio> using namespace std; ... int main() { printf("next(3) = %i\n", next(3)); printf("next(7) = %i\n", next(7)); printf("next(22) = %i\n", next(22)); printf("next(44) = %i\n", next(44)); return 0; }Write main at the bottom of the program. In C++, you need to define a function (or provide other information about it) before it is used
Write the function prints the entire sequence. Make sure that it is well indented and readable. Be sure that it uses the next function to compute the next value. Check it by doing a hand simulation.
Modify your main program so that it now reads a number n from the
user and prints the hailstone sequence starting at n.
Your main program might look as follows.
#include <cstdio>
using namespace std;
...
int main()
{
int n;
printf("What number should I start with? ");
scanf("%i", &n);
printf("The hailstone sequence starting at %i is\n", n);
printHailstoneSequence(n);
printf("\n");
return 0;
}
Test it.
Write the function that computes the length of the hailstone sequence starting at n. Make sure it is well indented and readable. Check it by doing a hand simulation. Modify main so that it shows both the hailstone sequence and its length. Test it.
Write the function that computes the largest number in the sequence. Keep it well indented and readable. Check it by doing a hand simulation. Augment your main program to use that function. Test it.
Write the function that computes how many of the numbers are odd. Keep it well indented and readable. Check it by doing a hand simulation. Augment the main program to show that information. Test it.
Write the function that computes the length of the longest hailstone sequence for any starting value from 1 to n. Augment the main program to show that information. Test it.
At this point you should have a working programs that is well documented, well indented and readable. Submit your program. See below for how to do that.
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 version (a), log into one of the Linux machines, change
your directory to the one that holds your programs, and do the
following command.
~abrahamsonk/3300/bin/submit 1a hailstone.cpp
To turn in version (b), do the following.
~abrahamsonk/3300/bin/submit 1b 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.
You can do repeated submissions. New submissions will replace old ones.