in c++ language and please focus on
Additional Requirements
For this assignment,
no function is allowed to change the value of
any variable, once that variable has been given a value. Pay attention to this!
You will lose a lot of points if you ignore this requirement. If you change the value of a variable with recursion at this point in your studies, it almost always means that you are not on the right track.
In most assignments, you are allowed to add extra functions. But
for this assignment, you must not add any additional functions.
Only write the functions that are required.
You will receive no credit for any required function that depends on an extra function that is not among the required functions.
It is important to define
exactly
the functions described in the design. Do not try to improve on the design. Do not add extra responsibilities to functions. Do not change the design for any reason.
All of the functions take exactly one parameter.
If you write a function that does not take
exactly
one parameter, then you will receive no credit for that function
Do not use arrays, default parameters or call-by-reference. Do not use any features of the C++ Standard Template Library.
Things to watch out for
Pay attention to the list of issues in assignment 2. Additionally, avoid creating a variable that is just a copy of another variable. For example, if you have a
length
function that begins
int length(int n)
{
int m = n;
…
}
then you have created a variable
m
that is just another name for
n. Remember that you can't change either of
m
and
n. Having two names for the same thing just confuses things.
Suggestions
Suggestions
|
1.
Create a directory to hold assignment 3. Copy files
hailstone.cpp,
Makefile
and
dotest
assignment 2 to the assignment 3 directory. Edit the comments at the top of
hailstone.cpp
to say that this is assignment 3.
You should be able to keep the same contracts, 'next' function and 'main' function from assignment 2, unless they contained errors that needed to be fixed. If necessary, edit those functions so that they do not change the value of any variable, once the variable has a value.
|
|
2.
Modify the other functions so that they use recursion instead of loops. Modify them one at at time, and test each one after modifying it. Do not try to modify them all then test them all together. The remaining items give some hints.
|
|
3.
Modify the function that
prints the entire sequence. Include a special case for
n
= 1. When
n
> 1, the sequence that starts at
n
contains
n
followed by the sequence that starts at next(n).
|
|
4.
Suppose that you want to find
the length of the hailstone sequence
starting at 7. Notice that next(7) = 22. If you ask for the length of the hailstone sequence starting at 22 (result: 16), how would you determine the length of the sequence starting at 7?
Handle the length of the sequence starting at 1 as a special case. Use an if-statement to decide whether this is the special case of
n
= 1 or not.
|
|
5.
Suppose that you want to know
the largest number in the sequence
starting at 7. Ask for the largest number in the sequence starting at 22. (The answer is 52.) The largest number for 7 is clearly the larger of 7 and 52, since 7 is the only number that was not already taken into account in the sequence starting at 22.
As another example, suppose that you want to know the largest number in the sequence starting at 52. Ask for the largest number in the sequence starting at 26 (since next(52) = 26). The answer is 40. What you want is the larger of 52 and 40: clearly 52.
Important Note.
In terms of efficiency, recursion acts as an amplifier. Algorithm designers use it because, if they think of a clever idea and they use it in a recursive definition, recursion amplifies it into a very efficient algorithm.
But recursion also amplifies bad ideas. If you do something in a slopply way in a recursive function, recursion can amplify it and make a
very slow
algorithm. In particular, if you do the same recursive call twice, which is a waste of time, recursion will be very slow. Try your program on input 97. Does it respond quickly, or is it really slow? Try it on a few larger numbers, say around 1000.
|
|
6.
Suppose you want to compute
the length of the longest sequence
starting on a number from 1 to
n. If
n
= 1, the answer is obvious. If
n
> 1, first get the length
k
of the longest sequence starting on a number from 1 to
n
− 1. Then compute the larger of length(n) and
k.
|
|
7.
Suppose you want to compute
the starting value of the longest sequence
starting on a number from 1 to
n. Again, the answer is obvious when
n
= 1. If
n
> 1, first get the starting value
m
of the longest sequence starting on a number from 1 to
n
− 1. Then compare length(n) and length(m). How can you determine the answer from the result of that comparison?
|
|
8.
Pay attention to the issues to be aware of listed for assignment 2.
|
Infinite Recursion
One problem that you might encounter is an infinite recursion, where a function keeps calling itself with the same value until it runs out of memory.
Since you are testing one function at a time, you will know which function is at fault. It will be the one that you just added. Inspect it. (What happens to you if you wrote all of the functions and are trying to test them all at once? You end up in the swamp. Not a good idea.)
If you run gdb with an infinite recursion, try to stop the program with control-C before it has produced too many copies of your function. If you do a backtrace and gdb says the run-time stack is corrupt, or that there is no run-time stack, then it means that you have run out of memory. Try slowing down your function by making it write something. Then you will be able to stop it before too many copies have been created.
this is assignment 2
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 number
n
from the standard input (after giving a suitable prompt) and then writes the following information on the standard output:
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 length of the longest hailstone sequence that starts with a number from 1 to
n;
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.
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.call-by-reference for this assignment. Do not use any features of the C++ Standard Template Library. You can use the , and libraries for this assignment.
All of the functions take exactly one parameter.
If you write a function that does not take exactly one parameter, other than a helper function that is not one of the required functions, then you will receive no credit for that function
Do not use arrays in this assignment. Do not use default parameters.
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.
|
|
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. (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? Just write a number.)
|
|
3. Write a comment telling what the program will do when you are finished writing it.
Say what the input is and give an example of the output. Avoid talking about how the program works.
|
|
4. Write a heading and contract for a function next(n).
This function must take exactly one integer
n
and return the number that follows
n
in a hailstone sequence. Follow the guidelines for function contracts.
Examples of what 'next' does are: next(7) = 22 and next(22) = 11.
Since there is no number that follows 1 in a hailstone sequence, 'next' requires its parameter
n
to be greater than 1. State that in the contract.
Your program must never compute next(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 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 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 heading and a contract for a function that takes an integer
n
and writes the entire hailstone sequence starting at
n.
This function must take exactly one parameter of type
int and it must have a
void
return-type. It must write the entire sequence on one line, with the numbers separated by spaces. Say so in the contract.
Follow the guidelines for contracts.
|
|
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 show the hailstone sequence starting at
n.
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 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.
This function must take exactly one parameter of type
int and it must return a value of type
int.
This function 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.
|
|
12. Write a heading and contract, then the body, of a function that takes an integer
n
and returns the largest value in the hailstone sequence starting at
n.
This function must take exactly one parameter of type
int and it must return a value of type
int. 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
on a few different start values before moving on.
|
|
13. 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 take exactly one parameter of type
int and it must return a result of type
int. 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 this function.
Test it
on a few different start values before moving on.
|
|
14. Write a heading and contract, then the body, 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 take exactly one parameter of type
int and it must return a result of type
int. 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
on a few different start values.
|
|
15. Check your program.
Proofread your contracts. Look for spelling and grammatical errors. Ensure that you have followed the standards.
|
|
16. Submit your work.
|
Compiling and Testing Your Program
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 do command
chmod u+x dotest
to make dotest executable. 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.