Ước số chung lớn nhất (greatest common divisor – GCD) của hai số nguyên a và b được định nghĩa như là số nguyên lớn nhất mà a và b đều chia hết. Ví dụ, GCD của 16 và 28 là 4.
Trong bài viết (Building Abstractions with Data) khi chúng ta nghiên cứu cách để thực thi một đại số quan hệ, chúng ta cần tính GCD của chúng đến tử số và mẫu số nhỏ nhất có thể. Cách để tìm GCD của hai số nguyên là phân tích chúng và tìm thừa số chung, nhưng có một thuật toán hiệu quả hơn nhiều.
Ý tưởng của thuật toán dựa trên sự suy diễn rằng, nếu r là số dư khi chia a với b, thì các ước số chung lớn nhất của a và b cũng giống như ước số chúng của b và r. Và rồi, chúng ta sử dụng hằng đẳng thức như sau:
GCD(a,b) = GCD(b,r)
Liên tục giảm vấn đề tính GCD đến vấn đề tính GCD của các cặp số nguyên nhỏ hơn.
GCD(206,40) = GCD(40,6) = GCD(6,4) = GCD(4,2) = GCD(2,0) = 2
Giảm GCD(206, 24) đến GCD(2,0) , nó là 2. Như bạn cũng thấy rằng việc bắt đầu với hai số nguyên bất kì và ước số được lặp lại sẽ luôn tạo ra một cặp giá trị mới nơi số thứ hai sẽ là 0 ở cặp kết thúc. Và GCD là một số khác trong cặp đó. Phương thức tìm ước chúng lớn nhất được gọi là thuật toán Euclid’.
Và có thể được trình diễn bằng một thủ tục đệ quy như sau:
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
Tiến trình tính toán này là một tiến trình lặp. Số lượng bước để tính toán tăng tương ứng với log của các số ban đầu.
Bài viết tiếp theo: Ví dụ về việc kiểm tra xem một số có phải số nguyên tố hay không?
One thought on “Ước số chung lớn nhất. Greatest common divisor – GCD.”