Eiklīda algoritms

Vikipēdijas raksts

Eiklīda algoritms skaitļu teorijā ir paņēmiens divu veselu skaitļu lielākā kopīgā dalītāja (LKD) atrašanai, vispirms nepilni izdalot lielāko skaitli ar mazāko un tad katrā nākamajā solī iepriekšējās darbības dalītāju savukārt dalot ar iegūto atlikumu. LKD ir pēdējais iegūtais nenulles atlikums.

Ievērojami ir tas, ka algoritmam nav nepieciešams sadalīt skaitļus pirmreizinātājos, kā arī tas, ka šis ir viens no vecākajiem zināmajiem algoritmiem.

[izmainīt šo sadaļu] Piemērs

$LKD (336, 287) = ? \$

$336 : {\color {Magenta} 287} = 1, atl. \color {red} 49$
${\color {Magenta} 287} : {\color {red} 49} = 5, atl. \color {blue} 42$
${\color {red} 49} : {\color {blue} 42} = 1, atl. \color {Magenta} \mathbf {7}$
${\color {blue} 42} : {\color {Magenta} 7} = 6, atl. \mathbf {0}$

Tātad $L K D (336,287) = 7$ .

[izmainīt šo sadaļu] Vēsture

Eiklīds šī algoritma uzdevumu sākotnēji formulēja ģeometriski – kā divu nogriežņu lielākā kopīgā mēra atrašanu. Tādā gadījumā no garākā nogriežņa tika atņemts īsākais, tad atlikums tika atņemts no īsākā nogriežņa utt.

Šādā formā algoritms parādījās Eiklīda "Elementos" apmēram 300 g. p.m.ē. Tomēr, iespējams, ka tas jau bija zināms līdz pat 200 gadiem agrāk. Piemēram, Aristotelis devis mājienu par šo algoritmu savā grāmatā "Tēmas" (Τοπικων/Topica) apmēram 330 g. p.m.ē.

Kategorijas: Algoritmi | Matemātika

See also ebooksgratis.com: no banners, no cookies, totally FREE.

Eiklīda algoritms

Vikipēdijas raksts

[izmainīt šo sadaļu] Piemērs

[izmainīt šo sadaļu] Vēsture

Views

Navigācija

Meklēt

Citās valodās