Evklidov algoritem: Razlika med redakcijama

odstranjenih 35 zlogov ,  pred 12 leti
m
slog
m (dp)
m (slog)
'''EvklidovEvklídov algoritemalgorítem''' [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 potrebopotrebno [[faktorizacijapraš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 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).
 
Zapis algoritma z [[rekurzija|rekurzijo]]:
'''else''' '''return''' gcd(b, a '''mod''' b)
 
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''²²).
 
== Zapis algoritma v jezikih [[Programski jezik C|C]] in [[C plus plus|C++]] ==
<source lang="c">
<pre><nowiki>
int gcd(int a, int b) {
if (b == 0)
return gcd(b, a % b);
}
</source>
</nowiki></pre>
 
Ali [[iteracija|iterativna]] različica:
 
<source lang="c">
<pre><nowiki>
int gcd(int a, int b) {
int t;
return a;
}
</source>
</nowiki></pre>
 
[[Kategorija:Algoritmi]]
19.279

urejanj