1
An algorithm defines a detailed and unambiguous sequence of actions for solving a particular problem or
for performing some task. If you have ever followed a recipe when cooking, followed a set of driving directions,
or filled out an income tax form, you have worked with an algorithm.
For example, at some point in time you were probably taught how to determine the greatest common divisor
(GCD) of two numbers. In case you??™ve forgotten, the GCD of two positive integers is the greatest integer that
is an even divisor of both numbers. For example, the GCD of 42 and 30 is 6. The algorithm given below can be
used to compute the GCD of two positive integers a and b:
If b is zero, then the GCD of a and b is a. Algorithm ends.
Set r to be the remainder obtained from the integer division of a and b.
Repeat this process using b and r.
Consider computing the GCD of 42 and 30. Let a = 42 and b = 30. We start the process at step 1 of the
algorithm. Since b is not zero, we proceed to step 2. In step 2 we compute the remainder obtained when 42 is
divided by 30, which is 12. Step 3 instructs us to repeat the process, this time using 30 and 12. So on this second
trip through the process a is now 30 and b is now 12.
Pages:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25