Evklidov algoritem: Razlika med redakcijama

Iz Wikipedije, proste enciklopedije
Izbrisana vsebina Dodana vsebina
m vrnitev sprememb uporabnika »194.249.197.2« (pogovor) na zadnje urejanje uporabnika »JAnDbot«
m dp
Vrstica 1: Vrstica 1:
'''Evklidov algoritem''' je [[algoritem|postopek]], s katerim določimo [[največji skupni delitelj]] dveh [[število|števil]] oz. [[polinom]]ov. [[Evklid]] je sicer prvotno je zasnoval algoritem za določanje največje skupne mere dveh [[daljica|daljic]].
'''Evklidov algoritem''' [evklídov algorítem] je [[algoritem|postopek]], s katerim določimo [[največji skupni delitelj]] dveh [[število|števil]] oziroma [[polinom]]ov. [[Evklid]] je sicer prvotno je zasnoval algoritem za določanje največje skupne mere dveh [[daljica|daljic]].


Prednost Evklidovega postopka je, da ni potrebo [[faktorizacija|razcepiti števil]]. Sam postopek je sicer eden najstarejših znanih algoritmov, datira okrog leta 300. pr.n.št., verjetno pa je bil poznan že 200 let prej.
Prednost Evklidovega postopka je, da ni potrebo [[faktorizacija|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 ==
== 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 postpek s številom ''b'' in ter celoštevilskim ostankom deljenja ''a'' z ''b'' ( a ''[[modulo|mod]]'' b).
Č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 postpek s številom ''b'' in ter celoštevilskim ostankom deljenja ''a'' z ''b'' ( a ''[[modulo|mod]]'' b).


Vrstica 13: Vrstica 14:
Analiza časa teka algoritma pokaže, da je najslabši možen primer, kadar imamo dve zaporedni [[Fibonaccijeva števila|Fibonaccijevi števili]], potreben čas je [[Zapis veliki O|''O''(''n'')]] deljenj, kjer je ''n'' število števk na vhodu. Ker pa praviloma deljenje ni osnovna operacija, je potreben čas reda ''O''(''n''²).
Analiza časa teka algoritma pokaže, da je najslabši možen primer, kadar imamo dve zaporedni [[Fibonaccijeva števila|Fibonaccijevi števili]], potreben čas je [[Zapis veliki O|''O''(''n'')]] deljenj, kjer je ''n'' število števk na vhodu. Ker pa praviloma deljenje ni osnovna operacija, je potreben čas reda ''O''(''n''²).


== [[Programski jezik C|C]]/[[C plus plus|C++]] implementacija ==
== Zapis algoritma v jezikih [[Programski jezik C|C]] in [[C plus plus|C++]] ==
<pre><nowiki>
<pre><nowiki>
int gcd(int a, int b) {
int gcd(int a, int b) {
if (b == 0)
if (b == 0)
return a;
return a;

return gcd(b, a % b);
return gcd(b, a % b);
}
}
</nowiki></pre>
</nowiki></pre>


Ali iterativna različica:
Ali [[iteracija|iterativna]] različica:


<pre><nowiki>
<pre><nowiki>

Redakcija: 23:37, 6. maj 2007

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

Prednost Evklidovega postopka je, da ni potrebo 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 postpek 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;
}