Forskel mellem versioner af "Euklids algoritme"

434 bytes fjernet ,  for 1 måned siden
skifter illustration, fordi den er uforståelig, se diskussionssiden
(Simplificere billedteksten en smule. Den er stadig ikke letlæselig.)
Tags: Mobilredigering Mobilwebredigering Avanceret redigering fra mobil
(skifter illustration, fordi den er uforståelig, se diskussionssiden)
[[File:Euklid.jpg|right|thumb|upright|Euklid som den flamske maler [[Justus van Gent]] (ca. 1410 - ca. 1480) forestillede sig ham omkring 1474.]]
[[Fil:Euclid's_algorithm_Book_VII_Proposition_2_3.png|right|thumb|417x417px| Euklids metode til at finde den største fælles divisor (GCD) af to startlængder BA og DC. Længden DC er kortere, det bruges til at måle BA, men kun én gang, fordi resten EA er mindre end DC. EA måler nu (to gange) den kortere længde DC, med resten FC kortere end EA. Derefter måler FC (tre gange) længde EA. Fordi der ikke er nogen rest, ender processen med, at FC er SFD. Til højre [[Nicomachus]]' eksempel med tallene 49 og 21 resulterende i deres SFD på 7 (afledt af Heath 1908: 300). ]]
'''Euklids algoritme'''{{efn|I nogle populære lærebøger, såsom [[I. N. Herstein]]s ''Topics in Algebra'' og [[Serge Lang]]s ''Algebra'', refererer den engelske term "Euclidean algorithm" til [[divisionsalgoritmen]].}} er en matematisk algoritme. Det er en effektiv metode til at beregne den [[største fælles divisor]] (forkortet SFD eller GCD efter ''greatest common divisor''). For to tal er SFD det største tal, der [[Divisor|går op i]] begge tal. Algoritmen er opkaldt efter den [[Ptolemæerriget|græske]] [[matematiker]] [[Euklid]], der først beskrev det i [[Euklids elementer|sine ''Elementer'']] (ca. [[300 f.Kr.]]). Det er et eksempel på en ''[[algoritme]]'', en trin-for-trin-procedure til udførelse af en beregning i henhold til veldefinerede regler, og er en af de ældste algoritmer i almindelig brug. Den kan bruges til at forkorte [[brøk]]er så meget som muligt og er blot en af mange [[Talteori|talteoretiske]] og [[kryptografi]]ske beregningsmetoder.