| Assigned: | Monday, January 8 |
| First version due: | Friday, January 19, 11:59pm |
| Second version due: | Monday, January 28, 11:59pm |
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.
Write a C++ program that reads a number n from the user (after giving a suitable prompt) and then tells the user three things: (1) the length of the hailstone sequence that starts with n, (2) the largest number in the hailstone sequence that starts with n, and (3) how many of the numbers in that hailstone sequence are even. The output needs to be sensible and easy to read, not just three numbers. For example, a session with this program might look like this. Parts in black are printed by the program. Parts in blue are typed by the user.
What number shall I start with? 7 The length of the hailstone sequence starting at 7 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 length of the hailstone sequence starting at 1 is 1. 0 of the numbers are even. The largest number in the sequence is 1.
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 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.
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.
You will need to use if-statements to make decisions, and you will need to use while-statements for repetition. Think about the job that each function needs to do, and how to do that job.
Compile your program and test it using g++ under Unix, as follows.
Log into one of the computers in Austin 208. At the login prompt, select options/session, and select Gnome. Type your computer science id, then return, then your password. When you type your password, nothing will be shown in the window. Your password is being read, though.
Create a terminal by right-clicking on the background, and selecting terminal.
You can see your files by typing command ls in the terminal window. At the end of each command, type the return key. Your files are the same as the My Documents folder in Windows, which called your home directory in Unix.
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. You can get a simple text editor by selecting Applications at the top of the screen and selecting Accessories/Text Editor. When you save your file, be sure to save it in the 3300/assn1 directory.
Software can be constructed by makefiles, which contain the commands needed to build the software. Suppose that your program is called hailstone.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: hailstone.cpp $(CC) hailstone.cpp run: a.out 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.
Here is a suggestion of steps to get this done.
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. 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.
//====================================================================== // 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. 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.
#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;
}
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.
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.
At this point you should have a working program that is well documented, well indented and readable. Make sure that your name and the course name (Computer Science 3300) are in a comment at the top of the program. Test your program again after adding that comment. (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 turn in two versions of this program, unless your grade on version 1 is one that you prefer to keep. To submit a version of a program, run one of the following commands in a terminal window. I am assuming that your program is called hailstone.cpp. If it has a different name, substitute that name.
~karl/3300/bin/submit 1a hailstone.cpp
~karl/3300/bin/submit 1b hailstone.cpp
If your program loops forever, you will probably want to use a debugger to find out what is wrong. There is a 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
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 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.
You can find additional documention on using Unix here. The version of Unix that the computers in Austin 208 are running is called Solaris.
Whether you log into Unix or Windows in the Austin computer labs, you will see the same files.
You cannot run Windows executable files in Unix, or Unix executable files in Windows. They are different machine languages and different file formats. So do not try to create a.out on Unix and then run it on a Windows machine.
Unix and Windows have different conventions for how to end a line. Unix uses one character, called the linefeed character (Ascii code 10, abbreviated LF). Windows uses a sequence of two characters, the carriage-return character (Ascii code 13, abbreviated CR) followed by the linefeed character. One effect of this difference is that, if you look at a Unix text file using Notepad on Windows, it will all be one line, with rectangles standing for the linefeed characters. Notepad is looking for the CR-LF combination to end a line. By the same token, if you look at a Windows text file in Unix, you might see extra CR characters, one at the end of each line.
A CR is also a control-M, and a LF is also control-J. So a CR might look like a control-M, often written ^M, when you see it.
Note. The emacs text editor, available for both Windows and Unix, can edit files in either format, regardless of the kind of machine that it runs on. You can edit Unix files using the Windows version of emacs, for example, or Windows programs using the Unix version of Emacs. Emacs is described in the Solaris documentation. It is available from www.gnu.org. (Gnu tools will work in Unix, Linux, MacOS X or Windows, not just in the Gnu operating system.)