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

Евклидийн алгоритм гэдэг нь 2 натурал тооны хамгийн их ерөнхий хуваагчийг олох аргуудын нэг юм.

2 бодит тоо a, b (ab)-гийн хувьд ab-д хуваахад гарах үлдэгдлийг r гэвэл a ба b-гийн хамгийн их ерөнхий хуваагч нь b ба r-ийн хамгийн их ерөнхий хуваагчтай тэнцүү байдаг. Энэхүү шинж чанарыг ашиглан цааш br-д хуваахад гарах үлдэгдлийг олох гэх мэтээр явсаар үлдэгдэл нь 0 болох хүртэл үргэлжлүүлэн a ба b-гийн хамгийн их ерөнхий хуваагчийг олдог.

Энэ нь МЭӨ 300 оны орчимд бичигдсэн, Евклидийн "Эхлэл" зохиолын 7-р бүлгийн 1-3-т бичигдсэн байдаг.

Программ ашиглаж математикийн бодлого бодох үед ихэвчлэн ашиглагдана. Хамгийн түгээмэл алгоритмын нэг бөгөөд (a) дээд, (b) доод хязгаараас дөхөлт хийдэг онцлогтой.

Жишээ[засварлах | кодоор засварлах]

(Бодлого) 1071 ба 1029-ийн хамгийн их ерөнхий хуваагчийг ол.

  • 1071-ээс 1029-г хасахад гарах үлдэгдэл 42
  • 1029-г 42-т хуваахад гарах үлдэгдэл 21
  • 42-г 21-т хуваахад гарах үлдэгдэл 0

Иймд 1071 ба 1029-ийн хамгийн их ерөнхий хуваагч нь 21 болно.

Stub icon

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

Stub icon

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