เคลื่อนไหวแบบยุคลิดอัลกอริทึม ที่ยิ่งใหญ่ที่สุดหารกัน "เครื่องบด"
อัลกอริทึมแบบยุคลิดแบบเคลื่อนไหว
Divisor ทั่วไปที่ยิ่งใหญ่ที่สุด
มีประโยชน์ในการลดเศษส่วน
ขั้นตอนวิธีแบบยุคลิดที่มองเห็นได้
GCD หรือที่รู้จักกันว่าเป็นปัจจัยร่วมที่ยิ่งใหญ่ที่สุด (gcf) ปัจจัยร่วมที่มากที่สุด (hcf) มาตรการที่ใหญ่ที่สุด (gcm) หรือตัวหารทั่วไปที่สูงที่สุด
การแสดงแบบไดนามิกและทางเรขาคณิตของอัลกอริทึม
ขั้นตอนวิธีการเรียกซ้ำ
และน้อยที่สุดที่พบบ่อยหลาย deduced จาก GCD:
lcm (a, b) = a * b / gcd (a, b)
มีประโยชน์ที่จะเข้าใจรหัส recursive gcd (Euclidean Algorithm): (Java)
int gcd (int m, int n) {
ถ้า (0 == n) {
return m;
}อื่น{
return gcd (n, m% n);
}
}
เพิ่มการแสดงข้อมูลทางเรขาคณิต
อัลกอริทึมที่ดำเนินการโดย Dandelions ที่มาจากบริเวณใกล้เคียง Mathematical Garden
Euclidean Algorithm History:
("Pulverizer")
อัลกอริทึมแบบยุคลิดคือขั้นตอนวิธีที่เก่าแก่ที่สุดในการใช้งานร่วมกัน
ปรากฏใน Euclid's Elements (ค.ศ. 300 BC) โดยเฉพาะในหนังสือ 7 (ข้อเสนอ 1-2) และหนังสือ 10 (ข้อเสนอ 2-3)
ศตวรรษต่อมาอัลกอริธึมของ Euclid ถูกค้นพบโดยอิสระทั้งในประเทศอินเดียและในประเทศจีนเพื่อแก้สมการไดโอแฟนไทน์ที่เกิดขึ้นในดาราศาสตร์และสร้างปฏิทินที่ถูกต้อง
ในช่วงปลายศตวรรษที่ 5 นักคณิตศาสตร์ชาวอินเดียและนักดาราศาสตร์ Aryabhata ได้อธิบายขั้นตอนดังกล่าวว่าเป็น "เครื่องบด" ซึ่งอาจเป็นเพราะประสิทธิภาพในการแก้สมการไดโอแฟนไทน์
ขอขอบคุณ:
Joan Jareño (Creamat) (เพิ่มจาก lcm)