Programming for Beginners

Minimum Value Algorithm

What would a reliable method of finding the smallest number on a paper full of numbers be?

We could try to find it this way: first, we would take out another piece of paper, a pencil and an eraser. To start out, we will pick a number from the first paper. Then, we copy it to the second paper, and, upon having done this we cross it out on the first paper.

We then pick a number that has not been crossed out from the first paper. If it is smaller than the number written on the second paper, then we replace the number on the second paper with the selected number from the first paper (we use the eraser to keep things cleaner). In any case, we also cross out the selected number on the first paper. In this manner, we can be sure that no number from the first paper will be skipped over. We repeat these steps until we have crossed over all the numbers from the first paper.

At the end, we should have the smallest number written on the second paper.

An elaborate description of a method for computing a particular result, like the description just provided, is called an algorithm. The algorithm described here is known as the minimum value algorithm.

We suspect that you have not been all that attentive while reading the description of this algorithm, because it does sound a bit convoluted. The best way to understand it is to take a piece of paper and write down any twenty numbers of your choice. Then you should follow the instructions of the minimum value algorithm that we have just laid out and see for yourself that you will end up with the smallest number. Do that now! On completion, you will have convinced yourself of both its validity and its simplicity.

This algorithm depends on a property that, at any given moment during its execution, the smallest of the crossed out numbers from the first paper will be written on the second paper. Should we at any subsequent step find a smaller number, then according to the algorithm, it will be written over the up-to-then smallest number on the second paper. This means that the highlighted property will always be satisfied: we will always have the smallest thus-far encountered number written on the second paper. When this algorithm is fully executed, all the numbers on the first paper will be crossed out, therefore, the smallest of all of them will lie written on the second paper.

But, how in the world are we to write down this algorithm in C++, since there we have neither papers, nor pencils nor erasers? Still, we do have variables. Assigning a new value to a variable amounts to erasing an old value and writing down a new value. As for the first piece of paper, we can think of it as a sequence of numbers to be read from standard input.

Let our problem be stated like this: Write a program that reads in 5 numbers from standard input and then prints out the smallest of those numbers to standard output.

In order to do that, we need two variables: the variable inputValue that will stand for the value being processed, which is a currently selected number from the first paper; and the second variable that will denote the only number on the second piece of paper, so it would be appropriate to name it minimum.

    double inputValue;
    double minimum;

How did that algorithm go again? Oh, yes, first we select one number, write it down on the second paper and cross it out on the first paper. That is the same as reading one number from standard input and assigning it to the variable minimum:

    cin >> minimum;

Proceeding further along, the algorithm says: select the next number from the first paper. Again, we should interpret that as reading a number from standard input. However, at this point we still do not know what to do with it, so we will just store it in the variable inputValue:

    cin >> inputValue;

"If it is smaller than the number on the second paper", says the algorithm – this might indicate an if statement. If what is smaller? Well, the selected number which has been stored in the variable inputValue. Smaller than what? Smaller than the number on the second paper, minimum:

    if (inputValue < minimum)

then we replace the number on the second paper by the selected number from the first paper – that would be an assignment:

        minimum = inputValue;

This assignment belongs to the if statement above, as it is a part of the sentence beginning with "if".

The algorithm says that we should repeat this, in our case, five times. We will then simply place the part to be repeated inside a for loop:

    for (double i=1;i<=5;i++)
        {
        cin >> inputValue;
        if (inputValue < minimum)
            minimum=inputValue;
        }

Behold, there is an if statement here as a part of a for loop. And, why not? A statement is a statement, like any other.

Finally, the algorithm says that at its conclusion, the smallest number will be found on the second paper. That means that once this for loop has done its work, the variable minimum will contain the smallest value. So, what are we to do with it? Well, we could write it out:

    cout << "The minimum is: " << minimum << endl;

That seems to be it. Let us just add a short message at the beginning of a program to inform the user what needs to be input:

#include <iostream>
using namespace std;

int main() 
{ 
    double minimum;
    double inputValue;    
    cout << "Please type in 5 numbers: " << endl;
    cin >> minimum;
    for (double i=1;i<=5;i++)
        {
        cin >> inputValue;
        if (inputValue < minimum)
            minimum=inputValue;
        }
    cout << "The minimum is: " << minimum << endl;
}

Running this program might result in:

Please type in 5 numbers:
231 
1005 
542 
177 
2048 
456
The minimum is: 177

This looks about right, except that there are six numbers read in from the standard input instead of five. It is another logical error that has slipped by, but this time quite an obvious one: the program already reads in one value before the for loop. To make this program correct, it will suffice to change the for loop so that the variable i ranges from 2 to 5.

Execute this program by hand now! Use the same numbers on the standard input as you have first used on a paper when following the description of the algorithm at the beginning of this chapter – and in the same order. Do you find the process of execution of this program by hand similar to the process of executing the algorithm as it was first described?