4.2 Problem Solving: Decision Steps in Algorithms

In the problem that follows, you will see how to improve the payroll program.

PROBLEM SPECIFICATION

Modify the simple payroll program to deduct a $25 tax only if an employee earns more than $100 and deduct no tax otherwise.

ANALYSIS

We will analyze this problem using the tools developed in the last chapter. Webegin by listing the data requirements and the algorithm.

Data Requirements

Problem Constants

maximum salary without a tax deduction (TaxBracket = 100.00)

amount of tax deducted (Tax = 25.00)

Problem Inputs

hours worked (Hours : NonNegFloat)

hourly rate (Rate : NonNegFloat)

Problem Outputs

gross pay (Gross : NonNegFloat)

net pay (Net : NonNegFloat)

Relevant Formulas

gross pay = hourly rate * hours worked

net pay = gross pay - deductions

Unlike problem inputs, whose values may vary, problem constants have the same values for each run of the program. Each constant value is associated with an identifier (Tax and TaxBracket above). The program style display following this problem describes the reason for this association.

DESIGN

The structure chart for this algorithm is given in Figure 4.3.

Figure 4.3 Structure Chart for Modified Payroll Program

Initial Algorithm

1. Display user instructions.

2. Enter hours worked and hourly rate.

3. Compute gross salary.

4. Compute net salary.

5. Display gross salary and net salary.

Now let's write the refinement of algorithm step 4 as a decision step.

Step 4 Refinement

4.1. IF Gross > TaxBracket THEN

Deduct a tax of $25

ELSE

Deduct no tax

END IF;

The decision step is expressed in pseudocode, which is a mixture of everyday language and Ada used to describe algorithm steps.

TEST PLAN

To test this program, run it with several sets of data. One data set should yield a gross salary greater than $100.00, and the other should yield a gross salary less than $100.00. You should also test the program with a data set that yields a gross salary that is $0.00, one that yields a gross salary of exactly $100.00, and at least one for invalid inputs.

IMPLEMENTATION

The modified payroll program is shown in Program 4.1.

Program 4.1
Modified Payroll Program

WITH Ada.Text_IO;
WITH Ada.Float_Text_IO;
PROCEDURE Modified_Payroll IS
------------------------------------------------------------------------
--| Computes and displays gross pay and net pay given an hourly
--| rate and number of hours worked.  Deducts a tax of $25 if
--| gross salary exceeds $100; otherwise, deducts no tax.
--| Author: Michael B. Feldman, The George Washington University
--| Last Modified: July 1995                           
------------------------------------------------------------------------

  SUBTYPE NonNegFloat IS Float RANGE 0.0 .. Float'Last;
  
  TaxBracket : CONSTANT NonNegFloat := 100.00;
                             -- maximum salary for no deduction
  Tax :        CONSTANT NonNegFloat := 25.00;   -- tax amount
 
  Hours : NonNegFloat; -- inputs - hours worked, hourly rate
  Rate:   NonNegFloat;
  Gross:  NonNegFloat; -- outputs - gross pay, net pay
  Net:    NonNegFloat;

BEGIN -- Modified_Payroll

  -- Enter Hours and Rate
  Ada.Text_IO.Put (Item => "Hours worked > ");
  Ada.Float_Text_IO.Get (Item => Hours);
  Ada.Text_IO.Put (Item => "Hourly rate $");
  Ada.Float_Text_IO.Get (Item => Rate);
  Ada.Text_IO.New_Line;

  -- Compute gross salary
  Gross := Hours * Rate;

  -- Compute net salary
  IF Gross > TaxBracket THEN
    Net := Gross - Tax;     -- Deduct a tax amount
  ELSE
    Net := Gross;           -- Deduct no tax
  END IF;

  -- Print Gross and Net
  Ada.Text_IO.Put (Item => "Gross salary is $");
  Ada.Float_Text_IO.Put (Item => Gross, Fore => 1, Aft => 2, Exp => 0);
  Ada.Text_IO.New_Line;
  Ada.Text_IO.Put (Item => "Net salary is $");
  Ada.Float_Text_IO.Put (Item => Net, Fore => 1, Aft => 2, Exp => 0);
  Ada.Text_IO.New_Line;

END Modified_Payroll;

Hours worked > 37.5
Hourly rate $7.50

Gross salary is $281.25
Net salary is $256.25

TESTING

The sample run shows one set of test data from the test plan.

PROGRAM STYLE
Use of Constants

The constants Tax and TaxBracket appear in the preceding IF statement and in Program 4.1. We might have been tempted to insert the constant values (100.00 and 25.00) directly in the IF statement, writing

    IF Gross > 100.00 THEN
        Net := Gross - 25.00;
    ELSE
        Net := Gross;
    END IF; 

There are two reasons why it is better style to use the constants as we did originally. First, the original IF statement is easier to understand because it uses the names Tax and TaxBracket, which are descriptive, rather than numbers, which have no intrinsic meaning. Second, a program written with constants is much easier to modify than one that is not. If the tax bracket and tax value were to change--and tax-related things always change--we would need to change only the constant declaration. If the constant values were inserted directly in the IF statement as just shown above, we would have to change them not only in the IF statement but in all the other statements in which they appeared. In a program of realistic length, finding all these occurrences would be a tedious and error-prone process. For both reasons, we recommend that you try to avoid dispersing constant values through your programs; instead use constants that are declared by name.

PROBLEM SPECIFICATION

Read three letters and find and display the one that comes first in the alphabet.

ANALYSIS

From our prior experience with conditions and decision steps, we know how tocompare two items at a time to see which one is smaller using the relational operator <. We can also use this operator to determine whether one letter precedes another in the alphabet. For example, the condition 'A' < 'F' is true because A precedes F in the alphabet. Because we have no direct way to compare three items, our strategy will be to do a sequence of pairwise comparisons. We will start by comparing the first two letters to find the smaller of that pair. The result of the second comparison will be the smallest of the three letters.

Data Requirements

Problem Inputs

three letters (Ch1, Ch2, Ch3 : Character).

Problem Outputs

the alphabetically first letter (AlphaFirst : Character).

DESIGN

Initial Algorithm

1. Read three letters into Ch1, Ch2, and Ch3.

2. Save the alphabetically first of Ch1, Ch2, and Ch3 in AlphaFirst.

3. Display the alphabetically first letter.

Algorithm Refinements

Step 2 can be performed by first comparing Ch1 and Ch2 and saving the alphabetically first letter in AlphaFirst; this result can then be compared to Ch3. The refinement of step 2 follows.

Step 2 Refinement

2.1. Save the alphabetically first of Ch1 and Ch2 in AlphaFirst.

2.2. Save the alphabetically first of Ch3 and AlphaFirst in AlphaFirst.

Figure 4.4 shows the structure chart that corresponds to this algorithm.

Figure 4.4
Structure Chart for Finding Alphabetically First Letter

TEST PLAN

Test this program with different sequences of letters, corresponding to the possible orderings of three distinct letters. Also, test with cases where at least two of the letters are equal. In this way, you are ensuring that each of the paths through the IF statements are tested.

IMPLEMENTATION

Program 4.2 shows the desired program. The IF statement with two alternatives saves either Ch1 or Ch2 in AlphaFirst. The IF statement with one alternative stores Ch3 in AlphaFirst if Ch3 precedes the value already in AlphaFirst. Later you will see that IF statements with more than two alternatives are also possible in Ada.

Program 4.2
Finding the First Letter

WITH Ada.Text_IO;
PROCEDURE First_Letter IS
------------------------------------------------------------------------
--| Finds and prints the alphabetically first letter.
--| Author: Michael B. Feldman, The George Washington University 
--| Last Modified: July 1995
------------------------------------------------------------------------

  Ch1, Ch2, Ch3  : Character;   -- input  - three letters
  AlphaFirst     : Character;   -- output - alphabetically first letter

BEGIN  -- First_Letter   

  -- Read three letters   
  Ada.Text_IO.Put (Item => "Enter any three letters, then press ENTER > ");
  Ada.Text_IO.Get (Item => Ch1);  
  Ada.Text_IO.Get (Item => Ch2);
  Ada.Text_IO.Get (Item => Ch3);

  -- Save the smaller of Ch1 and Ch2 in AlphaFirst
  IF Ch1 < Ch2 THEN
    AlphaFirst := Ch1;      -- Ch1 comes before Ch2
  ELSE
    AlphaFirst := Ch2;      -- Ch2 comes before Ch1
  END IF;

  -- Save the smaller of Ch3 and AlphaFirst in AlphaFirst
  IF Ch3 < AlphaFirst THEN
    AlphaFirst := Ch3;      -- Ch3 comes before AlphaFirst
  END IF;

  -- Print result
  Ada.Text_IO.Put (Item => AlphaFirst);
  Ada.Text_IO.Put (Item => " is the first letter alphabetically");
  Ada.Text_IO.New_Line;

END First_Letter;

Enter any three letters, then press ENTER > THE
E is the first letter alphabetically

As usual, the sample output shows one of the test cases.

Exercises for Section 4.2

Self-Check

1. What value is assigned to X for each segment below when Y is 15.0.
   a.

    
   X := 25.0;
   IF Y /= (X - 10.0) THEN
       X := X - 10.0;
   ELSE
       X := X / 2.0;
   END IF;
   

   
   b.

   IF Y < 15.0 THEN
       X := 5 * Y;
   ELSE
       X := 2 * Y;
   END IF;
   

Programming

1. Write Ada statements to carry out the steps below.

   a. If Item is nonzero, multiply Product by Item and save the result in Product; otherwise, skip the multiplication. In either case, display the value of Product.

   b. Store the absolute difference of X and Y in Z, where the absolute difference is (X - Y) or (Y - X), whichever is positive.

   c. If X is zero, add 1 to ZeroCount. If X is negative, add X to MinusSum. If X is greater than zero, add X to PlusSum.

2. Modify the structure chart and program for the first letter problem to find the first of four letters.
3. Write a structure chart and program to find the alphabetically last of three letters.

Copyright © 1996 by Addison-Wesley Publishing Company, Inc.