Thuật toán tìm ước chung lớn nhất trong C/C++

Thuật toán tìm ước chung lớn nhất của hai số nguyên
Thuật toán tìm ước chung lớn nhất của hai số nguyên

Trong bài viết này tôi sẽ cùng các bạn tìm hiểu về các thuật toán tìm ước chung lớn nhất của hai số nguyên và minh họa code bằng ngôn ngữ C/C++.

Định nghĩa ước chung lớn nhất

Ước chung lớn nhất (GCD – Greatest Common Divisor) của 2 số nguyên  và  là số nguyên lớn nhất  thỏa mãn tính chất cả a và b đều chia hết cho d.

Các thuật toán tìm ước chung lớn nhất

Dưới đây là một số cách thường được sử dụng để giải quyết bài toán tìm ước chung lớn nhất của hai số.

Cách 1. Tìm UCLN sử dụng phép trừ

Đây là sơ đồ của thuật toán này

Thuật toán tìm ước chung lớn nhất sử dụng phép trừ
Thuật toán tìm ước chung lớn nhất sử dụng phép trừ

Code minh họa

Giải thích:

 

Xem thêm: Các chia sẻ hay được đúc kết từ kinh nghiệm của tác giả

Cách 2. Tìm UCLN sử dụng phép chia dư

Sơ đồ thuật toán tương tự như cách 1. Chỉ thay đổi phép trừ sang phép chia dư.

Code minh họa

Cách 3. Tìm UCLN sử dụng giải thuật Euclid

Cho a, b là hai số nguyên (giả sử a ≥ b), để tìm ước chung lớn nhất của hai số a và b ta cần thực hiện chia a cho b được thương q và số dư r (r ≥ 0) tức là a = b*q + r, khi đó ta có:

Thuật toán tìm ước chung lớn nhất của hai số nguyên sử dụng C++

Cài đặt thuật toán sử dụng đệ quy.

Cài đặt khử đệ quy

Gợi ý: Một số bài viết về giải thuật tương tự

Cách 4. Tìm UCLN sử dụng hàm có sẵn của C++

Để có thể sử dùng hàm tìm ucln trong C++ ta cần thêm thư viện algorithm.

Ví dụ minh họa:

Tổng kết tất cả cách cách trên trong 1 chương trình.

Kết quả chạy thử

Trên đây tôi đã trình bày chi tiết về các thuật toán tìm ước chung lớn nhất của hai số. Nếu bạn đọc quan tâm hay có thắc mắc gì. Vui lòng để lại ở bình luận phía cuối bài viết.

Nếu bạn quan tâm đến tìm BCNN của 2 số, vui lòng chuyển qua bài viết tìm BCNN của 2 số nhé.

avatar
  Subscribe  
newest oldest most voted
Notify of
Nguyen Hai
Guest
Nguyen Hai

Có thể giải thích rõ hơn về từng cách đc ko ạ? Ví dụ như: Thuật toán trừ dần. Cho a = 7, b = 5. Ta có: a > b và theo đk thì trừ tới khi nào a == b thì dừng, thoát khỏi vòng lặp. Theo như cách hiểu đó của em thì, giả sử, a = a – b như vậy, ta có: a = 7 – 5 = 2. a = 2 – 5 = -3. a = -3 – 5 = -8. a = -8 – 5 = -13. Vậy cứ như thế biết… Read more »

nguyễn hoc
Guest
nguyễn hoc

anh dùng ide nào vậy anh

Cường Nguyễn Công
Member
Cường Nguyễn Công

cho em hỏi độ phức tạp của __gcd trong c++ là bao nhiêu vậy anh ?