Evklidov algoritem: Razlika med redakcijama
m r2.7.3) (Robot: Dodajanje he:מחלק משותף מקסימלי |
m Bot: Migracija 39 interwikija/-ev, od zdaj gostuje(-jo) na Wikipodatkih, na d:q230848 |
||
Vrstica 43: | Vrstica 43: | ||
{{Link FA|en}} |
{{Link FA|en}} |
||
[[ar:خوارزمية أقليدس]] |
|||
[[bg:Алгоритъм на Евклид]] |
|||
[[bn:ইউক্লিডীয় এলগরিদম]] |
|||
[[ca:Algorisme d'Euclides]] |
|||
[[cs:Eukleidův algoritmus]] |
|||
[[de:Euklidischer Algorithmus]] |
|||
[[el:Αλγόριθμος του Ευκλείδη]] |
|||
[[en:Euclidean algorithm]] |
|||
[[eo:Eŭklida algoritmo]] |
|||
[[es:Algoritmo de Euclides]] |
|||
[[fa:الگوریتم اقلیدس]] |
|||
[[fi:Eukleideen algoritmi]] |
|||
[[fr:Algorithme d'Euclide]] |
|||
[[he:מחלק משותף מקסימלי]] |
[[he:מחלק משותף מקסימלי]] |
||
[[hu:Euklideszi algoritmus]] |
|||
[[id:Algoritma Euklidean]] |
|||
[[it:Algoritmo di Euclide]] |
|||
[[ja:ユークリッドの互除法]] |
|||
[[ko:유클리드 호제법]] |
|||
[[lt:Euklido algoritmas]] |
|||
[[lv:Eiklīda algoritms]] |
|||
[[ml:യൂക്ലിഡിന്റെ അൽഗൊരിതം]] |
|||
[[mn:Евклидийн алгоритм]] |
|||
[[nds:Euklidsch Algorithmus]] |
|||
[[nl:Algoritme van Euclides]] |
|||
[[nn:Euklidsk algoritme]] |
|||
[[no:Euklids algoritme]] |
|||
[[pl:Algorytm Euklidesa]] |
|||
[[pms:Algoritm d'Euclid]] |
|||
[[pt:Algoritmo de Euclides]] |
|||
[[ro:Algoritmul lui Euclid]] |
|||
[[ru:Алгоритм Евклида]] |
|||
[[simple:Euclidean algorithm]] |
|||
[[sk:Euklidov algoritmus]] |
|||
[[sr:Еуклидов алгоритам]] |
|||
[[sv:Euklides algoritm]] |
|||
[[tr:Öklid algoritması]] |
|||
[[uk:Алгоритм Евкліда]] |
|||
[[vi:Giải thuật Euclid]] |
|||
[[zh:輾轉相除法]] |
Redakcija: 21:44, 8. marec 2013
Evklídov algorítem je postopek, s katerim določimo 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 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 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 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;
}