Evklidov algoritem: Razlika med redakcijama
Izbrisana vsebina Dodana vsebina
m vrnitev sprememb uporabnika 149.62.98.72 (pogovor) na zadnje urejanje uporabnika XJaM |
|||
Vrstica 5:
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.
==
Č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 algoritma z [[rekurzija|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 [[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 algoritma v jezikih [[Programski jezik C|C]] in [[C++]] ==
<source lang="c">
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
</source>
Vrstica 20 ⟶ 28:
<source lang="c">
int gcd(int a, int b) {
int t;
while (b != 0) {
t = b;
b = a % b;
a = t;
}
return a;
}
</source>
| |||