Evklidov algoritem

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Vsebina

Zgodovina

Evklidov algoritem, je eden najstarejših znanih algoritmov, odkar se je pojavil v Evklidovih Elementih, okrog leta 300 p.n.š. * Evklid problem definiral geometrijsko, kot problem iskanja "skupne mere" za dve daljici dane dolžine. Zo skupno mero je iskal tako, da je "odštel" krajšo daljico od daljše, in postopek ponavljal. Algoritma ni odkril Evklid, saj je bil znan že 200 let prej. Skoraj zagotovo je bil znan kot Eudoxus of Cnidus (okrog leta 375 p.n.š); in Aristotel (okrog leta 330 p.n.š) ga je skril v njegovih Topics, 158b, 29-35.

Evklidov algoritem

Evklidov algoritem imenujemo postopek, s katerim lahko poiščemo največji skupni delitelj dveh naravnih števil, ne da bi ju najprej razcepili na produkt praštevil. Postopek je zasnovan na osnovnem pravilu o deljenju.

Osnovni izrek o deljenju:

               a = k*b + r,

kjer sta a in b dani naravni števili, a > b; k je naravno število, in sicer je k kvocient števil a in b (k = a / b); r je ostanek pri deljenju a z b in r mora biti 0 ≤ r < b.

Najprej delimo: a / b in to je enako kvocientu k. Nato moramo še izračunati ostanek r : r = a - k * b.

Opis algoritma

Želimo poiskati največji skupni delitelj D(a,b) naravnih števil a in b. Če je a = b, je D(a,b) = a. Sicer pa je eno od števil večje od drugega. Recimo da je a > b. Delimo a z b:

                  a = k*b + r.

Če je r = 0, je a = k*b in tako očitno D(a,b) = b. Naj bo r > 0 in označimo D(a,b) = D. Ker je r = a - k*b in D deli a in b, D deli tudi r. Torej je D skupni delitelj števil b in r. Naj bo D1 = D(b,r) največji skupni delitelj števil b in r. Potem je D1 ≥ D. Ker D1 deli b in r, deli tudi a = k*b + r. Torej je D1 skupni delitelj števil a in b. Zato je D1 ≤ D. Iz D1 ≥ D in D1 ≤ D pa sledi D1 = D. Torej je

                   D(a,b) = D(b,r)

Delimo zdaj b z r:

                   b = k1*r + r1       (k1 naravno število, 0 ≤ r1 < r)

Če je r1 = 0, potem je D(b,r) = r. Sicer pa je D(b,r) = D(r, r1). Tako nadaljujemo. Števila v oklepaju se manjšajo in postopek se prej ali slej konča.

Ta algoritem lahko zapišemo kot program v Javi, in sicer iterativno in rekurzivno:


  1.  
  2. public class EvklidovAlgoritem{
  3. //iterativna metoda
  4. public static int evklid_iterativno(int x, int y){
  5. int temp;
  6. while(x%y!=0){
  7. temp = x;
  8. x = y;
  9. y = temp % y;
  10. }
  11. return y;
  12. }
  13. //rekurzivna metoda
  14. public static int evklid_rekurzivno(int x, int y){
  15. if(x%y==0) return y;
  16. return evklid_rekurzivno(y, x%y);
  17. }
  18. }

Razširjeni Eklidov algoritem (REA)

Pomemben je tudi razširjeni Evklidov algoritem. S pomočjo REA iščemo celi števili s in t, tako da bo a*s + b*t Postopek:

       a    1    0
k1     b    0    1
k2     r1   s1   t1
:      :    :    :
k(n+1) rn   sn   tn
        0

kjer je ki = r(i-2)/r(i-1), ri = r(i-2)-ki*r(i-1), si = s(i-2)-ki*s(i-1) in ti = t(i-2)-ki*t(i-1) za i = 1,2,...,n.

Algoritem lahko zapišemo v Javi:

  1.  
  2. public static int[] rea(int a, int b){
  3. int tabela[] = new int[3];
  4. //s1,s2,t1,t2 so na začetku 1 oziroma 0 po definiciji razširjenega Euklidovega algoritma (rea)
  5. int s1= 1;
  6. int s2 = 0;
  7. int t1 = 0;
  8. int t2 = 1;
  9. //če je b=0 ne rabimo nič računati
  10. if (b == 0){
  11. tabela[0]=s1;
  12. tabela[1]=s2;
  13. tabela[2]=a;
  14. return tabela;
  15. }
  16. //če b različen od 0 ponavljamo dokler je ostanek
  17. //deljenja a z b razlicen od 0
  18. int k = a/b; //izracunamo kolicnik
  19. int r = a%b; //ostanek deljenja a-ja z b
  20. while(r != 0){
  21. r =a%b; //nov ostanek
  22. }
  23. //ko pridemo iz zanke so s2,t2 in b željeni rezultati
  24. tabela[0] = s2;
  25. tabela[1] = t2;
  26. tabela[2] = b;
  27. return tabela;
  28. }

Primer

Poišči največji skupni delitelj števil a = 899 in b = 812.

899 = 1*812 + 87

812 = 9*87 + 29

87 = 3*29 + 0

D(899,812) = D(812,87) = D(87,29) = D(29,0) = 29

Torej največji skupni delitelj števil 899 in 812 je 29.

Dodatno: poišči še s in t, tako da bo a*s + b*t = D(a,b).

      899   1   0
  1   812   0   1
  9    87   1  -1
  3    29  -9  10
        0

Rešitev torej je : 899*(-9) + 812*(10) = 29.

Osebna orodja