Algorithm Design

Algorithm　 Design
　　　　 - a　 case　 study

Find　 gcd(u, v)
= greatest common divisor of u,v

gcd(24, 60) = 12

(1)Brute - force
　 t := min(u, v);
　 while (u mod t <> 0) or (v mod t <> 0) do t :=
　　 t - 1;
　　 gcd := t;

(2)Euclid's algorithm (輾轉相除法)
.mathematics :

(u, v) = (v, u-v) = (v, u-2v)
= ......... = (v, u mod v)

.Recursive　 Program :
　if　 v = 0　 then　 gcd := u ;
　else　 gcd := gcd(v, u mod v);
.Recursion :　 call itself
　.reduced to small problem - simple, clear
　.termination condition - tricky, inefficient
　.programming environment (stack)
　　　　　　　　　 Not in FORTRAN
　