Evklidov algoritem: Razlika med redakcijama

Iz Wikipedije, proste enciklopedije
Izbrisana vsebina Dodana vsebina
Rubinbot (pogovor | prispevki)
m r2.7.3) (Robot: Dodajanje he:מחלק משותף מקסימלי
Vrstica 56: Vrstica 56:
[[fi:Eukleideen algoritmi]]
[[fi:Eukleideen algoritmi]]
[[fr:Algorithme d'Euclide]]
[[fr:Algorithme d'Euclide]]
[[he:מחלק משותף מקסימלי]]
[[hu:Euklideszi algoritmus]]
[[hu:Euklideszi algoritmus]]
[[id:Algoritma Euklidean]]
[[id:Algoritma Euklidean]]

Redakcija: 15:50, 26. februar 2013

Evklídov algorítem je postopek, s katerim določimo največji skupni delitelj dveh števil oziroma polinomov. Evklid je sicer prvotno zasnoval algoritem za določanje največje skupne mere dveh daljic.

Graf za čas izračunavanja D(x,y). Rdeča označuje hitro izračunavanje, bolj modre točke pa označujejo počasnejše

Prednost Evklidovega postopka je, da ni potrebno razcepiti števil. Sam postopek je sicer eden najstarejših znanih algoritmov in je znan od približno leta 300 pr. n. št., verjetno pa je bil poznan že 200 let prej.

Opis algoritma

Če imamo naravni števili a in b, predpostavimo, da je a večji ali enak b. Če je b enak nič, potem je a rezultat postopka. Sicer pa nadaljujemo postopek s številom b in ter celoštevilskim ostankom deljenja a z b (a mod b).

Zapis algoritma z rekurzijo:

 function gcd(a, b)
     if b = 0 return a
     else return gcd(b, a mod b)

Analiza časa teka algoritma pokaže, da je najslabši možen primer, kadar imamo dve zaporedni Fibonaccijevi števili, potreben čas je O(n) deljenj, kjer je n število števk na vhodu. Ker pa praviloma deljenje ni osnovna operacija, je potreben čas reda O(n²).

Zapis algoritma v jezikih C in C++

int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

Ali iterativna različica:

int gcd(int a, int b) {
  int t;
  while (b != 0) {
    t = b;
    b = a % b;
    a = t;
  }
  return a;
}

Predloga:Link FA