Евклидийн алгоритм

Евклидийн алгоритм гэдэг нь 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 болно.

Энэ өгөгдлийн бүтэц ба алгоритмын тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.

Энэ тооны онолын тухай өгүүлэл дутуу дулимаг бичигджээ. Нэмж гүйцээж өгөхийг хүсье.