An Example of an Accumulation Problem Involving Repetition Structure

A storeowner wants a program that will total the prices of a group of items brought to the cashier and then display the total on the screen.

Background:

"Accumulation" is the process commonly referred to as "sub-totaling" where a variable (called an "accumulator") is repeatedly adjusted by another value. This is typically performed in a repetitive process (or "loop") using "sentinel control" to stop the repetition when all of the values to be sub-totaled have been entered. A "sentinel value" must be selected by the programmer for the user to enter to signal an end of the loop. The value selected must be one that will never be entered by the user for any purpose other than to end the loop. In this example, the value -1 is used as the sentinel value because it is unlikely that any item will have a price of -1 dollars.

Portions of the solution below (including the flowchart, desk check, and C source code) have been duplicated in different background colors to illustrate the use of both of the repetitive structures discussed in class, "Pretest Loop" (based on a "leading decision") and "Posttest Loop" (based on a "trailing decision"). If you were solving this problem, you would select only one of the two structures and document it.

PROBLEM STATEMENT:

Request and build a running total of a series of item prices, stopping when the user enters the value negative one (-1). Then display the total (rounded to cents) with an identifying message.

DATA DEFINITION:

In the sample output below the numbers to the left of the sample screen are there only for your reference in other documentation. Underlined items indicate user input and could be different each run of the program.

SAMPLE OUTPUT (Softcopy):

Note: In programs that involve repetitive processes (loops) be sure to provide sample output that shows more than one pass through the loop so that readers can see an example of the repetition taking place.

SYMBOLIC CONSTANT LIST:

VARIABLE LIST:

LABEL	DESCRIPTION	DATA TYPE	VALUE	USAGE	DESTINATION
SENT	Sentinel value for loop exit	Floating point	-1.0	Loop Sentinel	Screen

LABEL	DESCRIPTION	DATA TYPE	SOURCE	USAGE	DESTINATION
P	Price of each item	Floating point	Keyboard	Loop Sentinel & accumulated in T	---
T	Running total of all items (except for the sentinel)	Floating point	Set to 0.0	Accumulates P	Screen

FLOWCHART FOR PROGRAM "Accumulate" USING THE PRETEST LOOP STRUCTURE:

When designing programs that use loops, we can illustrate the repetition structure through either an [outlined algorithm] or a diagram called a flowchart (see below). Such diagrams show the flow of control (or order of execution) of the steps within a program and can be used instead of an outline when developing and documenting an algorithm. Students are advised to read the basic web page about Flowcharting Symbols & Guidelines. The flowchart below illustrates a repetition structure based on the value stored in a control variable named C. The diamond shape encloses the condition that is being tested. The processes leading out of the diamond are called branches or legs and must be labeled to indicate which one is to be followed when the condition in the diamond is TRUE or FALSE. It is typical to define the condition such that it will be true for the branch that passes through the loop body and false for the branch that exits the loop.

Flowchart of a pretest decision sentinel controlled accumulating loop

Notice the use of the "prime read" prior to the loop and the "next read" as the last step of the loop. This approach is used to make sure that the accumulation process performed as the body of the loop will not be performed on the sentinel value. Also notice the step ahead of the loop that initializes the accumulator T so that it has a defined value before its first use in the body of the loop.

TEST OUTPUT (for the Pretest Loop solution):

1 2 3 4 5 6 7 Item price (-1 to stop)? [5.25] Item price (-1 to stop)? [2.15] Item price (-1 to stop)? [3.40] Item price (-1 to stop)? [1.20] Item price (-1 to stop)? [-1] Total of purchases: $12.00

TRACING CHART (for the Pretest Loop solution):

Data Tracing Charts are used to document what would be happening in the computer's memory during the execution of the steps described in an algorithm. A column is provided for each variable in your analysis and for each condition being tested (in a diamond shape). An additional column can be added on the left of the table to serve as a reference to steps in your flowchart if you choose to put reference letters next to the related shapes. This was not done in the example shown below. The entries in the chart below relate to only steps in the algorithm that effect the memory.

P	T	P not = SENT
	0.0
5.25
		True
	5.25
2.15
		True
	7.40
3.40
		True
	10.80
1.20
		True
	12.00
-1
		False

C++ SOURCE CODE (for the Pretest Loop solution):

/* accumulate.cpp */
/* a repetitive process using a leading decision structure */
/* by Randolph Gibson - 9 September 2011 */

#include <iostream>  /* Standard Input/Output header file */
using namespace std;
#include <iomanip>   /* Stream Manipulator header file */

#define SENT -1.0   /* Sentinel value for loop control tests */

float P, T;  /* item price(s) and total */

int main ()
{
  cout << setprecision(0) << fixed;
  T = 0.0; /* Initialize total to zero */
  cout << "Item price (" << SENT << " to stop)? ";
  cin >> P;  /* Prime Read */
  while (P!=SENT)
    { /* loop */
      T = T + P;    /* Accumulate P in T */
      cout << "Item price (" << SENT << " to stop)? ";
      cin >> P;   /* Next Read */
    } /* loop */
  cout << setprecision(2);
  cout << "\nTotal of purchases: $" << T << endl;
  return 0;
}

FLOWCHART FOR THE PROGRAM "Accumulate" USING THE POSTTEST LOOP STRUCTURE:

We can illustrate the trailing decision repetition structure through either an [outlined algorithm] or the flowchart below.

Flowchart of a posttest decision sentinel contolled accumulating loop

The use of a "posttest decision" approach to develop this loop requires the use of a "selection (if-then) structure" in the middle of the loop to "guard" the accumulation process from acting on the sentinel value and improperly including it in the sub-total. The selection structure and the if statement are discussed in Chapter 5 of our textbook. This guard technique is often used in loops using the Do-While structure to prevent sentinel values from being processed with the rest of the normal data within a loop.

TEST OUTPUT (for the Posttest Loop Solution):

TRACING CHART (for the Posttest Loop Solution):

Readers who have difficulty rendering tracing charts can read the [text-based tracing list] for this example instead.

P	P not = SENT (Guard)	T	P not = SENT (Loopback)
		0.0
5.25
	True
		5.25
			True
2.15
	True
		7.40
			True
3.40
	True
		10.80
			True
1.20
	True
		12.00
			True
-1
	False
			False

C++ SOURCE CODE (for the Posttest Loop Solution):

/* accumulate.cpp */
/* a repetitive process using a trailing decision structure */
/* by Randolph Gibson - 9 September 2011 */

#include <iostream>  /* Standard Input/Output header file */
using namespace std;
#include <iomanip>   /* Stream Manipulator header file */

#define SENT -1.0   /* Sentinel value for loop control tests */

float P, T;  /* item price(s) and total */

int main ()
{
  cout << setprecision(0) << fixed;
  T = 0.0; /* Initialize total to zero */
  do { /* loop */
      cout << "Item price (" << SENT << " to stop)? ";
      cin >> P;
      if (P!=SENT) T = T + P;   /* Accumulate P in T */
     } /* loop */
  while (P!=SENT);
  cout << setprecision(2);
  cout << "\nTotal of purchases: $" << T << endl;
  return 0;
}