About the Author

    Donald's family was one of the very first to obtain the 8-bit Atari VCS (later named Atari 2600) console in 1977, slightly before it's public release in the United States. At the age of 11, he was copying examples from the Atari Basic booklet into the console, displaying classic programs such as "A IS 12".

     By the age of 15 in 1983, he wrote his first Pac-Man on the 8-bit Commodore 64 and a simple version of Joust. Computer systems he worked with included the Atari Computers (400, 800), Commodore computers (VIC-20, C-64), TSR-80, IBM XT, Apple Lisa, and Apple ][.

     In high school he won local tournaments for computer programming, placed Bronze in the International Computer Problem Solving Competition, returned the next year as the team captain and placed Silver.

     After high school, two attempts to work while in college failed due to the nature of the job which required random schedules with random days off and unwillingness to cooperate with a school schedule. Meanwhile, he continued self-study with a constantly growing library of computer science books and a file cabinet stuffed with notes and hand-written programs.

[to be continued]

About the Author

     Donald's family was one of the very first to obtain the 8-bit Atari VCS (later named Atari 2600) console in 1977, slightly before it's public release in the United States. At the age of 11, he was copying examples from the Atari Basic booklet into the console, displaying classic programs such as "A IS 12".

     By the age of 15 in 1983, he wrote his first Pac-Man on the 8-bit Commodore 64 and a simple version of Joust. Computer systems he worked with included the Atari Computers (400, 800), Commodore computers (VIC-20, C-64), TSR-80, IBM XT, Apple Lisa, and Apple ][.

     In high school he won local tournaments for computer programming, placed Bronze in the International Computer Problem Solving Competition, returned the next year as the team captain and placed Silver.

     After high school, two attempts to work while in college failed due to the nature of the job which required random schedules with random days off and unwillingness to cooperate with a school schedule. Meanwhile, he continued self-study with a constantly growing library of computer science books and a file cabinet stuffed with notes and hand-written programs. [to be continued]

The Basic Algorithm

Algorithm: A step-by-step procedure for solving a problem in a finite amount of time

    As a tutor working with beginning C++ students,. I observe their textbooks and lecture notes are excellent regarding the C++ language, grammar and syntax. Unfortunately, the ability to logically progress from the problem to a working solution is mission. I watch student jump straight from the textbook exercises into C++ code without having a good idea of what their program should look like when it's finished. This is like a builder constructing a house without a blueprint. This guide is designed to answer the question, "How do I solve C++ problems?"

    The goal of this guide is to show how to solve problems using step-by-step descriptions called Algorithms and pseudo-code, then how to translate those into C++.

---

    The idea of the computer dates back to the early 1800s when Charles Babbage designed the "Analytical Machine." The machine consisted of four parts and also is the foundation of the most basic computer algorithm:

1. Storage
2. Input
3. Calculations
4. Output

    Modern computers only add the requirement of performing logic, however, that doesn't change the basic algorithm.

Allocate (Declare) Storage

     This simply means to tell the computer that your program needs some memory. Every piece of data that the program must input must also be stored in memory and thus allocated. Every piece of data that is ouput likewise must also be allocated. Also, any piece of information that the calculations need to perform that is neither input nor output data must also be allocated. Although allocating storage must happen before anything else in the program, this section is usually the last one to be written since knowledge of input, output, and calculations must be determined first.

     C++ will allow you to freely mix allocation with any other part of the algorithm. I recommend against this for students for two reasons:

1. Keeping each section of the program separated from the other sections make the program easier to write and easier to fix
2. It's much easier to fix problems if you know exactly where to look for them

Input Data

     Only the extreme simplest programs do no require input. The classic example are the "Hello, world!" programs. Otherwise, your program will be interactive by requiring someone at the keyboard and screen to type in the data your program needs, or your program will be non-interactive will all of the input built into the program or files on the disk, but most of the time it will be a combination of both.

Prompt and Response

     Getting data from the user at the keyboard should always involve a prompt/response pair of commands. First, prompt the user by displaying on the screen a descriptive text instructing the user exactly what to do. Second, expect the user to type in some useful piece of information and store it in some location in the computer's memory.

Prompt: Tell the user what to do

Response: Receive information from the user and put it into memory.

When writing the algorithm, it's normal to simplify this by saying, "Input some piece of data," for example, when getting the user's last name, write:

Input the user's last name.

Next, when translating this into C++, break it into the two parts, prompt and response:

cout << "Enter your last name: ";

cin >> lastName;

Writing the Input Data algorithm

     To write this section of the algorithm, read through the textbook exercise and look for places where the problem says to input or prompt for information. List each piece of information here.

Perform Calculations

     This section of code takes the input values and transforms them into output values.

     An example from algebra takes two points, (x1, y1), (x2, y2), and find the distance between them using the formula:

     The goal here is to translate from an algebraic formula into C++. Since C++ does not have built-in operators for squaring or for square roots, some functions from the <cmath> header is needed: sqrt() and pow().

(x2-x1)² in C++ is pow(x2-x1, 2)

(y2-y1)² in C++ is pow(y2-y1, 2)

in C++ is sqrt(pow(x2-x1, 2) + pow(y2-y1, 2))

The final C++ code looks like this:

d = sqrt(pow(x2-x1,2) + pow(y2-y1,2));

HOWEVER...

     This is only one of several possible solutions. Programmers will cringe at the above code because it calls on the pow() function which typically requires several hundred machine language instructions to complete. A much more efficient (in terms of speed) would be to multiply (x2-x1) by itself like this:

(x2-x1)² in C++ is (x2-x1)*(x2-x1)

(y2-y1)² in C++ is (y2-y1)*(y2-y1)

d = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));

This is also a correct, faster, but slightly harder to read solution.

Working Storage...

Sometimes a calculation can be better by introducing more memory to store in-between results. This is called working storage.

Again, some programmer will cringe at the above solution because it performs duplicate calculations, performing x2-x1 twice and y2-y1 twice. They will declare some extra memory so that they can perform these calculations exactly one time, and their final C++ code ends up looking like this:

dx = x2-x1;

dy = y2-y1;

d = sqrt(dx*dx + dy*dy);

This is also a correct, fastest, and slightly harder to code solution since it requires allocating more memory.

Which one should you use?

1. d = sqrt(pow(x2-x1, 2) + pow(y2-y1, 2));
2. d = sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1));
3. dx = x2-x1; dy = y2-y1; d = sqrt(dx*dx + dy*dy);

Unless your program must be able to perform millions of distance calculations per second (and some do), chose the solution which make the most sense to you, the programmer.  In other words, it's your personal preference (unless your instructor says otherwise).

Output Results

     This section of the algorithm tends to be the easiest to write, but the longest to translate into C++. You will find yourself making changes over and over again trying to make the C++ code output results that look like the textbook.

     To write this section, read through the textbook exercise and look for places that describe what must be output or displayed to the screen. For each thing that is output, list it here in this part of the algorithm.

Selection Statements

A selection statement means to chose an action based on a condition. An everyday example is the traffic light. If the light is red, I stop my car, otherwise if the light is green, I go.

In C++, selection statemens work similarly. If some value in memory meets some condition, perform this section of code, otherwise perform the other section of code. There are 2 C++ selection statement available:

1. If statements
2. Switch statements

Refer to your textbooks and lecture notes for the details of these. This guide will cover questions like, "Where do I put if statements," and "How do I use and if statement?"

When to use if statements

There's three basic times to use if statements:

1. Making sure some input value is valid
2. Chosing which calculation to perform
3. Deciding which values to output

Testing for valid input

When is the best time to check the data input by a user? Immediately after the program has attempted to input the value. Consider the following algorithm:

• Input data
  • Input the positive square value
    • Make sure the value is positive

Translating this into C++ looks like this (assuming a variable called "value" has been declared)

cout << "Enter a positive square value: ";

cin >> value;

if(value < 0)

{

cout << "Sorry, the value must be positive." << endl;

return 0;

}

One observation I see often is students attempting to make sure the value is valid before it has ever been input (that is, the if statement happens before the cin >> value statement.) This generally makes the compiler cry comething about uninitialized variables.

Another note: The textbooks have not yet covered anything that would allow your program to gracefully try again. At this point, it's still okay to make your program quit as soon as it encounters something wrong. Later chapters will cover how to make the program try again.

Selecting a calculation to perform

Lets say the program must perform different calculations based on the value of the input. If the input value is below 100, then calculate the square of the value, otherwise calculate the square root. Here's what the algorithm looks like:

• Perform calculations
  • If the input value is below 100
    • the output value equals the input value squared
  • Otherwise
    • the output value equals the square root of the input value

Now to translate that into C++

if(value < 100)

{

result = value * value;

}

else

{

result = sqrt(value);

}

You'll hear this many times: There's more than one way to solve it.  For the above C++ code, "No, since single statements follow the "if" and the"else", the curly braces aren't needed." Yes, I could have used the conditional operators ?: to shorten it down to

result = value < 100 ? value * value : sqrt(value);

but, most textbooks don't cover the conditional operator yet, and introducing it now might confuse students more than help them.

Choosing ouput

Sometimes you don't want your program to display certain output. Common examples are displaying the remainder in a division only when the remainder is non-zero. Consider the following problem statement:

Write a C++ program that prompts the user to enter the dividend and the divisor. If the user enters an invalid divisor, the program shall display an error message and terminate. The program shall output the quotient, and output the remainder only if the remainder isn't zero.

Here's the algorithm

• Allocate storage
  • dividend
  • divisor
  • quotient
  • remainder
• Input data
  • input the dividend
  • input the divisor
    • Make sure the divisor isn't zero.
• Perform calculations
  • calculate quotient
    • quotient is dividend divided by divisor
  • calculate remainder
    • remainder is dividend modulus by divisor
• Output results
  • output quotient
  • if remander isn't zero
    • output remainder

Here's the algorithm translated into C++ statements

// Allocate storage

int dividend, divisor, quotient, remainder;

// Input data

cout << "Enter the dividend: ";

cin >> divident;

cout << "Enter the divisor: ";

cin >> divisor;

if(divisor == 0)

{

cout << "Division by zero is not a valid math operation." << endl;

return 0;

}

// Perform calculations

quotient = dividend / divisor;

remainder = dividend % divisor;

// Output results

cout << "The quotient is " << quotient;

if(remainder != 0)

{

cout << " with a remainder of " << remainder;

}

cout << endl;

Loops

Loops can occur in the Input Data, the Perform Calculations, and the Output Results section of your algorithm.

Types of Loops

Count Controlled Loops - Looping when you know exactly how many times your code must be repeated.

Sentinel Controlled Loops - Loop until a special value is input.

End of File Controlled Loops - Loop until the end of a file is found.

Flag Controlled Loops - Loop until some value is set to true (or perhaps set to false).

Loops in Input Data

Sometimes you need to make sure the user inputs valid data. Lets say that the user must input a number between 0.0 and 1.0. If they enter a value outside of this range, they should be prompted to re-enter the value.

• input data
  • Loop until the user enters a value between 0.0 and 1.0

A common method to solve this problem looks like this:

• Prompt the user to enter a value
• Input the value
• Loop if the value isn't valid
  • Display an error message
  • Prompt the user to enter a value
  • Input the value
• End the loop

Translating it into C++ looks like this:

double value;

cout << "Enter a value between 0 and 1: ";

cin >> value;

while(value < 0.0 || value > 1.0)

{

cout << "Invalid value, must be between 0 and 1" << endl;

cout << "Enter a value between 0 and 1: ";

cin >> value;

}

Loops in Perform Calculations

Functions