Chương trình Python thuật toán Euclid mở rộng

Trong bài viết này, chúng ta sẽ tìm hiểu giải pháp cho bài toán sau:

Đề bài – Cho hai số, cần tính GCD (ƯCLN) của hai số đó và hiển thị.

GCD (Greatest Common Divisor) là số lớn nhất chia hết cả hai. Cách Euclid: chia liên tục đến khi dư = 0. Mở rộng dựa trên giá trị trước trong đệ quy.

Hãy quan sát giải pháp trong triển khai dưới đây:

Ví dụ

# Euclid mở rộng
def gcdExtended(a, b, x, y):
    # Base Case
    if a == 0:
        x = 0
        y = 1
        return b
    x1 = 1
    y1 = 1
    gcd = gcdExtended(b % a, a, x1, y1)
    # cập nhật x, y từ giá trị trước
    x = y1 - (b // a) * x1
    y = x1
    return gcd

x = 1
y = 1
a = 11
b = 15
g = gcdExtended(a, b, x, y)
print("ƯCLN của", a, "&", b, "là =", g)

Kết quả

ƯCLN của 11 & 15 là = 1

Kết luận

Trong bài này, chúng ta đã học cách làm chương trình Python thuật toán Euclid mở rộng.