The user will enter these values one at a time and end with a -1 to indicate that there are no more prices to discount.

Remember how we do a trace. Step 1 is to make a column for each variable and put in 'garbage' (a question mark( - or the variable's initial value if it has been initialized. Our trace for this algorithm then starts as follows:

Step 2 is to walk through the algorithm executing each instruction, being careful to do only what the algorithm says - no more, no less. In other words, don't do what you want to be done but what the instructions say is to be done.

The first instruction of our loop asks us (as the computer) to compare the value in 'Price' with -1. When we retrieve the contents of 'Price', we find that it holds garbage. OOPS! This means that 'Price' could have ANY value including -1. If it accidentally had a -1 as its value, the loop would stop before we had a chance to enter any values. Clearly, we have a problem! As a matter of fact, any time an algorithm attempts to use the value of a variable holding garbage there is a problem!

But let's assume that we don't have a problem here and see if everything else is OK. The first time through the loop the user enters $10 and the Discounted Price is $8.70 so our trace looks as follows:

Looks good so far. The computer returns to the top of the loop to run again the test that decides if the loop is finished. This time 'Price' has the value 10, which is not equal to -1, so the instructions inside the loop are executed again. The user enters $100, the Discounted Price is calculated and the trace becomes:

Again, all is OK and again the computer returns to the top of the loop and compares 'Price' with -1. 100 does not equal -1 so the loop is entered again and this time the user enters -1. This means the loop should stop but note that the next instruction after

has nothing to do with deciding if the loop should be discontinued. Yes, you and I know that the loop should stop but the computer doesn't. (Remember the warning to do what the instructions say when tracing, NOT what we want to have done.) So, the computer calculates the discount for a price of -1 dollars and even outputs that price. The trace contains:

It's not so bad that the computer calculated the bogus discounted price but when it outputs a price of $-0.87, our program looks silly. Of course, the user can be told to ignore the final output and things will be OK but the program won't really be right and it certainly won't get much respect.

We have discovered that our algorithm has two problems. First, the first time through the loop the memory location symbolized by the variable 'Price' just might contain the value -1 in which case our program will terminate before it even gets started; and second, the final output will always be the strange $-0.87. Our algorithm needs to be fixed.

The problems actually are related. The cause of the first problem is that there is no input before the test condition in the while loop. The cause of the second problem is that the test condition is not executed right after the input is entered. It is this failure to test the value of the input immediately after it is entered that allows the system to calculate and output a discounted price for a 'price' of -1. Perhaps we need to rearrange the order of the input and test condition. The first thing we could do is move the input so that it takes place before the loop - to guarantee that 'Price' has a value before it is tested. Such a 'read instruction' is called a priming read. Here is the code:

Get Price
while Price != -1
{
Discounted Price = Price * Discount
Output Discounted Price

}

Now, we are assured that there is something valid in 'Price' before we execute the while loop test condition. However, do you see the problem? If not, try running a trace on this - what happens?

Hopefully, you have discovered that we have an infinite loop - the contents of the memory location symbolized by the variable 'Price' will never change so the 'Price' will never equal -1 (unless that was the first value entered) and the loop will never stop! OOPS!!!

Now, we could copy 'Get Price' back where it was and have the code:

Get Price
while Price != -1
{
Get Price
Discounted Price = Price * Discount
Output Discounted Price

}

Again, there is a problem. Take a moment to look at it and if you do not see it, try tracing the algorithm. If you still don't see the problem, compare your trace with one done for you

Now you realize that the problem is that the first price will not be discounted since it is read before the loop and another 'Get Price' is executed before the line:

is executed. So, what do we do? We can't remove the priming read line "Get Price' before the 'while' loop begins or we are back to problem number one and there must be a 'Get Price inside the 'while' loop or we have an infinite loop. The answer to this quandary lies in noting two things:

1. We want the discount price calculation to take place before the second price is read in

2. 'Get Price' should be executed just before the 'while' loop test condition is executed. (Remember that the reason the value -1 is being treated as a price is that the test condition is not executed right after the input.)

Putting these two facts together provides a hint as to where 'Get Price' should be inside the 'while' loop - at the bottom of the loop!

Get Price
while Price != -1
{
`Discounted Price = Price * Discount
Output Discounted Price
Get Price

}

You may resist this idea but if you trace it, it does work. This approach works for all problems where the user enters a sentinel value to indicate the end of input. We therefore have our first pattern - expressed as a very general algorithm.

Pattern Name: The While Loop with Priming Read


	Purpose: 	To loop through a set of instructions until the user
			enters some sentinel value


	Pattern: 	Get value(s) from the user for the variable(s) in the
	                 test condition
          
			while the test condition is true 
			{
				Do some set of instructions
				Get value(s) from the user for the variable(s) in the
	                         test condition
			}

We can use this general algorithm or pattern to write a more specific algorithm for any problem involving user input and a loop that ends with a sentinel value input by the user. In fact, that is how the correct algorithm (a few paragraphs above) for the discounted price calculation was written. Here we repeat the algorithm and compare its instructions with the general instructions found in the pattern:

Once you have an algorithm in a form that is both correct and close to what a computer needs, it is easy to translate that algorithm into code. Below is the C++ code for the "Friday the 13th" Problem. Make sure you understand how all the lines were coded.

// A program to calculate sale prices based on a single discount percentage 
// File: ch3prg1.cpp

// THE SPECIFICATIONS 

#include <iostream.h>

const
	double DISCOUNT = .87;

void main()
// Purpose: 	to calculate sale prices based on a single discount percentage
// Receives:	NONE
// Returns:	NONE
	
{ 	  
	double price;
	double discountedPrice;
	      
        cout << "Please enter an item's original price (Enter -1 to Stop) ";
        cin >> price;

        while (price != -1) 
	{
           	discountedPrice = price * DISCOUNT;
     		cout << "The New Price is: $" <<  discountedPrice << endl;
              	cout << "Please enter an item's original price (Enter -1 to Stop) ";
             	cin >> price;
        }
}

You will be assigned many programs of this type, both in this course and in any future programming you do. Take advantage of this pattern. After you have coded for awhile, this pattern (and the other patterns we are about to learn) will become second nature to you and you won't need to specifically review them each time you code. For now, however, while the idea is still new to you and you are likely to forget some aspect of the algorithm, always review this pattern and the other patterns below before starting to code.

Top of Section

Main Menu

Next Section