Lập trình C/C++

Thuật toán tìm ƯCLN với C++

Posted on 21/01/202221/01/2022 by Đỗ Thành

21
Th1

View: 68

Ướ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. Đây là một thuật toán được sử dụng khá phổ biến trong lập trình, trong bài viết này chúng tôi xin được chia sẻ với các bạn 4 thuật toán tìm ƯCLN của 2 số:

1. Thuật toán sử dụng phép trừ

int uc_tru(int a, int b){
    if(a == 0 || b == 0) { return a;}
    while (a!=b){
        if (a > b) {a -= b;}
        else {b -= a;}
    }
    return a;
}

2. Thuật toán sử dụng phép chia

int uc_chia(int a, int b){
    while (a*b != 0) {
        if (a > b) {
            a %= b;
        }
        else {
            b %= a;
        }
    }
    return a + b; 
}

3. Thuật toán sử dụng đệ quy

int uc_Dequy(int a, int b) {
    int temp;
    if(b == 0) return a;
    return uc_Dequy(b, a % b);
}

4. Thuật toán sử dụng hàm có sẵn trong C++

Với thuật toán này, chúng ta cần khai báo thêm thư viện algorithm:

cout << "UCLN(" << a << ", " << b << ") = " << __gcd(a, b);

Tham khảo phần Code chúng tôi đã thực hiện:

#include<iostream>
#include <algorithm>

using namespace std;
// Thuat toan su dung phep tru:
int uc_tru(int a, int b){
    if(a == 0 || b == 0) { return a;}
    while (a!=b){
        if (a > b) {a -= b;}
        else {b -= a;}
    }
    return a;
}
// Thuat toan su dung phep chia:
int uc_chia(int a, int b){
    while (a*b != 0) {
        if (a > b) {
            a %= b;
        }
        else {
            b %= a;
        }
    }
    return a + b; // Vi luc nay mot trong hai so a hoac b bang 0
}
// Thuat toan su dung de quy
int uc_Dequy(int a, int b) {
    int temp;
    if(b == 0) return a;
    return uc_Dequy(b, a % b);
}

int main(){
    int a, b;
    cout << "Nhap 2 so:" << endl;
    cout << "a = "; cin >> a;
    cout << "b = "; cin >> b;
    cout << endl << "Su dung phep tru: ";
    cout << "UCLN(" << a << ", " << b << ") = " << uc_tru(a, b);
    cout << endl << "Su dung phep chia: ";
    cout << "UCLN(" << a << ", " << b << ") = " << uc_chia(a,b);
    cout << endl << "Su dung De quy: ";
    cout << "UCLN(" << a << ", " << b << ") = " << uc_Dequy(a, b);
    cout << endl << "Su dung Ham co san: ";
    cout << "UCLN(" << a << ", " << b << ") = " << __gcd(a, b);
    return 0;
}

Trả lời Hủy