19. Euklidov algoritam za nzd (najveci zajednicki delilac)
nzd(a, 0) = a
nzd(a, b) = nzd(b, a % b), ako je b != 0
int nzd(int a, int b) {
if (b == 0)
return a;
return nzd(b, a % b);
}
Primer: a = 39, b = 15
nzd(39,15) = nzd(15,9) = nzd(9,6) = nzd(6,3) = nzd(3,0) = 3
int nzd1(int a, int b) {
int c;
while (b != 0) {
c = a % b;
a = b;
b = c;
}
return a;
}
a b c
39 15 9
15 9 6
9 6 3
6 3 0
3 0
Slozenost je O(log(max(a,b));
Nakon svaka dva prolaska kroz while petlju vrednost broja b se smanji bar dva puta. Odnosno, ako je vrednost broja b na pocetku nekog prolaza bila b’, a nakon dva prolaza kroz while petlju iznosi b”, onda je b” <= b’ / 2
Kako se svaka sledeca vrednost broja b odredjuje kao ostatak pri deljenju broja brojem b, a ostatak je uvek manji od delioca (tj. broja b), onda je svaki sledeci b manji od prethodnog. Neka je b’ trenutna vrednost nroja b, a neka je a’ trenutna vrednost broja a. Postoje dve mogucnosti:
a’ % b’ <= b’/2. Tada je vec u (prvoj) sledecoj iteraciji petlje vrednost broja b bar dvaput manja, a vrednost posle druge iteracije ce biti jos manja.
a’ % b’ > b’ / 2. Tada b’ postaje novo a, a a’ % b’ > b’/2 postaje novo b. Opet racunamo b” = b’ % (a’ % b’) = b’ – (a’ % b’) < b’ – b’ / 2 = b’ / 2
NTP 