Assigned: | Tuesday, September 6 |
Due: | Wednesday, September 14, 11:59pm |
This assignment is intended to familiarize you with basic C++, including loops, functions and function contracts.
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.
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 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 when you run it.
Write and test a C++ program that reads a number n from the user (after giving a suitable prompt) and then tells the user the following information:
the entire hailstone sequence starting at n, all on one line, with the numbers separated by spaces;
the length of the hailstone sequence that starts with n;
the largest number in the hailstone sequence that starts with n;
the largest length of any hailstone sequence starting with a number from 1 to n.
the starting number of the longest hailstone sequence starting 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
The nonfunctional requirements are additional requirements on how the program must be written, documented, etc., that are not directly concerned with what the program does when you run it.
This program is required to contain the functions described below under "design issues and a development plan." If the function that is described takes one parameter, make sure that your function takes one parameter. Each function must perform the job that is described for it.
The program is required to follow the coding standards for this course, which include the following.
You are required to start from the template that is provided. Be sure to put in your own name and the assignment number. Notice that, if you use tabs, you must say how far it is between tab stops. If you have a tab stop every 4 characters, for example, say
Tabs stops: 4
The program must use the correct file format and file name. Be sure to indent well. Put a blank line before and after each function contract.
Only use margin comments sparingly, if at all.
Each function can have at most one loop in its body.
A function body must not change the value of a call-by-value 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.
Avoid calling the same function with the same parameter more than once, especially when it is easy to avoid that by storing the result in a variable.
The last character that your program writes should be an end-of-line character ('\n').
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.
The body of every if-statement, loop, etc. must be a compound statement. That is, it must be surrounded by braces.
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.
Every function is required to have a clear, concise and precise contract. Make sure that your contract describes what the function accomplishes, how each parameter affects what the function accomplishes and what the returned value means (if there is a returned value). Refer to parameters by name, not by pronouns or phrases such as "it" or "the integer."
Your contract should not say how the function accomplishes its job. It should not refer to local variables in the function's body. Assume that anyone reading the contract can also see the function's heading, but not the function's body. It is not necessary to say what the type of each parameter is in the contract, since that is clear from the heading. Do not say what the return type is, since thhat is also clear from the heading.
Here is a good contract and heading for the function that finds the
length the hailstone sequence starting at n.
// hailLength(n) returns the length of the hailstone sequence
// starting at n.
int hailLength(int n)
Here is a contract that is cluttered with irrelevant information and
that refer to the parameter by a phrase, "a given integer" instead
of by its name, n.
// hailLength(int n) goes through the hailstone sequence starting at
// a given integer. It finds the length and then returns the length.
// The length has type int.
The fact that n has type int is clear from the heading.
Saying that this function "goes through the hailstone sequence …"
is trying to say how it works. Sayingthat it "finds the length"
is redundant, since the function cannot return the length without
finding it. There is no need to say what the
return-type is.
Avoid vague contracts, such as this one.
// This function computes the length of a hailstone sequence.
Always talk about parameters by name. Always say explicitly
what is returned.
Use correct spelling and punctuation.
Write a comment near the beginning of the program that tells what the program does. It serves as a contract for main. You do not need a separate contract for main.
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 can include information about how some critical functions work, but for this course you should avoid such details.
This section both describes the required design and suggests how to write the program. You are required to follow this design.
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 1. 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 where 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 contract for a function that takes an integer value n and returns the number that follows n in the 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 the 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. |
4. Now write a C++ definition of the function that you have described in the preceding item. The C++ definition is called the implementation of the function. Make sure the implementation is faithful to the contract. |
5. 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 the next function works. Make sure that your tests, taken together, make use of every line that you have written. |
6. 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 one a few different values of n. Do not move on until this part works. |
7. 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 write (print) anything. Modify your main function to 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. |
8. 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 write anything. Modify your main function to so that it also shows the result of this function. Test it one a few different start values before moving on. |
9. 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 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 to so that it also shows the result of this function. 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 start value k, from 1 to n, that has the longest length. This function must not 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 to so that it also shows the result of this function. Test it on a few different start values. |
11. Check your assignment. Proofread your contracts. Look for spelling and grammatical errors. Ensure that you have followed the standards. |
12. Submit your work. |
Get file Makefile and put it in the same directory as your program. Then, use the following commands.
After doing make debug, you will get a prompt
(gdb)
Type
run
to start running your program. Before that you can set
a breakpoint: a place where the debugger will pause your
program. To set a breakpoint at the beginning of hailPrint,
say
break hailPrint
before you type run. When the program enters hailPrint,
the program will pause. Type
print x
to print the value of variable x. Type
cont
to continue running.
If the program appears to be in an infinite loop,
type control-C. The debugger will stop the program.
Type
bt
to get a backtrace, which shows
which functions are running, with the most recently started
function on top.
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 1, change
your directory to the one that holds assignment 1 and do the
following command.
~abrahamsonk/2530/bin/submit 1 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 1
will show you what you have submitted for
assignment 1.
You can do repeated submissions. New submissions will replace old ones.
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.