อัลกอริทึมแบบยุคลิดสำหรับการคำนวณ GCD ใน JavaScript

ในทางคณิตศาสตร์ อัลกอริธึมของ Euclid เป็นวิธีการคำนวณตัวหารร่วมมาก (GCD) ของตัวเลขสองตัว ซึ่งเป็นจำนวนที่มากที่สุดที่หารทั้งสองตัวโดยไม่เหลือเศษ

อัลกอริธึมแบบยุคลิดตั้งอยู่บนหลักการที่ว่าตัวหารร่วมมากของจำนวนสองตัวจะไม่เปลี่ยนแปลงหากจำนวนที่มากกว่าถูกแทนที่ด้วยผลต่างด้วยจำนวนที่น้อยกว่า

ตัวอย่างเช่น 21 คือ GCD ของ 252 และ 105 (เนื่องจาก 252 =21 × 12 และ 105 =21 × 5) และหมายเลขเดียวกัน 21 จะเป็น GCD ของ 105 และ 252 − 105 =147 ด้วย

เนื่องจากการแทนที่นี้จะลดจำนวนที่มากกว่าของตัวเลขสองตัว การทำซ้ำขั้นตอนนี้จะทำให้คู่ของตัวเลขมีขนาดเล็กลงเรื่อยๆ จนกว่าตัวเลขทั้งสองจะเท่ากัน เมื่อสิ่งนั้นเกิดขึ้น จะเป็น GCD ของตัวเลขสองตัวดั้งเดิม

โดยการย้อนกลับขั้นตอน GCD สามารถแสดงเป็นผลรวมของตัวเลขเดิมสองตัวคูณด้วยจำนวนเต็มบวกหรือลบ เช่น 21 =5 × 105 + (−2) × 252

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่ใช้ตัวเลขสองตัวและใช้อัลกอริทึมของ Euclid ในการคำนวณ GCD (ตัวหารร่วมที่ยิ่งใหญ่ที่สุด)

ตัวอย่าง

ต่อไปนี้เป็นรหัส -

const num1 = 252;
const num2 = 105;
const findGCD = (num1, num2) => {
   let a = Math.abs(num1);
   let b = Math.abs(num2);
   while (a && b && a !== b) {
      if(a > b){
         [a, b] = [a - b, b];
      }else{
         [a, b] = [a, b - a];
      };
   };
   return a || b;
};
console.log(findGCD(num1, num2));

ผลลัพธ์

ต่อไปนี้เป็นผลลัพธ์บนคอนโซล -