Evklidov algoritem: Razlika med redakcijama
m vrnitev sprememb uporabnika 149.62.98.72 (pogovor) na zadnje urejanje uporabnika Glaisher |
|||
Vrstica 1: | Vrstica 1: | ||
'''Evklídov |
'''Evklídov algorítem''' je [[algoritem|postopek]], s katerim se določi [[največji skupni delitelj]] dveh [[število|števil]] oziroma [[polinom]]ov. [[Evklid]] je sicer prvotno zasnoval algoritem za določanje največje skupne mere dveh [[daljica|daljic]]. |
||
[[Slika:Euclidean algorithm running time X Y.png|thumb|right|230px|Graf za čas izračunavanja [[največji skupni delitelj|D(''x'',''y'')]]. Rdeča označuje hitro izračunavanje, bolj modre točke pa označujejo počasnejše]] |
[[Slika:Euclidean algorithm running time X Y.png|thumb|right|230px|Graf za čas izračunavanja [[največji skupni delitelj|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 [[praštevilski razcep|razcepiti števil]]. Sam postopek je sicer eden najstarejših znanih |
Prednost Evklidovega postopka je, da ni potrebno [[praštevilski razcep|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 |
== Opis algoritma == |
||
Če se obravnavata naravni števili ''a'' in ''b'', se predpostavi, da je ''a'' večji ali enak ''b''. Če je ''b'' enak nič, potem je ''a'' rezultat postopka. Sicer pa se nadaljuje postopek s številom ''b'' in ter [[celo število|celoštevilskim]] [[deljenje z ostankom|ostankom deljenja]] ''a'' z ''b'' (a ''[[modulo|mod]]'' b). |
Če se obravnavata naravni števili ''a'' in ''b'', se predpostavi, da je ''a'' večji ali enak ''b''. Če je ''b'' enak nič, potem je ''a'' rezultat postopka. Sicer pa se nadaljuje postopek s številom ''b'' in ter [[celo število|celoštevilskim]] [[deljenje z ostankom|ostankom deljenja]] ''a'' z ''b'' (a ''[[modulo|mod]]'' b). |
||
Zapis |
Zapis algoritma z [[rekurzija|rekurzijo]]: |
||
'''function''' gcd(a, b) |
'''function''' gcd(a, b) |
||
'''if''' b = 0 '''return''' a |
'''if''' b = 0 '''return''' a |
||
'''else''' '''return''' gcd(b, a '''mod''' b) |
'''else''' '''return''' gcd(b, a '''mod''' b) |
||
Analiza časa teka |
Analiza časa teka algoritma pokaže, da je najslabši možen primer, kadar sta 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''²). |
||
== Zapis |
== Zapis algoritma v jezikih [[Programski jezik C|C]] in [[C++]] == |
||
<source lang="c"> |
<source lang="c"> |
||
int gcd(int a, int b) { |
int gcd(int a, int b) { |
Redakcija: 13:38, 25. november 2016
Evklídov algorítem je postopek, s katerim se določi največji skupni delitelj dveh števil oziroma polinomov. Evklid je sicer prvotno zasnoval algoritem za določanje največje skupne mere dveh daljic.
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 se obravnavata naravni števili a in b, se predpostavi, da je a večji ali enak b. Če je b enak nič, potem je a rezultat postopka. Sicer pa se nadaljuje 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 sta 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;
}