We noted earlier that programming can be a very complex task and
that a number of tools have been developed to make that complexity
more manageable. As you were struggling to write your homework
from last chapter you may have wished you had some of those tools.
And, you can be assured that they were used in the course of writing
the example code found in that chapter. Now that you are crying
out for help it is time to provide some.
There are four phases or tasks in developing a program:
We have talked a bit already about coding , compiling, debugging and testing and will talk much more about them in the rest of this text. This chapter focuses on analysis and some of the simplest aspects of design. These two steps, analysis and design, are so important that many texts don't discuss any code at all until after exploring them in detail. Hopefully, you have a small sense of their importance from your struggles both to understand the code you have read and to write your own programs. Before proceeding to the discussion of analysis there are three general points to note:
I. The Analysis Phase
Before you can write a program, you need to have a clear understanding
of what is required of the program including:
Questions like this constitute the first phase of programming,
the Analysis Phase. The second or design phase builds
on this first phase.
The analysis and design phases of a programming task can often
blur. For us, in this course, the analysis phase will consist
of describing the problem to be programmed and stating the requirements
of the problem. Specifically, the analysis phase seeks to discover:
-any screens introducing or describing the program to the user;
-input requests (also called prompts) - two examples:
-the form the outputs will take - text, files, graphics etc.
It needs to be stressed that at this point we are NOT concerned
at all with HOW the program will do what ever it is supposed to
do. Our goal is to develop a clear, precise understanding of what
the program is to do. It obviously does not make a lot of sense
to start writing code or even designing a program before one is
clear on what the program is to do.
The first step in the analysis process is to write a narrative
description of the programming problem. Such a narrative should
describe IN GREAT DETAIL what the program will be expected
to do and describe in general what type of interface the program
should have - how user's will interact with the program.
The second step is to use the narrative to determine more precisely
the interface of the program. As noted above the interface
includes introductory and descriptive screens,
title and welcoming screens, as well as the inputs
to the program and outputs from the program. The notion of an
input implies that some value is entered into the program from
the 'outside' while an output implies that some value is sent
out of the program. Such values have to somehow be stored inside
the computer after they are input or before they are output .
For this we use the 'variables' that we discussed in chapter two.
We also discussed there that variables have a form or type and
therefore any description of inputs and outputs should state their
type - whether they are characters, strings, integers, doubles
or some other type - AND where they are coming from: a file, the
keyboard, the mouse, etc. If an input is coming from the keyboard,
there should be a description of how it will be requested - what
prompt(s) or message(s) will appear on the monitor to tell the
user what information is expected and when to enter it. If the
input is to come from a file, the format or organization of the
file should be defined.
At this point you may be scrambling to find out HOW to write the
code to handle strings as input or how to get input from a mouse
or how to write to a file. Remember, however, that we are not
concerned here with HOW. Problem analysis can be done by people
who are not programmers. Try your best to avoid 'how questions'
at this point. Just assume that whatever wonderful design you
come up with, you or someone else will be able to, sooner or later,
implement it as code.
The third step in the analysis process is relatively simple -
use the narrative again to determine if there are any constants
in the problem. These should simply be listed along with their
purpose. Remember, a constant is a value that remains the same
throughout a program. It is not that constants NEVER change. A
tax rate might be an example of a constant. Tax rates change in
the course of the political process but one does not change a
tax rate in the middle of the run of a program. When you go into
a store you do not expect that the first five items you buy are
taxed at 6% and the rest at 6.5%.
The end result of this effort is a detailed problem description
and a set of specifications. To demonstrate this process
we will use the employee problem coded as program 7 in chapter
2. Of course, the way we are proceeding here is backwards.
The specifications should always be completed before the coding
begins. As noted, some texts do not show any code until after
analysis and design have been discussed. Hopefully, however, by
having seen a bit of code, you have some sense of what it is we
are aiming for in the analysis process. So, as any good parent
would say, "Do as we say, not as we do". In other words,
from here on always perform the analysis and design stages before
coding.
Before proceeding, one more word of caution. Simple problems such
as this employee program often require a simple analysis. The
results hardly seem worth all the formal effort expended. Don't
let the simplicity of the analysis here lead you to believe that
the analysis phase is not important. In real world problems the
analysis phase can take six months, a year, or even longer and
be much too complex for anyone to maintain in their head. Ultimately,
you will not need to go through the analysis process on the types
of problems presented in these early chapters but by practicing
on 'easy' problems you will hopefully be prepared for more complex
systems analysis.
So, here is a possible narrative for the employee problem.
This is a good start - it certainly seems to provide a good amount
of detail for such a simple problem. Still, it is not quite detailed
enough. The analysis phase can be simple or complex depending
both on the complexity of the problem and on how clearly the programming
task is understood and described by those requesting the program.
Often the users (requesters) of a program do not have a good sense
of what they want in a program. At other times they may have a
good sense of this but be unable to express it. In either case,
it is the task of the programmer analyst to develop a precise
description of the program and its specifications.
The problem narrative just written provides an example of this
in that it has no description of the required interface. There
is no information upon which to base the second step of the analysis
phase - the designing of the interface. If you were given this
problem narrative and asked to design an interface, you would
be wise to ask a few questions of potential users, come up with
your own ideas, and then show them to those who want this program
- before you write any code. In a real world programming task
a smart analyst would create an interface specification and show
it to whomever is requesting the program before going to the design
or coding stage. This will guarantee that what the programmers
are working on is really what the 'requester' wants.
In this example (and still working backwards) we will start with
the relatively simple interface shown in the code for program
ch2prg7. We have, however, improved somewhat on that initial
interface. For example, as implemented in chapter two, this program
has no introductory screen. One is added here because most real
programs have one or many opening/introductory screens.
Read carefully through the interface analysis below. Be sure you
understand it before proceeding. Words enclosed in angle brackets
(<...>) represent possible program variables. At this point,
the exact names of the variables as used in the analysis are not
important. When you are finished, read over and run the code that
corresponds to this analysis
Interface:
An Introductory Screen:
An Exit Screen:
Inputs:
All inputs come from a user at a keyboard.
1. Prompt : "Please enter your rate of pay."
Input: < rate of pay> double
2. Prompt: Please enter the hours you worked this week"
Input: < hours worked> double
1. "This employee's salary is: < salary>
The final step is to look for and record any constants. A program
narrative may not include this information and you may have to
ask yourself just what information is needed to compute the outputs
required according to the interface. (Note that we are not saying
that you need to determine exactly HOW the outputs are determined
but rather, what information is needed.) In this example, the
program narrative is more helpful. Note that it mentions two numbers
that do not seem to change as the employee information changes
- the numbers of hours that determine when overtime begins (40)
and the factor to multiply by to get the overtime pay rate (1.5).
These are, of course, the numbers declared as constants in the
actual program - and they better be because the analysis and the
code should match! The next part of the formal analysis is written
this way:
Constants:
Below we put the whole thing together and make a few comments:
/*
This program is to compute the salaries of ten employees who
are paid by the hour with the possibility of earning overtime
pay. Each employee will have a rate of pay and the hours worked
during the pay period . An employee's salary is calculated by
multiplying the rate of pay by the hours worked. If the hours
worked is greater than 40, the salary is calculated by multiplying
the first 40 hours by the rate of pay and the number of hours
greater than 40 by 1.5 times the rate of pay. After being calculated,
the salary of each employee will be immediately output to the
screen.
Interface:
An Introductory Screen:
An Exit Screen:
Inputs:
All inputs come from a user at a keyboard.
1. Prompt : "Please enter your rate of pay."
Input: < rate of pay> double
2. Prompt: Please enter the hours you worked this week"
Input: < hours worked> double
1. "This employee's salary is: < salary>
Constants:
First, observe the use of the characters '/*' to open this material
and '*/' to end it. This material is meant to go at the very top
of your program file, just after the line that states the name
of the file containing this code. We have already seen that two
slashes (//) indicates that the following code is to be ignored
by the compiler as it does its translation. When you have a multi-line
comment you can use '//' at the beginning of each line or you
can begin the long comment with '/*' and end it with '*/'. That
is exactly what was done above. Since the analysis phase for our
relative simple programs usually results only in a page or so
of text, we shall include the analysis in our code. For real world
problems the analysis may full 100's of pages and is kept separate
from the program although a summary may be included with the code.
Second, note that the words inside the angle brackets (<....>) represent sets of characters that could be turned into C++ style variables but, as written, they are not variables - there are spaces between words. At this point you are writing an analysis of a problem. When it becomes time to turn this into code, one could use any appropriate language. (Technically, the comment marks discussed above are not part of the analysis. They are only included here to show you how to include the analysis in the programs we will be writing.)
That ends our discussion of the analysis phase. To repeat one
more time: the specifications for this program are quite simple.
Having seen such a simple example, you will be tempted to skip
the specifications writing step or do it as fast as possible.
Try to avoid that temptation. Trust in the experience of past
programmers. These steps can truly save you time later on. It
is true that for a simple task, these steps will appear to be
a waste of time but you need to practice these steps on easy tasks
so that you can easily apply them to complex tasks.
II. Algorithms - One Component of the Design Phase
We now have a general idea of 'what' our program should do to
accomplish its task and it is time to move on to 'how' that task
should be accomplished and some initial discussion of design.
Some of you may be thinking, "Ah, good, now we jump into
the code." Not so fast! There is nothing worse than writing
code before you have taken the time to design the code you are
going to write.
Programming problems always involve two components:
2. A set of actions involving the objects, for example:
The complexity of whatever part of the world (real, or imaginary
) we are attempting to model in a program is reflected in the
interactions among the objects modeled in the program. As a programmer
you must have a good handle on that complexity before you proceed
to coding. Humans almost always handle complexity using a divide
and conquer strategy. We break down or decompose complex problems
into easier, more manageable components. Later, we will discover
that there are two basic approaches in the programming world to
this decomposition process. One can focus on the objects in the
problem environment and examine each object separate from others.
Or, one can focus on the actions/tasks involved in a problem and
focus on each task separate from all others. At present, however,
we are not ready to handle any real complexity. Instead, we will
focus on problems that are so simple as to have only one object
and only one basic task. A caution is in order - in reality even
these problems can be further decomposed but let's pretend otherwise
for the moment.
The amazing thing is that even with programming problems this
simple it is unwise to simply start coding. You still have to
make sure that you know how to accomplish the task - after all,
how can you tell a computer how to solve a problem if you do not
know how to solve the problem yourself. Your first goal then is
to come up with some general plan or description for solving the
problem and then express that plan in a systematic way. In other
words, your goal is to state clearly and in order the exact steps
necessary to accomplish the task/problem . The basic steps for
a task represent an algorithm for the task.
Formally, an algorithm is:
Good recipes, especially those written for beginners, can be considered
algorithms. They are step by step descriptions for solving the
problem of preparing some kind of food.
Whenever you write instructions for someone else, you need ask
yourself, what can I leave out. In other words, how much does
the person already know and how much detail must I provide. For
example, in a cookie recipe, do you need to tell the person to
grease the cookie sheet? The answer is an emphatic 'YES' if you
are writing for someone like at least one of the authors of this
text! You should provide all possible details and you should do
so in as simple a language as possible. .
The same is true for computer based algorithms - algorithms that
will be turned into code in some programming language. Computers
assume nothing. They do not perform any action they are not explicitly
told to perform. In addition, the instructions they perform are
simple and programming languages such as C++ tend to reflect that
simplicity. For that reason algorithms should be written in simple,
concise English. - no compound sentences, no skipping of details.
Think of yourself as writing instructions for a ten year old who
can read, knows the basics of arithmetic and can follow instructions.
In addition, to keep your algorithms as general as possible, try
to avoid writing your algorithms for a specific language such
as C++.
Our First Algorithm
Let's start by writing the algorithm for the sixth program from
chapter 2
- the program to calculate the salary for one
employee. Yes, this is a simple program and yes, we are working
backwards by having, in fact, already written the code, but let's
pretend that the program is more complex and that we have not
yet written the code. The first step, of course, is to do an analysis
- something that we have essentially already done in the previous
section. For the moment we will ignore that part of the analysis
that talks about opening and closing screens and about processing
more than one employee. Here is how the algorithm might look:
Get the Rate of Pay for the employee
Get the Hours Worked for the employee
if Hours Worked is greater than 40
{
Regular Salary = 40 * Rate of Pay
Overtime Rate of Pay = Rate of Pay * 1.5
Overtime Salary = Overtime Rate of Pay * (Hours Worked - 40)
Full Salary = Regular Salary + Overtime Salary
}
else
{
Full Salary = Hours Worked * Rate of Pay
}
Output the Full Salary
Compare this with the actual code and you will discover
a number of points. The algorithm goes through the same steps
as the code but it is not written as C++. There are no variable
declarations, the rules for variables are not followed, it uses
words like 'get' and 'output' that are clear English but not part
of C++ and it does not include some of the peculiarities
of C++ syntax.
Also, the algorithm does not worry about special points such as
constants. Actually, we could have written this algorithm with
names such as REGULAR HOURS and OVERTIME ADJUSTMENT for the values
40 and 1.5 respectively and it would have been more general. That
would improve the algorithm. On the other hand, programming languages
include constants to allow programs to be easily modified. At
the algorithm development stage, such considerations are not important.
In this case, it was decided to not to include constants simply
to make the algorithm easier to read.
If we had not yet written the code but had carefully worked out
this algorithm, it would be easy to now translate this algorithm
into code. Each variable and constant would be appropriately declared;
the Get instructions would be turned into the appropriate pair
of cout and cin instructions; the 'if' statement would have been
written with the arithmetic instructions inside it; and the output
instruction would have been translated as cout..... The moral
of the story is,
But, how does one come up with a correct algorithm, one that captures
all the essential steps in the correct order AND is written in
a way easily translated into a programming language. The answer
has three parts. First, one must know how to solve the problem
independent of any computer considerations. That is an issue in
general problem solving and will not be discussed here. We shall
assume that you could solve any of the problems in this text with
paper and pencil if you had to. If you cannot, please consult
another book or someone who does know how to solve the problem.
Please, NEVER try to write code for a problem that you cannot
do yourself without a computer. PLEASE!
Second, one must have a sense of what happens when instructions
are executed on a computer. As you write each instruction in an
algorithm you need to ask yourself:
Computers have what is called a state which includes:
Each instruction modifies one or more elements of the state. Instructions
that include the assignment statement (=), modify or change memory;
'if' statements may cause the computer to jump to a completely
different set of instructions; Output (cout) instructions modify
what is on the monitor. The purpose of an instruction can be described
as the modification of the state of the computer in some way.
The goal can be described as the state of the computer AFTER the
instruction is executed. Let's add 'Purpose and Goal' statements
to our salary algorithm.
Purpose: To get the rate of pay for an employee from the user
Goal: The variable Rate of Pay has the rate of pay
Get the Rate of Pay for the employee
Purpose: To get the hours worked for an employee from the user
Goal: The variable Hours Worked has the hours worked
Get the Hours Worked for the employee
Purpose: To decide if the employee has worked overtime
Goal: The program counter will be pointing to the appropriate
set of instructions to determine
the salary
if Hours Worked is greater than 40
{
Purpose: To calculate the overtime rate of pay
Goal: The variable Overtime Rate of Pay holds the overtime
rate of pay
Overtime Rate of Pay = Rate of Pay * 1.5
Purpose: To calculate the overtime salary
Goal: The variable Overtime Salary holds the overtime salary
Overtime Salary = Overtime Rate of Pay * (Hours Worked - 40)
Purpose: To calculate the full salary of the employee (overtime
and regular)
Goal: The variable Full Salary holds the full salary of the
employee
Full Salary = Regular Salary + Overtime Salary
Purpose: To output the employee's salary to the screen
Goal: The screen displays the employee's salary.
Output the Full Salary
This sure is full of redundancy isn't it! In essence we have a
series of checks and balances here. (Remember your high school
civics class?) The goal captures the purpose and the instruction
captures both the purpose and the goal. If the goal and the instruction
you write are redundant to the purpose and the purpose is the
correct purpose for this point in the algorithm, then the instruction
is correct. Because writing out algorithms in this redundant format
can be so tedious, we will not do it often. However, to get you
used to thinking carefully about the meaning and purpose of instructions,
you may be asked to follow this "Purpose, Goal, Instruction"
format in the problems at the end of the chapter.
III. Patterns
Back a few paragraphs we said that there were three parts to developing
a correct algorithm. The first two were
Now we discuss the third part. It turns out that computer-based
solutions to certain problems don't always take the same form
as human oriented solutions. And, even when they do, there are
often ways of phrasing the solution in algorithmic form that are
easier to translate into code. A simplistic example: Suppose we
had written the 'if' part of the algorithm above as:
When the Hours Worked is greater than 40 Regular Salary = 40 * Rate of Pay Overtime Rate of Pay = Rate of Pay * 1.5 Overtime Salary = Overtime Rate of Pay * (Hours Worked - 40) Full Salary = Regular Salary + Overtime Salary Otherwise Full Salary = Hours Worked * Rate of Pay endwhenTo an English speaker, this means the same thing as the above algorithm but it may not be clear to a novice programmer that "when....otherwise" is translated as 'if...else'. More important there are times when a computer algorithm must include details that would never be included in a set of instructions meant for a human.
Consider the program from chapter 2 to calculate the sum of 10 numbers . Instructions given to a human for this problem would be something like:
However, this is not at all how a computer solves this problem
- as you can see from looking at the code for program 4 of chapter
2. Therefore, translating from the algorithm we just wrote
into C++ code would be a difficult task. A more 'computer friendly'
algorithm for this problem might look as follows:
Set the Sum to 0 Set the Count to 0 While the Count is less than 10 Get a Number from the user Add that Number to Sum Add 1 to Count EndWhile Output the SumA number of elements make this algorithm different. Humans would never be told to 'initialize' some memory location - which is what the first two steps do. A computer must be explicitly told this. Humans implicitly repeat a set of steps, (execute a loop) while computers need explicit information about how many times to loop and what instructions are part of the loop. No wonder then that programming can be a difficult process for the novice:
You WILL learn how to write easily translatable algorithms as
you learn how to code but in the meantime you need an aid in writing
good algorithms. It turns out that there are a number of general
patterns or templates that underlie many common
coding problems. Expert programmers simply 'know' these and use
them in developing their algorithms . These patterns represent
the general form your algorithms should take when faced with certain
classes of problems. The rest of this chapter discusses a number
of these patterns and provides coding examples based on these
. You are strongly advised to study these carefully and use them
when you begin a new programming problem. They are meant to guide
you in the design process and to help you avoid having to 're-invent
the wheel' every time you start a new program. (For those simply
wanting a summary of the patterns themselves, a separate document is provided.)
A. The "While Loop with Priming Read" Pattern
We will start first with one of the 'while' loop patterns. Suppose
you are a sales clerk in a store. The store wants to have a "Friday
the 13th Sale" where the price of "selected" items
is reduced by 13%. You have the job of figuring out the new prices.
You know that the new price equals the old price times .87 (1.00
- .13) but this is ugly math and you want to automate the process.
How about writing a program that allows you to enter each price
after which the computer displays the new price.
If you think about it for a moment you realize that the program
will include some kind of a loop - to allow it to repeatedly calculate
the new price. But, how will the computer know when to stop looping?
You could count the number of selected items to be discounted
and have the computer loop that many times but there are two problems
with this. First, if a large number of items have been selected,
it could take awhile to do all the counting and your goal is to
save time not take more time. Second, what if the manager adds
or deletes items from the sale after you have made your count
but before you are finished writing and running your program.
You do not want to have to rewrite your program.
Usually in situations like this, the algorithm is designed so
that the user (in this case, you will be both the programmer and
the user of the program) has some way to signal to the computer
when he or she is finished entering data. How about deciding that
the user will enter a -1 (since no item costs less than 0 dollars)
to indicate that there are no more items to discount.
Values that indicate that some loop should terminate are called
sentinel values. In this case '-1' is a sentinel value.
Sentinel values such as -1 can also be viewed as stopping conditions
since they represent the conditions under which the loop should
stop. Loops that involve such sentinel values or stopping conditions
are very common and we can generalize the purpose of such a loop
as follows:
So, how do we put together an algorithm to accomplish such a purpose?
One might be tempted to write the following algorithm:
The user will enter these two values 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'. (If this were a trace of C++ code,
we would use values other than 'garbage' if the variables were
initialized when declared.) Our trace then starts as follows:
| Price | Discounted Price |
| ? | ? |
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:
| Price | Discounted Price |
| ? | ? |
| 10 | 8.70 |
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:
| Price | Discounted Price |
| ? | ? |
| 10 | 8.70 |
| 100 | 87.00 |
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:
| Price | Discounted Price |
| ? | ? |
| 10 | 8.70 |
| 100 | 87.00 |
| -1 | -.87 |
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 which 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:
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:
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:
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!
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 ReadThis algorithm implies that there can be multiple test conditions involving multiple variables. Usually, however, there will only be one of each. In the program presently under discussion 'Price' is the variable and "Price <> -1" is the test condition.
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(s) while all condition test(s) are true { Do some set of instructions Get value(s) from the user for the variable(s) in the test condition(s) }
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 for the discounted price calculation
was written. Compare the two:
| Get Price | corresponds to | Get a value from the user for the variable(s) in the test condition |
| Price <> -1 | corresponds to | all condition tests are true |
| Discounted Price = Price * Discount Output Discounted Price |
correspond to | Do a set of instructions |
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 WOULD GO HERE. #includeconst double DISCOUNT = .87; void main() // Purpose: to calculate sale prices based on a single discount percentage // Inputs: the original price of all items to be discounted // Outputs: the discounted prices // 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.
B. The Counter Pattern
Now suppose the manager wants to know just how many items were
discounted. Again, you could physically count them or you could
have the computer do the work for you. We noted above that humans
do not need to be told to initialize their variables but that
in certain circumstances computers do need to be told. A counter
is a good example of a variable that needs to be initialized.
(Actually, this does sometimes happen in the 'real world'. Imagine
that you have been given one of those 'clicker counters', the
kind where you push a little button every time you want to increment
the counter. Imagine further that you are employed at a large
discount store and told to stand in front all day using your 'clicker'
to count the number of customers that enter during the day. What
should you do first thing in the morning before you start counting?
Reset your counter to zero, of course!)
Anyway, computer counters need to be set to zero and the counter
itself needs to be incremented inside some kind of loop. Aha,
another pattern! And, here it is - in its most general form.
Pattern Name: The Counter Pattern Using a Loop
Purpose: To count the number of times a loop repeats; to implement a counter.
Pattern: Initialize the Counter Variable to 0 Use some loop pattern - see Sections 'B' and 'C' above Inside the loop pattern add the following code: Counter Variable++
Using this pattern we can modify the above algorithm to include
a counter
Set Item Count to 0
Get Price
while Price <> -1
Discounted Price = Price * Discount
Output Discounted Price
Item Count++
Get Price
EndWhile
Output Item Count
There are a number of important points to pay attention to here.
First, note that we are really using two patterns in this program
- the "While loop with a priming read" pattern and the
counter pattern. A number of the programs in chapter two, for
example, ch2prg7.cpp, took advantage of these]
two patterns although at the time we did not discuss it. Once
you learn other looping patterns you will also be able to use
them with the counter pattern. In any case, the mixing of patterns
is a part of the creativity of the programming process. And, the
more patterns you are comfortable with, the more creative mixing
you are capable of. But there are important issues in pattern
mixing. For example, note how part of the counter pattern (the
initialization phase) exists outside the loop while the increment
phase is inside the loop. You can't just mix the elements of two
patterns in any old way.
The second point to notice about this program is the placement of :
It must appear outside the loop or the output will be:
If you do not see this, as usual, TRACE it
And now that you are comfortable with the algorithm, here is the
code:
// A program to calculate a sale prices based on a single discount percentage and count the // number of items discounted // File: ch3prg2.cpp // THE SPECIFICATIONS WOULD GO HERE. FOLLOW THIS LINK TO SEE HOW #includeconst double DISCOUNT = .87; void main() // Purpose: to calculate sale prices based on a single discount percentage and count the // number of items discounted // Inputs: the original price of all items to be discounted // Outputs: the discounted prices // the number of items discounted // Receives: NONE // Returns: NONE { double price; double discountedPrice; int itemCount = 0; 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; itemCount++; cout << "Please enter an item’s original price (Enter -1 to Stop) "; cin >> price; } cout << itemCount; }
One question you might have is why didn't we initialize or somehow place a value into the variable 'discountedPrice' before beginning the loop? (If you observe, it is the only variable still holding 'garbage' at this point.) Well, suppose we had set it to 0 before the 'while' loop. Would that 0 value ever have been used? If you study a trace of this code (with this variable initialized), you will see that the answer is no! In essence the 'discountedPrice' is not used on the right side of a calculation, as part of a test, or as an output before it is calculated. This being the case, any value we initialize the variable to would be lost in the calculation:
before it was used. In other words, we could initialize the variable
but it would be a waste of time since the initializing value would
be lost.
Here is another example using the counter loop pattern, a code
fragment that could be used to count the number of times the user
chooses to enter a loop. Note that we would need to add code to
replace the comment line "/* other instructions inside the
loop */" before this code would do anything useful. That
is why it is called a code fragment- it is only part of, a fragment
of, some larger program. Try to read it without worrying about
the new C++ syntax that has been included.
int count = 0;
cout << "Enter 'Y' if you have more to do\n";
cout << "Enter 'N' if you are finished.\n";
cin >> answer;
while ((answer == 'Y') || (answer == 'y'))
{
count++;
/* other instructions inside the loop *
cout << "Enter 'Y' if you have more to do\n";
cout << "Enter 'N' if you are finished.\n";
cin >> answer;
}
Likewise a line that might be written:
could also be written as:
Second, the test condition is more complex. Its purpose is to
handle the fact that a user can enter either an upper case or
lower case 'Y'. What the test condition is saying is: "while
the character entered is an upper case 'Y' OR a lower case 'y'...."
continue the loop. The two vertical parallel lines (||) are the
symbol for 'OR'. It is what we call a logical operator.
There are two other very useful operators of this kind: '&&'
is the symbol for AND while '!' is the symbol for NOT. All three
of these can be used in any 'if' or 'while' test condition.
Their meaning is the same as in English. Therefore, "||"
means that if EITHER of the individual conditions ("answer
== 'Y'" or "answer == 'y'", in this code) are true,
then the test as a whole is true. "&&" means
that both conditions must be true - which would not make sense
in this case since the memory location symbolized by 'answer'
cannot contain 'Y' and 'y' at the same time. '!' means Not. In
other words, if "answer == 'Y'" is True then "!(
answer == 'Y')" would be False. Note one can have multiple
'||' operators in an expression in which case, if any one of them
is True, the combined expression is True. Likewise, you can have
multiple '&& operators in an expression, in which case,
only if all of the individual expressions is True, is the whole
expression True. The issue of when and how to use and combine
AND,s (&&), Or's (||) and NOT's (!)is very tricky. You
should avoid mixing these unless you absolutely need to and are
comfortable with logic. Chapter 6 has more discussion
on how to decide when to use '&&' and when to use '||'.
Note the extra set of parenthesis in the test condition. They
are technically not required but they do make the code easier
to read. To see why they are not needed we need to understand
that logical operators (||, &&, and !) also have
precedence rules just as arithmetic operators do. As a matter of fact all operators are part of the same precedence
order. Here is the precedence table for all the operators we have
seen so far:
Note that both "&&" and "||" occur
below "==" in precedence. In other words, in a line
such as:
the "==" operator (in both places) is executed before
the "||" operator even without the parenthesis - which
is as it needs to be for this to make sense. In other words, the
system determines the truth of both equality tests and then does
an OR operation because '==' has higher precedence that '||'.
If either of the tests returns True, the whole expression is True
so in this case, if 'answer' contains 'Y' or 'y' the expression
is True. (If the precedence of "||" was higher than
"==", this code, without the extra set of parentheses,
would be asking the computer to do an OR on 'Y' and 'answer' -
whatever that would mean!)
As a separate point, note that the '+' and '-' symbols appear
twice in this table: in lines 2 and 4. In line 2 the '+' and '-'
refer to the unary plus and the unary minus as in
+5 and -5. Unary, of course, means 1 and in these two expressions
there is only one value or operand. Contrast that with "3
- 5" or "value1+value2" where the '+' and '-' operators
operate on two values or operands. In this case, '+' and '-' are
binary operators. This particular precedence difference is rarely
an issue in C++ so you can stop worrying about it but you should
understand the basic difference between unary and binary operators.
This whole discussion was related to the Counter Pattern so a
brief summary is in order.
Initialize the Counter Variable to 0
Counter Variable++
int itemCount = 556;
C. The Sum Pattern
Pattern: Initialize the Sum variable to 0
Use some loop pattern - see Sections 'B' and 'C' above
Inside the loop pattern add the following code:
Sum variable = Sum Variable + Amount To Add
The next pattern to become familiar with is closely related to
and often used in conjunction with the counter pattern. Often
we need to get a sum of some set of numbers. For example suppose
the manager of the store wants to know the total of the discounted
prices. As one might suspect, the pattern to accomplish this summing
behavior is quite similar to the counter pattern. First, one must
initialize to 0 the variable that will hold the sum, then one
must read in the numbers to be summed and add them to the sum
variable. Here is the general pattern:
Pattern Name: The Sum Pattern Using a Loop
Purpose: To calculate the sum of some set of numbers.
Using this pattern we can create an algorithm to add up all the
discounted prices
You may have already figured out just by reading this that the
Total Discounted Price is calculated by determining each individual
discounted price each time through the loop and then adding that
amount to whatever value is already in Total Discounted Price
variable - again, each time through the loop. That is why this
variable needs to be set to zero. You should also note that, as
with the counter pattern, there really are two patterns here and
the output of the total is after the while loop. Were it to be
placed inside the loop, the user would see the total continuously,
as it was being updated.
If any of this is unclear, you are strongly urged to trace the
algorithm.
Try moving around or deleting various lines in the algorithm and
see what happens when you trace.
Let's make the problem a bit harder before we translate the algorithm
into C++ code. Suppose the manager of the store wants to know
the total amount that was discounted - the difference between
the total original price and the total price after the discount.
One way to accomplish this, as hinted by the very description
just given (an advantage in writing a clear problem description
as part of the analysis phase) would be to add up all the original
prices, add up all the discounted prices, and calculate the difference.
Here is the modified algorithm:
As you can see, we now have two total variables. An algorithm can have as many as it needs. Also, each total/sum calculation can occur anywhere inside the while loop as long as the value to be summed has already been calculated or somehow entered into the appropriate variable. In this case, we could have moved the line:
to the very top of the 'while' loop - just after the "while
Price <> -1" line. Of course, it could not be the last
line in the while loop because we would then have lost the first
price and at the end we would be adding -1 to the total. (If this
is not clear, you know what to do.)
The other summation line could be placed anywhere inside the loop
after the line that calculates the Discounted Price. Note that
'Total Discount' must be calculated after the 'while' loop but
it could be placed anywhere from the end of the loop to just before
its output line. What you are discovering here is that a particular
line of code does not have only one spot in which it can be placed.
On the other hand, there is usually some limit to where it can
be placed. There is more than one way to write a program but there
are definitely 'wrong' ways.
The translation of this algorithm into C++ is straight forward.
As a reminder, however, remember that "X = X + Y" can
be translated as "X += Y".
// A program to calculate sale prices based on a single discount percentage and output the // difference between the original price total and the discounted price total. // File: ch3prg3.cpp // THE SPECIFICATIONS WOULD GO HERE. #includeconst double DISCOUNT = .87; void main() // Purpose: to calculate sale prices based on a single discount percentage and output the // difference the original price total and the discounted price total. // Inputs: the original price of all items to be discounted // Outputs: the discounted prices // the sum of the Original Prices // the sum of the Discounted Prices // the difference between the Original and Discounted Totals // Receives: NONE // Returns: NONE { double price; double discountedPrice; double totalDiscount; double originalPriceTotal = 0; double discountedPriceTotal = 0; 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; originalPriceTotal += price; discountedPriceTotal += discountedPrice; cout << "Please enter an item’s original price (Enter -1 to Stop) "; cin >> price; } totalDiscount = originalPriceTotal - discountedPriceTotal; cout << "The total of the original prices is: $" << originalPriceTotal << endl ; cout << "The total of the discounted prices is: $" << discountedPriceTotal << endl; cout << "The total amount discounted is: $" << totalDiscount << endl; }
int discountedPriceTotal = 1234;
One More Pattern: The Average Pattern
As part of the example of the sum pattern we took out any references
to the counter pattern. It is actually quite common for both a
counter and a sum to be required in the same problem and therefore
for both patterns to be required in the same problem. A perfect
example of this is any problem requiring an average. As you know,
an average is calculated by dividing the sum of some set of numbers
by the number of items summed - the total divided by the count.
The very act of analyzing the requirements of an average problem
tells us that we need the counter and sum patterns and from that
we know we need a loop pattern because both the sum and counter
patterns talk about the need for a loop pattern.
You might be tempted to conclude that since a loop pattern is
mentioned in both the counter and sum patterns, the algorithm
for an average problem will require two loops. This is where
you need to be careful when combining patterns. If you think about
it carefully, you realize that the loop pattern's purpose in both
the counter and sum patterns is to handle, one at a time, the
items being counted or summed. In other words, the same loop meets
both goals - it brings in the items to be summed and allows them
to be counted. Therefore, we only need one loop pattern.
The average pattern uses all three of the patterns already discussed
and adds the average calculation itself at the end:
Pattern Name: The Average Pattern
As the pattern is written, no average is taken if there are no
items to average. In this case a message is output. There are
other ways of handling this situation. For example, you could
set the average to 0.
To make this discussion concrete: suppose that the manager of
the store we have been working with wants to know the average
discounted Price. To calculate this we need the Total Discounted
Price and the number of discounted items - two values we have
already worked with. Here is the algorithm for this pattern. Note
that most of it is simply a combination of the two algorithms
we have just seen.
Set Item Count to 0
Set Total Discounted Price to 0
Get Price
while Price <> - 1
Discounted Price = Price * Discount
Output Discounted Price
Total Discounted Price = Total Discounted Price + Discounted Price
Item Count = Item Count + 1;
Get Price
EndWhile
Output Total Discounted Price
Output Item Count
If Item Count <> 0 then
{
discountedPriceAverage = Total Discounted Price / Item Count;
output discountedPriceAverage;
}
else
{
output "There were no discounted items to average."
}
Assuming that we have completed our analysis and design, let's
proceed to the code for this problem:
// A program to calculate sale prices based on a single discount percentage and output the // number of items discounted, the total discounted prices, and the average of the discounted // prices. // File: ch3prg4.cpp // THE SPECIFICATIONS WOULD GO HERE. #includeconst double DISCOUNT = .87; void main() // Purpose: to calculate sale prices based on a single discount percentage // and output the number of items discounted, the total discounted // prices, and the average of the discounted prices. // Inputs: the original price of all items to be discounted // Outputs: the discounted prices // the sum of the Discounted Prices // the number of items discounted // the average of the discounted prices // Receives: NONE // Returns: NONE { double price; double discountedPrice; double averageDiscountedPrice; double discountedPriceTotal = 0; double originalPriceTotal = 0; int itemCount = 0; 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; discountedPriceTotal += discountedPrice; itemCount++; cout << "Please enter an item’s original price (Enter -1 to Stop) "; cin >> price; } cout << "The total of the discounted prices is: $" << discountedPriceTotal << endl; cout << "The number of items discounted is: " << itemCount << endl; if (itemCount != 0) { averageDiscountedPrice = discountedPriceTotal / itemCount; cout << "The average discountedPrice is: $" << averageDiscountedPrice << endl; } else { cout << "There were no discounted items to average.\n"; } }
you will notice that it says that only the variable(s) involved
in the test condition need be retrieved from the user before the
while loop.
In the Salary Calculation program we only need one indicator from the user that he or she is finished and that can either be a specific value for the rate of pay or for the hours worked. Let's assume that any negative value for the rate of pay will indicate that there are no more employees. If this is the case, only the rate of pay need be retrieved before the 'while' loop and our algorithm can be modified as follows:
Get the Rate of Pay for the employee
While rate of pay > = 0 (greater than or equal to 0)
{
Get the Hours Worked for the employee
if Hours Worked is greater than 40
{
Regular Salary = 40 * Rate of Pay
Overtime Rate of Pay = Rate of Pay * 1.5
Overtime Salary = Overtime Rate of Pay * (Hours Worked - 40)
Full Salary = Regular Salary + Overtime Salary
}
else
{
Full Salary = Hours Worked * Rate of Pay
}
Output the Full Salary
Get the Rate of Pay for the employee
}
V. The 'for' loop
Now, suppose we knew how many employees there were and wanted
to write code that would execute exactly that many times. We saw
earlier how to accomplish this for 10 employees with a
'while' loop
. There is, however, a simpler way to do this involving
yet another C++ instruction. In the 'while' loop version (the
key parts of which are shown below):
int count = 0; // initialize the counter to 0
while (count < 10)
{ cout << "Please enter your rate of pay";
cin >> rateOfPay;
cout << "Please enter the hours you worked this week";
cin >> hoursWorked;
if (hoursWorked > REGULAR_HOURS)
{ regularSalary = REGULAR_HOURS * rateOfPay;
overtimeRateOfPay = rateOfPay * OVERTIME_ADJUSTMENT;
overtimeSalary = (hoursWorked - REGULAR_HOURS) *
overtimeRateOfPay;
fullSalary = regularSalary + overtimeSalary;
}
else
{ fullSalary = hoursWorked * rateOfPay;
}
cout << "Your salary is: " << salary << endl;
}
We will explore the tremendous power of this statement later. Here, however, is how we would write a for loop that executed some code ten times:
Everything of importance for the loop is inside the parenthesis of the 'for' statement. First is the initialization of the 'count' variable, then there is the test to see if count remains less than NUM_TIMES, and finally there is the instruction to increment count by 1 each time through the loop. The first time through the loop 'count' is set to 0 and its value is tested to make sure it is less than NUM_TIMES. If for some reason we had set the value of count to 10 or greater, the loop would never have been entered! Once the system sees that 'count' is less than NUM_TIMES, the loop is entered and whatever instructions are inside the loop are executed. At the end of the loop 'count' is automatically incremented by 1 and its value is again compared with NUM_TIMES. Again, if its value is less than NUM_TIMES the loop is entered, the code inside the loop is executed and 'count' is incremented. This continues until 'count' is no longer less than NUM_TIMES. Note: we could have used the value '10' inside the 'for' statement instead of NUM_TIMES but it is better to use a named constant whenever possible.
Here is the full code to calculate the salary of ten employees:
// A program to calculate the salaries for 10 employees using the 'for' loop // File: ch3prg5.cpp #include// THE SPECIFICATIONS WOULD GO HERE. const int REGULAR_HOURS = 40; // Number of hours before overtime kicks // in double OVERTIME_ADJUSTMENT = 1.5; // Overtime pay adjustment int NUM_TIMES = 10; // Number of employees to work with void main() // Purpose: to calculate salaries for 10 employees // Inputs: the hours worked and the rate of pay of 10 employees // Outputs: the salary of 10 employees // Receives: NONE // Returns: NONE { double rateOfPay; double overtimeRateOfPay; double regularSalary; double overtimeSalary; double fullSalary; double hoursWorked; // can be a fraction of an hour for (int count = 0; count < NUM_TIMES; count++) { cout << "Please enter an employee's rate of pay"; cin >> rateOfPay; cout << "Please enter the hours by that employee"; cin >> hoursWorked; if (hoursWorked > REGULAR_HOURS) { regularSalary = REGULAR_HOURS * rateOfPay; overtimeRateOfPay = rateOfPay * OVERTIME_ADJUSTMENT; overtimeSalary = (hoursWorked - REGULAR_HOURS) * overtimeRateOfPay; fullSalary = regularSalary + overtimeSalary; } else { fullSalary = hoursWorked * rateOfPay; } cout << "The employee’s salary is: " << fullSalary << endl; } }
'For' loops have a number of uses but the one we just saw - to
loop through a group of instructions some set number of times
- is the most common. Often, the exact number of times is not
known when the code is being written even though it will be known
before the loop is executed. This would happen if, for example,
the user was to enter the number of times the loop is to execute
or if there was some way to calculate the number of times to loop.
Here is a general C++ based pattern that captures the key idea
of this notion of getting or calculating the number of times to
loop:
for ( int Counter Variable = 0; Counter Variable <
Num Times; Counter Variable++)
{
// instructions to be executed within the loop
Finally, the 'for' statement can be used with the sum, counter
and average patterns. The code for those patterns would remain
the same but there would be changes in the loop code. You might
want to review both the code that used a 'while' loop to process
ten employees and the 'while' loop code that processed
some unknown number of employees. Note that the
version involving an unknown number of employees requires a sentinel
value and a priming read while the other version has no priming
read. Since the 'for' loop (as we have studied it so far) is used
when the loop is to be executed a pre-determined number of times,
there is, similarly, no need for a priming read.
VI. How to Take Advantage of These Patterns
Back at the beginning of this chapter we talked about the need
to design an algorithm before proceeding to code and about the
challenge of writing an algorithm that can easily be translated
into computer code. We then introduced patterns as one aid in
writing such translatable algorithms. We close this chapter with
a discussion of just how to take advantage of these patterns.
As part of the analysis phase for a problem, you discover the
purpose of a program. Notice that the various patterns also have
a purpose. The average pattern, for example, has as its purpose:
Big deal, hu? But, if you compare the purpose of your problem
with the purpose of the various patterns you might find a match!
If you decide, for example, that the problem you have in front
of you needs an average calculated, it is clearly time to pull
out the old average pattern.
Please take advantage of these patterns. If you don't, you will
be 're-inventing the wheel' every time you start a new program.
To summarize then - the steps you know for successfully completing
a programming problem are:
Each of these steps depends on the ones above it and, if you discover
a problem, you may need to go back to an earlier step to fix that
problem. When you think you are finished, make sure that the output
you have matches your specifications. It is not uncommon for programmers
to write a set of specifications and then drift away from them
as they go through the rest of the steps. It is a bit like that
game where one person whispers something into someone's ear and
the 'secret' gets passed from person to person, and finally passed
back to the original person. Usually, the final version of the
secret is quite different from the original.
And, be careful with your testing. For example, in the average
problem we just looked at, a good set of tests would have included
two or three sets of numbers whose averages were easily calculated
(for example, 10, 20, 30 where the average is 20 and 5, 6, 7 where
the average is 6) AND at least one run where no numbers were entered
- to test the 'if' statement. In general if your program has multiple
'paths' (different sets of code that are chosen by 'if' and 'while'
test conditions) each of those paths should be tested with a data
set.
VII. Wrap Up
In this chapter you have been introduced to algorithm patterns
- an important tool in program development. We have assumed that
our programming problems are simple enough to be solved with one
pattern or one combination of patterns. Real world problems are
usually much more complex and require some kind of 'divide and
conquer' strategy - as hinted at above. In the next chapter we
will take a look at one variation of this strategy. Remember,
as you read the next chapter, however, that, once a problem is
broken up into parts, solving each of those parts may benefit
from the user of the patterns you learned here.