Rate this post

GCD (Greatest Common Divisor) hoặc UCLN (Ước chung lớn nhất) là giá trị lớn nhất mà là ước của hai hoặc nhiều số nguyên.

Các bài viết liên quan:

Trong C++, có nhiều cách để tính GCD của hai số nguyên, trong đó cách phổ biến nhất là sử dụng thuật toán Euclide.

Ví dụ:

#include <iostream>
using namespace std;

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

int main()
{
    int a = 60, b = 48;
    cout << "GCD cua " << a << " va " << b << " la: " << gcd(a, b) << endl;
    return 0;
}

Trong ví dụ trên, chúng ta đã sử dụng thuật toán Euclide để tính GCD của hai số 60 và 48. Kết quả trả về là 12.

Các thuật toán khác nhau có thể sử dụng để tính GCD, nhưng thuật toán Euclide là một trong những thuật toán tính GCD được sử dụng nhiều nhất vì đơn giản và hiệu quả.

Có một số thuật toán khác được sử dụng để tính GCD của hai số nguyên:

  • Sử dụng vòng lặp: ta có thể duyệt từ 2 đến min(a, b) và tìm ước chung lớn nhất của hai số.
int gcd(int a, int b) 
{
    int gcd = 1;
    for (int i = 2; i <= min(a, b); i++) 
    {
        if (a % i == 0 && b % i == 0) 
        {
            gcd = i;
        }
    }
    return gcd;
}
  • Sử dụng vòng lặp với các toán tử bit: ta có thể sử dụng các toán tử bit để tìm GCD của hai số.
int gcd(int a, int b) 
{
    while (b) 
    {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}
  • Sử dụng thuật toán Stein: là một phiên bản nâng cao của thuật toán Euclide. Nó sử dụng các toán tử bit để tìm GCD của hai số nguyên.
int gcd(int a, int b)
{
    if (a == 0) 
        return b;
    if (b == 0) 
        return a;
    if (~a & 1) 
    {
        if (b & 1) 
            return gcd(a >> 1, b);
        else
            return gcd(a >> 1, b >> 1) << 1;
    }
    if (~b & 1) 
        return gcd(a, b >> 1);
    if (a > b) 
        return gcd((a - b) >> 1, b);
    return gcd((b - a) >> 1, a);
}

Trong tổng quát, chúng ta có thể sử dụng bất kỳ thuật toán nào để tìm GCD của hai số nguyên tùy thuộc vào yêu cầu.

Các thuật toán này đều có thể áp dụng cho bài toán tìm GCD của nhiều số nguyên nhưng tùy thuộc vào yêu cầu cụ thể của bài toán, một thuật toán có thể hiệu quả hơn thuật toán khác.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now