Trong toán học, thuật toán Euclid, là một phương pháp để tính ước số chung lớn nhất (GCD) của hai số, số lớn nhất chia cả hai mà không để lại phần dư.
Thuật toán Euclide dựa trên nguyên tắc rằng ước chung lớn nhất của hai số không thay đổi nếu số lớn hơn được thay bằng hiệu của nó bằng số nhỏ hơn.
Ví dụ:21 là GCD của 252 và 105 (252 =21 × 12 và 105 =21 × 5), và cùng một số 21 cũng là GCD của 105 và 252 - 105 =147.
Vì sự thay thế này làm giảm số lớn hơn trong hai số, nên lặp lại quá trình này sẽ cho các cặp số nhỏ hơn liên tiếp cho đến khi hai số trở nên bằng nhau. Khi điều đó xảy ra, chúng là GCD của hai số ban đầu.
Bằng cách đảo ngược các bước, GCD có thể được biểu thị dưới dạng tổng của hai số ban đầu, mỗi số nhân với một số nguyên dương hoặc âm, ví dụ:21 =5 × 105 + (−2) × 252.
Chúng tôi được yêu cầu viết một hàm JavaScript có hai số và sử dụng thuật toán Euclid để tính GCD (ước số chung lớn nhất) của chúng
Ví dụ
Sau đây là mã -
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)); Đầu ra
Sau đây là kết quả trên bảng điều khiển -
21