Евклидийн алгоритм
Евклидийн алгоритм гэдэг нь 2 натурал тооны хамгийн их ерөнхий хуваагчийг олох аргуудын нэг юм.
2 бодит тоо a, b (a ≧ b)-гийн хувьд a-г b-д хуваахад гарах үлдэгдлийг r гэвэл a ба b-гийн хамгийн их ерөнхий хуваагч нь b ба r-ийн хамгийн их ерөнхий хуваагчтай тэнцүү байдаг. Энэхүү шинж чанарыг ашиглан цааш b-г r-д хуваахад гарах үлдэгдлийг олох гэх мэтээр явсаар үлдэгдэл нь 0 болох хүртэл үргэлжлүүлэн a ба b-гийн хамгийн их ерөнхий хуваагчийг олдог.
Энэ нь МЭӨ 300 оны орчимд бичигдсэн, Евклидийн "Эхлэл" зохиолын 7-р бүлгийн 1-3-т бичигдсэн байдаг.
Программ ашиглаж математикийн бодлого бодох үед ихэвчлэн ашиглагдана. Хамгийн түгээмэл алгоритмын нэг бөгөөд (a) дээд, (b) доод хязгаараас дөхөлт хийдэг онцлогтой.
Жишээ[засварлах | кодоор засварлах]
(Бодлого) 1071 ба 1029-ийн хамгийн их ерөнхий хуваагчийг ол.
- 1071-ээс 1029-г хасахад гарах үлдэгдэл 42
- 1029-г 42-т хуваахад гарах үлдэгдэл 21
- 42-г 21-т хуваахад гарах үлдэгдэл 0
Иймд 1071 ба 1029-ийн хамгийн их ерөнхий хуваагч нь 21 болно.
![]() |
Энэ алгоритм ба өгөгдлийн бүтэц тухай өгүүлэл хэт богино байна. Үүнийг өргөжүүлж Википедиад туслаарай. |
![]() |
Энэ тооны онол тухай өгүүлэл хэт богино байна. Үүнийг өргөжүүлж Википедиад туслаарай. |