Caribbean Secondary Education Certificate - Information Technology/Converting Algorithms to Programs

Example

Problem: Find the greatest common divisor (GCD) of two integers, m and n.

Euclid's Algorithm:

while m is greater than zero:

  If n is greater than m, swap m and n.
  Subtract n from m.

n is the GCD

Program (in C): int gcd(int m, int n) /* precondition: m>0 and n>0. Let g=gcd(m,n). */

{ while( m > 0 )
   { /* invariant: gcd(m,n)=g */
    if( n > m )
      { int t = m; m = n; n = t; } /* swap */
     /* m >= n > 0 */
     m -= n;
   }
  return n;
}