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:
Modern computers only add the requirement of performing logic, however, that doesn't change the basic algorithm.
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:
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.
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.
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)2 in C++ is pow(x2-x1, 2)
(y2-y1)2 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)2 in C++ is (x2-x1)*(x2-x1)
(y2-y1)2 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.
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?
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).
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.
