Counting

book : How ToSolve It by Computer

chapter 2. Fundamental Algorithm

Algorithm 2.2 
Counting

Problem

Given a set of n students' examination marks (in the range 0 to 100) make a count of the number of students that passed the examination. A pass is awarded for all marks of 50 and above.

Algorithm development

Counting mechanisms are very frequently used in computer algorithms. Generally a count must be made of the number of items in a set which possess some particular property or which satisfy some particular condition or conditions. This class of problems is typified by the "examination marks" problem.

Suppose that we are given the set of marks

55, 42, 77, 63, 29, 57, 89

To make a count of the passes for this set we can start at the left, examine the first mark (i.e. 55), see if it is >= 50, the second mark is then examined and no adjustment is made to the count. When we arrive at the third mark we see it is >=50 and so we add one to our previous count. The process continues in a similar manner until all marks have been tested.

In more detail we have:

Marks   Counting details for passes

previous count = 0 current count = 1

previous count = 1 current count = 1

previous count = 1 current count = 2

previous count = 2 current count = 3

previous count = 3 current count = 3

previous count = 3 current count = 4

previous count = 4 current count = 5

The conclution : number of students passed = 5

Algorithm description

1.    Prompt then read the number of marks to be processed.

2.     Initialize count to zero.

3    While there are still marks to be processed repeatedly do

      (a)     read next mark,

      (b)    if it is a pass (i.e. >=50) then add one to count. 

4.    Write out total number of passes

Pascal implementation

program passcount (input, output);

const passmark = 50;

var count {contains number of passes on termination},

   i {current number of marks processed},

   m {current mark),

   n {total number of marks to be processed}: integer;

begin {count the number of passes (>=50) in a set of marks] 

writeln ('enter a number of marks nona separate line followed by the marks')) 

readln (n);

{assert: n>=0}

count := 0;  

i := 0;

{invariant: count -number of marks in the first i read that are >=passmark A / = <n}

 While/</? Do

begin {read next mark, test it for pass and update count if necessary) 

 i :=/+1;

read (m);

If eoln (input) then read/n; 

 if m>=passmark then count := count+1 

end; 

 {assert: count = number of passes in the set of n marks read} 

writeln ('number of passes = ', count) 

 end.

Notes on design

1. Initially, and each time through the loop, the variable count represents the number of passes so far    encountered. On termination (when i = n) count represents the total number of passes in the set.
2. It was possible to use substitution to improve on the original solution to the problem. The simplest and most efficient solution to a problem is usually the best all-round solution.
3. An end-of-line test is included to handle multiple lines of data.