Evklidov algoritem: Razlika med redakcijama
m Bot: en:Euclidean algorithm is a featured article |
m robot Dodajanje: bn:ইউক্লিডীয় এলগরিদম; kozmetične spremembe |
||
Vrstica 6: | Vrstica 6: | ||
== Opis algoritma == |
== Opis algoritma == |
||
Če imamo naravni števili ''a'' in ''b'', predpostavimo, da je ''a'' večji ali enak ''b''. Če je ''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]]: |
Zapis algoritma z [[rekurzija|rekurzijo]]: |
||
Vrstica 40: | Vrstica 40: | ||
[[Kategorija:Algoritmi]] |
[[Kategorija:Algoritmi]] |
||
[[Kategorija:Evklid]] |
[[Kategorija:Evklid]] |
||
{{Link FA|en}} |
|||
[[ar:خوارزمية إقليدس]] |
[[ar:خوارزمية إقليدس]] |
||
[[bg:Алгоритъм на Евклид]] |
[[bg:Алгоритъм на Евклид]] |
||
[[bn:ইউক্লিডীয় এলগরিদম]] |
|||
[[ca:Algorisme d'Euclides]] |
[[ca:Algorisme d'Euclides]] |
||
[[cs:Euklidův algoritmus]] |
[[cs:Euklidův algoritmus]] |
||
[[de:Euklidischer Algorithmus]] |
[[de:Euklidischer Algorithmus]] |
||
[[el:Αλγόριθμος του Ευκλείδη]] |
[[el:Αλγόριθμος του Ευκλείδη]] |
||
[[en:Euclidean algorithm]] |
[[en:Euclidean algorithm]] |
||
[[eo:Eŭklida algoritmo]] |
[[eo:Eŭklida algoritmo]] |
||
[[es:Algoritmo de Euclides]] |
[[es:Algoritmo de Euclides]] |
Redakcija: 23:24, 7. december 2009
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 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 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;
}