Algorithmic Thinking

Let's take our program modification one step at a time, starting with just the top two weights. Figure 4.1 is one possible way to handle this version of the problem.

Figure 4.1. Finding the top two weights, first try (codepump1a.cpp)

#include <iostream>
using namespace std;

int main()
{
  short CurrentWeight;
  short HighestWeight;
  short SecondHighestWeight;
  cout << "Please enter the first weight: ";
  cin >> CurrentWeight;
  HighestWeight = CurrentWeight;
  SecondHighestWeight = 0;
  cout << "Current weight " << CurrentWeight << endl;
  cout << "Highest weight " << HighestWeight << endl;

 while (CurrentWeight > 0)
  {
  cout << "Please enter the next weight: ";
  cin >> CurrentWeight;
  if (CurrentWeight > HighestWeight)
   {
   SecondHighestWeight = HighestWeight;
   HighestWeight = CurrentWeight;
   }
  cout << "Current weight " << CurrentWeight << endl;
  cout << "Highest weight " << HighestWeight << endl;
  cout << "Second highest weight " << SecondHighestWeight << endl;
  }

 return 0;
}

The reasons behind some of the new code, shown in bold, should be fairly obvious, but we'll go over them anyway. First, of course, we need a new variable, SecondHighestWeight, to hold the current value of the second highest weight we've seen so far. Then, when the first weight is entered, the statement SecondHighestWeight = 0; sets the SecondHighestWeight to 0. After all, there isn't any second-highest weight when we've only seen one weight. The first nonobvious change is the addition of the statement SecondHighestWeight = HighestWeight;, which copies the old HighestWeight to SecondHighestWeight, whenever there's a new highest weight. On reflection, however, this should make sense; when a new high is detected, the old high must be the second highest value (so far). Also, we have to copy the old HighestWeight to SecondHighestWeight before we change HighestWeight. After we have set HighestWeight to a new value, it's too late to copy its old value into SecondHighestWeight.

First, let's see how Susan viewed this solution:

Susan: I noticed that you separate out the main program { } from the other { } by indenting. Is that how the compiler knows which set of { } goes to which statements and doesn't confuse them with the main ones that are the body of the program?

Steve: The compiler doesn't care about indentation at all; that's just for the people reading the program. All the compiler cares about is the number of { it has seen so far without matching }. There aren't any hard rules about indentation; it's a “religious” issue in C++, where different programmers can't agree on the best way.

Susan: Now on this thing with setting SecondHighestWeight to 0. Is that initializing it? See, I know what you are doing, and yet I can't see the purpose of doing this clearly, unless it is initializing, and then it makes sense.

Steve: That's correct.

Susan: How do you know how to order your statements? For example, why did you put the "SecondHighestWeight = HighestWeight;" above the other statement? What would happen if you reversed that order?

Steve: Think about it. Let's suppose that:

CurrentWeight is 40

HighestWeight is 30

SecondHighestWeight is 15

and the statements were executed in the following order:

1. HighestWeight = CurrentWeight

2. SecondHighestWeight = HighestWeight

What would happen to the values? Well, statement 1 would set HighestWeight to CurrentWeight, so the values would be like this:

CurrentWeight is 40

HighestWeight is 40

SecondHighestWeight is 15

Then statement 2 would set SecondHighestWeight to HighestWeight, leaving the situation as follows:

CurrentWeight is 40

HighestWeight is 40

SecondHighestWeight is 40

This is clearly wrong. The problem is that we need the value of HighestWeight before it is set to the value of CurrentWeight, not afterward. After that occurs, the previous value is lost.

Susan: Yes, that is apparent; I was just wondering if the computer had to read it in the order that you wrote it, being that it was grouped together in the {}. For example, you said that the compiler doesn't read the {} as we write them, so I was wondering if it read those statements as we write them. Obviously it has to. So then everything descends in a progression downward and outward, as you get more detailed in the instructions.

If you wish, you can try out this program. First, you have to compile it by following the compilation instructions on the CD. Then type pump1a to run the program under DOS. It will ask you for weights and keep track of the highest weight and second-highest weight that you've entered. Type 0 and hit ENTER to end the program.

You can also run it under the debugger by following the usual instructions for that method.

Susan Finds a Bug

This program may seem to keep track of the highest and second highest weights correctly, but in fact there's a hole in the logic. To be exact, it doesn't work correctly when the user enters a new value that's less than the previous high value but more than the previous second-high value. In that case, the new value should be the second-high value, even though there's no new high value. For example, suppose that you enter the following weights: 5 2 11 3 7. If we were to update SecondHighestWeight only when we see a new high, our program would indicate that 11 was the high, and 5 the second highest. Since neither 3 nor 7 is a new high, SecondHighestWeight would remain as it was when the 11 was entered.

Here's what ensued when Susan tried out the program and discovered this problem:

Susan: Steve, the program! I have been playing with it. Hey this is fun, but look, it took me awhile. I had to go over it and over it, and then I was having trouble getting it to put current weights that were higher than second weights into the second weight slot. For example, if I had a highest weight of 40 and the second highest weight of 30 and then selected 35 for a current weight, it wouldn't accept 35 as the second-highest weight. It increased the highest weights just fine and it didn't change anything if I selected a lower number of the two for a current weight. Or did you mean to do that to make a point? I am supposed to find the problem? I bet that is what you are doing.

Steve: Yep, and I'm not sorry, either. <G>

Susan: You just had to do this to me, didn't you? OK, what you need to do is to put in a statement that says if the current weight is greater than the second-highest weight, then set the second-highest weight to the current weight (as illustrated in Figure 4.2).

Figure 4.2. Susan's solution to the bug in the first attempt

else { if (CurrentWeight > Second HighestWeight) Second HighestWeight = CurrentWeight; }

I hope you are satisfied.

Steve: Satisfied? Well, no, I wouldn't use that word. How about ecstatic? You have just figured out a bug in a program, and determined what the solution is. Don't tell me you don't understand how a program works.

Now I have to point out something about your code. I understood what you wrote perfectly. Unfortunately, compilers aren't very smart and therefore have to be extremely picky. So you have to make sure to spell the variable names correctly, that is, with no spaces between the words that make up a variable name. This would make your answer like the else clause shown in Figure 4.3.

Congratulations again.

As Susan figured out, we have to add an else clause to our if statement, so that the corrected version of the statement looks like Figure 4.3.

Figure 4.3. Using an if statement with an else clause

if (CurrentWeight > HighestWeight)
  {
  SecondHighestWeight = HighestWeight;
  HighestWeight = CurrentWeight;
  }
else
  {
  if (CurrentWeight > SecondHighestWeight)
    SecondHighestWeight = CurrentWeight;
  }

In this case, the condition in the first if is checking whether CurrentWeight is greater than the previous HighestWeight; when this is true, we have a new HighestWeight and we can update both HighestWeight and SecondHighestWeight. However, if CurrentWeight is not greater than HighestWeight, the else clause is executed. It contains another if; this one checks whether CurrentWeight is greater than the old SecondHighestWeight. If so, SecondHighestWeight is set to the value of CurrentWeight.

What happens if two (or more) pumpkins are tied for the highest weight? In that case, the first one of them to be encountered is going to set HighestWeight, as it will be the highest yet encountered. When the second pumpkin of the same weight is seen, it won't trigger a change to HighestWeight, since it's not higher than the current value of that variable. It will pass the test in the else clause, if (CurrentWeight > SecondHighestWeight), however, which will cause SecondHighestWeight to be set to the same value as HighestWeight. This is reasonable behavior, unlikely to startle the (hypothetical) user of the program, and therefore is good enough for our purposes. In a real application program we'd have to try to determine what the user of this program would want us to do.

Figure 4.4 shows the corrected program.

Figure 4.4. Finding the top two weights (codepump2.cpp)

#include <iostream>
using namespace std;

int main()
{
   short CurrentWeight;
   short HighestWeight;
   short SecondHighestWeight;
   cout << "Please enter the first weight: ";
   cin >> CurrentWeight;
   HighestWeight = CurrentWeight;
   SecondHighestWeight = 0;
   cout << "Current weight " << CurrentWeight << endl;
   cout << "Highest weight " << HighestWeight << endl;

   while (CurrentWeight > 0)
     {
     cout << "Please enter the next weight: ";
     cin >> CurrentWeight;
     if (CurrentWeight > HighestWeight)
         {
         SecondHighestWeight = HighestWeight;
         HighestWeight = CurrentWeight;
         }
     else
         {
         if (CurrentWeight > SecondHighestWeight)
             SecondHighestWeight = CurrentWeight;
         }
     cout << "Current weight " << CurrentWeight << endl;
     cout << "Highest weight " << HighestWeight << endl;
     cout << "Second highest weight " << SecondHighestWeight << endl;
     }

   return 0;
}

If you wish, you can try out this program. First, you have to compile it by following the compilation instructions on the CD. Then type pump2 to run the program under DOS. It will ask you for weights and keep track of the highest weight and second-highest weight that you've entered. Type 0 and hit ENTER to end the program.

You can also run it under the debugger, by following the usual instructions for that method. When you are asked for a weight, type one in and hit ENTER just as when executing normally. When you enter a 0 weight, the program will stop looping and execution will take the path to the end }.

By the way, since we've been using the if statement pretty heavily, this would be a good time to list all of the conditions that it can test. We've already seen some of them, but it can't hurt to have them all in one place. Figure 4.5 lists these conditions, with translations.

You may wonder why we have to use == to test for equality rather than just =. That's because = means “assign right hand value to variable on left”, rather than “compare two items for equality”. This is a “feature” of C++ (and C) that allows us to accidentally write if (a = b) when we mean if (a == b). What does if (a = b) mean? It means the following:

Some people find this useful; I don't. Therefore, whenever possible I enable a compiler warning that tells you when you use = inside an if statement in a way that looks like you meant to test for equality.

Even a Simple Change to a Program Can Cause Errors

I hope this excursion has given you some appreciation of the subtleties that await in even the simplest change to a working program. Many experienced programmers still underestimate such difficulties and the amount of time that may be needed to ensure that the changes are correct.^[1] I don't think it's necessary to continue along the same path with a program that can award three prizes. The principle is the same, although the complexity of the code grows with the number of special cases we have to handle. Obviously, a solution that could handle any number of prizes without special cases would be a big improvement, but it will require some major changes in the organization of the program. That's what we'll take up next.

^[1] There is a book called Refactoring: Improving the Design of Existing Code (ISBN 0-201-48567-2) that is very helpful to programmers with some experience who want to improve their ability to modify programs without introducing new errors. Reading this book has changed my attitude toward maintenance from distaste to interest.