| Assigned: | Wednesday, September 3 |
| First version due: | Friday, September 12 |
| Second version due: | Monday, September 22 |
This assignment lets you get familiar with C++.
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.
This is intended to be a warmup assignment. It does not reflect the kinds of things that we will be doing. Expect later assignments to be larger, and to involve principles of data structures.
This assignment has two parts, involving two different ways of writing the program. Turn in both of them at the same time. (Remember that you turn in two versions of a programming assignment. For this assignment, each version involves two programs.)
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).
Write a C++ program that reads a number n from the user (after giving a suitable prompt) and then tells the user four things: (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; and (4) how many of the numbers in that hailstone sequence are even. The output needs to be sensible and easy to read, not just numbers. For example, a session with this program might look as follows. Parts in black are printed 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. 11 of the numbers are even. The largest number in the sequence is 52.
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. 0 of the numbers are even. The largest number in the sequence is 1.
The program is required to be written in accordance with the design issues and algorithmic issues discussed below.
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.
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.
Include a function that takes an integer n and returns the largest number in the hailstone sequence starting at n.
Include a function that takes an integer n and returns the number of even numbers in the hailstone sequence starting at n.
Include a main program that interacts with the user, asking for the start number n, and then printing the results.
Each function is required to have a clear and concise contract.
The design requires you to have functions that compute the desired results, such as the length of the sequence and the largest number in the sequence. You are required to use them. It is unacceptable to write them and then to let the main function do its own computation, without using the tools that are available to it.
For part 1, use if-statements to make decisions and loops for repetition. Think about the job that each function needs to do, and how to do that job.
Part 2 is similar to part 1, but for part 2 you are not allowed to us any kind of loop. Instead, use recursion. Think about how each function can help itself. For example, suppose that you want to find the length of the hailstone sequence starting at 7. If you asked 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.
Each function is required to have a clear and concise contract. Write the contract just before the function definition. Make sure that the contract tells what the function does, not how it works.
The functions in parts 1 and 2 are required to have exactly the same contracts in the two parts. For example, the contract for function length in part 1 must be identical to the contract for function length in part 2.
Compile your program and test it using g++ under Linix, as follows.
Log into one of the computers in Austin 208, or log into login.cs.ecu.edu using ssh or NX. Use your pirate id and password. Write your pirate id using lower case letters.
In the graphical user interface, create a terminal by right-clicking on the background and selecting open in Terminal. (For ssh, you are automatically in a terminal. You can create more by clicking on the new terminal button (white with blue dots across it)).
You can see the names of your files by typing command ls in the terminal window. At the end of each command, type the return key.
Create a new folder (or directory) for your CSCI 3300 assignments by issuing command
mkdir 3300
Then change to that directory using command
cd 3300
To show your current directory, type
dirs
Note that ~ stands for your home directory, and directories are
separated by /, not \.
Create another directory, inside the 3300 directory, for assignment 1. For example, do commands
mkdir assn1 cd assn1
Create your program using a text editor. If you are using ssh, you will probably be best off editing the file on your local computer and transfering it to the server. In the ssh window, there is a yellow button with blue dots over it at the top of the screen. Push that to get a file transfer window. Drag files back and forth.
In the graphical interface, you can get a simple text editor by typing command gedit in the terminal. Other editors are also available.
Software can be constructed by makefiles, which contain the commands needed to build the software. Suppose that your program is called hailstone1.cpp. Using a text editor, create the following file in the 3300/assn1 directory, and call it Makefile. (Just copy it from this document and paste it into the editor.)
CC=g++ -g -Wall -Wshadow -Wpointer-arith -O a.out: hailstone1.cpp $(CC) hailstone1.cpp run: a.out ./a.out debug: a.out gdb a.outThe spaces shown in blue must be a single tab character. Do not use spaces. The first character on those lines should be a tab.
Compile your program by running command
make
If you get any errors, then modify your program using the text editor.
If you just get another prompt, without any error messages,
then your program contains no compile errors. That does not guarantee
that it works, though.
Once your program compiles correctly, try running it. First, list your files using ls. You should see one called a.out. That is the executable version of your program. (Unix does not use the .exe convention that Windows uses for executable programs.) Use either command
./a.out
or
make run
to run your program. (If you use make run, then the computer
will automatically recompile your program first if you have modified
it, and then will run it.) Try it on several numbers, and check whether the
results are correct. Does it work? If your program gets stuck in
an infinite loop, type control-C (the control and C keys at the same
time) to stop your program.
To log out, click on Actions at the top of the screen, and select logout.
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. It does not work. 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 of steps to get this done. It uses an approach called successive refinement.
Write a design. Write a contract and heading for each function. Check that the contract for a function explains how each parameter influences what that function does. Refer to parameters by their names, not by pronouns or vague phrases. Write it all down in file hailstone1.cpp, not just on paper. Do this before writing the bodies of the functions.
Be sure that each contract tells exactly what the function that it describes does, not how it works. The contract must clearly explain the result, and how each parameter influences the result. It should not mention the roles of local variables inside the body. There is no need to be verbose, but be sure that the contract is precise. Write the contract, as a comment, followed by the function heading. Here is a sample contract and heading for the next function, with an empty body.
//======================================================================
// 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. You already have your design, so just write this in the design, in the spot that you have reserved for this function. Make sure that it does not try to do too much. Its only job is to get the next value in the sequence. Make it do that job, and nothing more. Make sure this function 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 that uses the iostream library for output.
#include <iostream>
using namespace std;
...
int main()
{
cout << "next(7) = " << next(7) << "\n";
cout << "next(22) = " << next(22) << "\n";
cout << "next(3) = " << next(3) << "\n";
cout << "next(44) = " << next(44) << "\n";
return 0;
}
Here is a an alternative main program that uses
the stdio library for output.
#include <cstdio>
using namespace std;
...
int main()
{
printf("next(7) = %i\n", next(7));
printf("next(22) = %i\n", next(22));
printf("next(3) = %i\n", next(3));
printf("next(44) = %i\n", next(44));
return 0;
}
To keep the compiler happy, write main at the bottom of the program.
You will need to define a function before it is used. (This is
different from Java, where you can write methods in any order.)
Make a copy of your program, called hailstone2.cpp. (Command cp file1 file2 copies file1, and calls the copy file2. So use command
cp hailstone1.cpp hailstone2.cppContinue editing hailstone1.cpp.
Write the function that computes the length of the hailstone sequence, starting at n, in the spot reserved for it in your design. Make sure it is well indented and readable. Check it by doing a hand simulation. Be sure that it uses the next function to compute the next value.
Modify your main program so that it now reads a number n from the user, and prints just the length of the hailstone sequence starting at n. 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, so that it now prints both the length and the largest number. Test it.
Write the function that computes how many of the numbers are even. Keep it well indented and readable. Check it by doing a hand simulation. Augment the main program to show that information. Test it.
Now turn to hailstone2.cpp. Do the same steps, writing each of the functions that previously used a loop, but using recursion instead. Test your work.
At this point you should have two working programs that are well documented, well indented and readable. Write (1) your name, (2) the course number, (3) the assignment number at the top of each program, in a comment. Test your program again after adding that comment, to be sure it still works. (Never make even the most trivial modification without testing afterwards.) Submit your program. See below for how to do that.
If you find that your program is already in good shape, good. Give yourself a pat on the back. If you find yourself having to clean up the program at this point before submitting it, then you have not paid attention to the plan, and you are using software development methods that have been shown over and over to yield very bad results. Remember that you do not know more than those who have walked this road before you.
You will receive feedback on your program. If you have followed this plan, then you should end up with a grade of 100%. If there are any problems, then fix them and resubmit your program.
You will get instructions on how to submit your work later.
If your program loops forever, you will probably want to use a debugger to find out what is wrong. There is a simple debugger called gdb that works as follows.
Make sure that your Makefile uses option -g, as shown above.
Now run a.out using gdb as follows.
gdb a.out
Alternatively, use the debug target in the makefile, as follows.
make debug
The debugger will greet you and give you a prompt. Type
run
to run your program.
You can interrupt your program using a control-C. When you do, you return to the debugger. It will show you the line that the program is currently running. If you type
backtrace
it will show you the functions that are waiting, with the main
program at the bottom. Each function called the one above it.
You can use bt as an abbreviation for backtrace.
You can print the value of a variable. For example, to find out what n is, type
print n
You can move to other functions. The functions in the stack are numbered, starting at 0, when you do backtrace. To go to the next-higher-numbered function, use command
up
To go to the next-lower-numbered function, type
down
You can only print the variables in the function that you are currently
looking at, so you need to move to that function first.
A good way to debug a program is to turn on the lights. That means show things that the program normally would not show. For this program, a good idea is to show the numbers in the hailstone sequence as you compute them, to see that you are doing the right thing. Remove those prints before handing in your program.