Evklidov algoritem: Razlika med redakcijama

Jump to navigation Jump to search
dodanih 829 zlogov ,  pred 5 leti
brez povzetka urejanja
(ods. Link FA/GA)
 
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.
 
== 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 je rešitev pravilna!'''
 
== Opis algoritma ==
Brezimni uporabnik

Navigacijski meni

Osebna orodja

Imenski prostori

Različice

Več