Naredna: Testiranje programa Gore: NZD Prethodna: Specifikacija   Sadržaj

Pseudokod programa

Kako napisati algoritam za izračunavanje najvećeg zajedničkog delioca dva nenegativna cela broja?
Pođimo prvo od definicije:
NZD brojeva x i y je najveći prirodan broj koji deli x i deli y.

Broj 1 deli svaki nenegativan ceo broj. Počnimo sa vrednošću 1 i isprobajmo sve brojeve koji su manji od x i manji od y. Ukoliko neki deli oba broja, sačuvajmo ga kao potencijalni NZD, ukoliko ne deli, nastavljamo dalje sa isprobavanjem. Na taj način dobijamo sledeći algoritam:

{x > 0, y > 0}
z = 1;
br = 2;
while (br ≤ x && br ≤ y) do
    begin
      if ((x % br) == 0 && (y % br) == 0) 
        then z = br;
      br = br + 1;
    end
{z = NZD(x,y)}

Prethodni algoritam nije efikasan jer se u njemu polazi od vrednosti 1 i isprobavaju se svi mogući brojevi dok ne dođemo do gornje granice. S obzirom da tražimo najveći zajednički delilac brojeva algoritam možemo da unapredimo tako što ćemo da počnemo isprobavanje brojeva od z (gde je z manja od vrednosti x i y) i čim naiđemo na prvi broj koji ih deli on je traženi NZD. U najgorem slučaju, telo petlje izvršiće se z puta dok ne dođemo do vrednosti 1.

{x > 0, y > 0}
z = 1;
if (x < y) 
   then z = x;
   else z = y;
indikator = 1;
while (indikator ≠ 0) do
    begin
      if ((x % z) == 0 && (y % z) == 0) 
        then indikator = 0;
        else z = z-1;
    end
{z = NZD(x,y)}

Međutim, i ovaj algoritam nije u potpunosti efikasan. Na primer, ukoliko su oba broja parna, nema smisla isprobavati da li je neki neparan broj njihov NZD. Da bismo preskočili isprobavanja koja nas ne vode do rešenja, primetimo sledeću osobinu prirodnih brojeva:
Ako neki broj deli x i deli y onda taj broj deli i razliku brojeva x i y.
Ovu osobinu koristimo za izvođenje sledeće jednakosti:

		NZD(x-y, y), x > y
NZD(x,y)={	NZD(x, y-x), y > x
		x,           x = y

Prethodna formula prevodi se direktno u sledeći pseudokod:

{x > 0, y > 0}
p = x;
q = y; 
while (p ≠ q) do
    begin
     if (p > q) 
        then p = p - q;
        else q = q - p;
    end
z = p;
{z = NZD(x,y)}

Da li možemo još da unapredimo efikasnost našeg algoritma? Na osnovu osobina prirodnih brojeva, važi sledeće:
Ako je x > y, onda se x može jednoznačno predstaviti zbirom
x = q * y + r
gde su q i r nenegativni celi brojevi i za r važi 0 ≤ r < y.
Kako NZD deli y, i NZD deli x = q * y + r to znači da NZD deli i r. To možemo da iskoristimo za formulisanje sledeće jednakosti

		NZD(y, x % y), x > y
NZD(x,y)={	NZD(x, y % x), y > x
		x,             y = 0

koja se može prevesti u sledeći algoritam koji je poznat kao Euklidov algoritam za izračunanje najvećeg zajedničkog delioca dva nenegativna cela broja.

{x > 0, y > 0} 
p = x;
q = y;
if (p < q) then
   begin
       pom = p;
       p = q;
       q = pom;
    end
while (q ≠ 0) do
    begin
       pom = q;
       q= p % q;
       p = pom;
    end
z = p;
{z = NZD(x,y)}

Pitanje koje se sada postavlja je da li je ovaj program ispravan? Da li on zaista izračunava najveći zajednički delilac dva nenegativna cela broja?

Naredna: Testiranje programa Gore: NZD Prethodna: Specifikacija   Sadržaj