Evklidov algoritem: Razlika med redakcijama
Brez povzetka urejanja |
Brez povzetka urejanja |
||
Vrstica 28: | Vrstica 28: | ||
11 584 : 16 = 724 |
11 584 : 16 = 724 |
||
'''Torej |
'''Torej Evklidov algoritem deluje!''' |
||
== Opis algoritma == |
== Opis algoritma == |
Redakcija: 17:14, 3. april 2015
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.
Praktična uporaba
Pravzaprav je Evklidov algoritimen eden izmed najlažjih algoritmov. Vzemimo za primer, da imamo dve števili; 10 288 in 11 584. Pri ugotavljanju največjega skupnega delitelja nam bo Evklidov algoritem prišel prav. Začnemo tako, da večje število delimo z manjšim tako da dobimo število in ostanek - med njiju vstavimo +;
11 584 : 10 288 = 1 + 1296
Zatem delitelj delimo z ostankom in postopek ponavljamo, dokler ostanek ni nič. Delitelj v tem računu, kjer je ostanek nič je največji skupni delitelj:
11 584 : 10 288 = 1 + 1296
10 288 : 1296 = 7 + 1216
1296 : 1216 = 1 + 80
1216 : 80 = 15 + 16
80 : 16 = 5 + 0
Največji skupni delitelj števil 10 288 in 11 584 je torej 16. To lahko tudi preverimo;
10 288 : 16 = 643
11 584 : 16 = 724
Torej Evklidov algoritem deluje!
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;
}