Thuật toán Euclide cơ bản và mở rộng

Thuật toán Euclide cơ bản và mở rộng

Thuật toán Euclide là một thuật toán cổ điển để tìm ước số chung lớn nhất (GCD) của hai số nguyên dương. Thuật toán Euclide cơ bản là như sau:

1. Cho hai số nguyên dương a và b.
2. Nếu a bằng 0, trả về b. Ngược lại, chuyển đổi a và b sao cho a lớn hơn b.
3. Lặp lại các bước sau cho đến khi b bằng 0: a. Tính r = a % b, tức là số dư của phép chia a cho b. b. Gán a = b và b = r.
4. Trả về a, đó là ước số chung lớn nhất của a và b.

Thuật toán Euclide mở rộng là phiên bản mở rộng của thuật toán Euclide cơ bản, cho phép tìm các hệ số Bézout của a và b, tức là tìm các số nguyên x và y sao cho:

ax + by = gcd(a,b)

Thuật toán Euclide mở rộng có thể được thực hiện bằng cách sử dụng thuật toán Euclide cơ bản và đệ quy. Các bước của thuật toán Euclide mở rộng như sau:

1. Cho hai số nguyên dương a và b.
2. Nếu b bằng 0, trả về (1,0,a).
3. Tính (x’, y’, gcd) = extended_gcd(b, a mod b) bằng cách gọi đệ quy với (b, a mod b).
4. Trả về (y’, x’ – (a // b) * y’, gcd), trong đó // là toán tử chia lấy phần nguyên.

Kết quả trả về sẽ là một bộ ba số nguyên (x, y, gcd), với x và y là các hệ số Bézout của a và b và gcd là ước số chung lớn nhất của a và b.

Ví dụ về Thuật toán Euclide cơ bản và mở rộng

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

Cài đặt thuật toán Euclide mở rộng

def extended_gcd(a, b):
    if b == 0:
        return (1, 0, a)
    else:
        x, y, gcd = extended_gcd(b, a % b)
        return (y, x - (a // b) * y, gcd)

Ví dụ sử dụng các hàm trên để tính ước số chung lớn nhất và các hệ số Bézout tương ứng của 60 và 24:

a = 60
b = 24

# Tính ước số chung lớn nhất
print(gcd(a, b))  # Kết quả: 12

# Tính các hệ số Bézout
x, y, gcd = extended_gcd(a, b)
print(x, y, gcd)  # Kết quả: 1 0 12 và 0 1 12

Chú ý rằng thuật toán Euclide mở rộng trả về tất cả các cặp hệ số Bézout tương ứng với các bước đệ quy của thuật toán, vì vậy chúng ta cần chọn cặp phù hợp với mục đích của mình. Ở ví dụ trên, chúng ta chọn hai cặp hệ số Bézout cuối cùng (1, 0, 12) và (0, 1, 12), tương ứng với ước số chung lớn nhất của 60 và 24.

Cài đặt Thuật toán Euclide cơ bản và mở rộng với C++

Để cài đặt thuật toán Euclide cơ bản và mở rộng trong C++, chúng ta cũng có thể sử dụng đệ quy để tìm ước số chung lớn nhất và các hệ số Bézout tương ứng.

Cài đặt thuật toán Euclide cơ bản

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

Cài đặt thuật toán Euclide mở rộng

void extended_gcd(int a, int b, int& x, int& y, int& gcd) {
    if (b == 0) {
        x = 1;
        y = 0;
        gcd = a;
    } else {
        extended_gcd(b, a % b, y, x, gcd);
        y -= (a / b) * x;
    }
}

Ví dụ sử dụng các hàm trên để tính ước số chung lớn nhất và các hệ số Bézout tương ứng của 60 và 24:

#include <iostream>

using namespace std;

int main() {
    int a = 60;
    int b = 24;

    // Tính ước số chung lớn nhất
    cout << gcd(a, b) << endl;  // Kết quả: 12

    // Tính các hệ số Bézout
    int x, y, gcd_res;
    extended_gcd(a, b, x, y, gcd_res);
    cout << x << " " << y << " " << gcd_res << endl;  // Kết quả: 1 0 12 và 0 1 12

    return 0;
}

Chú ý rằng hàm extended_gcd trả về các hệ số Bézout thông qua tham số tham chiếu x và y, và ước số chung lớn nhất thông qua tham số tham chiếu gcd_res. Chúng ta có thể sử dụng các giá trị này cho mục đích của mình sau đó.