Euclidean Algorithm GCD

เคลื่อนไหวแบบยุคลิดอัลกอริทึม ที่ยิ่งใหญ่ที่สุดหารกัน "เครื่องบด"

อัลกอริทึมแบบยุคลิดแบบเคลื่อนไหว

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)