Thuật toán tìm ước chung lớn nhất của hai số nguyên bằng C/C++
Trong bài viết này ta sẽ tìm hiểu cách tìm ra ước chung lớn nhất của hai số nguyên. Về thuật toán thì cơ bản nó được áp dụng cho tất cả các ngôn ngữ lập trình không riêng gì C/C++, còn ở đây mình xin phép sử dụng C/C++ để minh họa. Trước tiên ta hãy tìm hiểu ước chung lớn nhất là gì?
Định nghĩa ước chúng lớn nhất.
"Trong toán học, số nguyên dương x lớn nhất là ước của cả hai số nguyên a, b được gọi là ước số chung lớn nhất (GCD-Greatest Common Divisor) của a và b. Trong trường hợp cả hai số nguyên a và b đều bằng 0 thì chúng không có ƯCLN vì khi đó mọi số tự nhiên khác không đều là ước chung của a và b. Nếu chỉ một trong hai số a hoặc b bằng 0, số kia khác 0 thì ƯCLN của chúng bằng giá trị tuyệt đối của số khác 0."
Một số thuật toán tìm ước chung lớn nhất
Cách 1. Sử dụng phép trừ
Đây là lưu đồ thuật toán này:
Sau đây là đoạn code minh họa:
Cách 2. Sử dụng phép chia lấy phần dư
Về cơ bản thì thuật toàn này khá giống với cách 1 chỉ khác chút là điều kiện và phép toán ta sử dụng ở đây là phép chia lấy dư. Hãy xem qua lưu đồ này để rõ hơn nhé:
Còn đây là đoạn code mà mình sử dụng:
Cách 3. Sử dụng thuật toán Eculid
Thuật toán này có từ năm 300 trước công nguyên, do nhà toán học người Hy Lạp cổ Eculid tìm ra, ông đã viết về thuật toán này cuốn sách "Elements".
"Bắt đầu với cặp số nguyên dương a, b(a>b) ta tạo ra cặp số nguyên dương mới với số b là số nhỏ hơn và số còn lại là r là phần dư của phép chia lấy dư của a cho b. Quá trình này tiếp tục cho tới khi hai số này bằng nhau, đó chính là ƯCLN của a và b."
Còn đây là đoạn code minh họa:
Chúng ta còn có thể cài đặt đệ quy cho thuật toán này:
Cách 4. Sử dụng hàm có sẵn trong C++
Với cách này khá đơn giản vì C++ có sẵn một hàm tìm ƯCLN, ta chỉ việc khai báo thêm thư viện algorithm để sử dụng.
Hàm này có thể code như sau:
Thuật toán tìm ước chung lớn nhất
Trả lờiXóa