| Assigned: | January 17 |
| Design due: | January 23, 11:59pm |
| First version due: | January 30, 11:59pm |
| Second version due: | February 6, 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.
This is an exercise, 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.
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.
You have functions that compute the desired results. 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. 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 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 directory.
Suppose that your program is called assn1.cpp. Compile your program by running command
g++ -Wall assn1.cpp
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 command
a.out
to run your program. 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 the 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. Check that each contract tells what the function does, not how it works, or what other tools it uses.
Put your name, the course name (Computer Science 3300) and the assignment number, as a comment, at the top of the file. Submit the design.
Make a copy of the design, so that you can keep the original design. You can copy a file using the cp command. For example,
cp assn1.cpp assn1.cpp.designwill create a copy of assn1.cpp called assn1.cpp.design.
Write 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.
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";
}
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. Submit it.
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, 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 three versions of this program.
The first version is just a design. It will contain a contract and a heading for each function, but it will not contain a body for any of the functions. Your name, with the course number and assignment number, and the version, should be at the top, in a comment. For example, your program might begin as follows.
// Chris Doe // Computer Science 3300 // Assignment 1, design
Be sure that each contract tells exactly what the function that it describes does. The contract must clearly explain the result, and how each parameter influences the result. 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)
You cannot run the design, since it does not contain any function implementations.
The next version is a complete, working program. Do not leave anything out.
The final version is also a complete, working program. You will receive feedback on your previous version, and have an opportunity to make improvements. This version contains those improvements.
To submit a version of a program, change to your home directory. Using a text editor, edit a file called ".bashrc". (The quotes are not part of the name, but the dot is. The file name starts with a dot. Be sure that your file has this name, and that it is in your home directory.) If that file does not already exist, you will create it. If it already exists, just edit it. Add the following line.
alias submit="~karl/3300/bin/submit"
Now, create a new terminal window. (The new window will read what is written in .bashrc.) In that window, use the following commands to submit your work. I am assuming that your program is written in file assn1.cpp. If it has a different name, use that name.
submit 1a assn1.cpp
submit 1b assn1.cpp
submit 1c assn1.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.
First, recompile your program using option -g, as follows.
g++ -Wall -g assn1.cpp
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 from 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 print the variables in the current function.
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 or Windows, not just in the Gnu operating system.)