Tổng hợp một số thuật toán cơ bản

Posted on September 23rd, 2016

Thuật toán kiểm tra một số có phải là số chính phương hay không

Tư tưởng là ta sẽ kiểm tra xem các số m từ 1 đến số a xem nếu m*m = a thì số a là số chính phương. Tuy nhiên ta sẽ sử dụng thuật toán chia đôi để nhanh chóng tìm ra kết quả.

bool IsSquareNumber(int a)
{
    int left = 1, right = a, m;
    while(left < right)
    {
        m = (left + right) / 2;
        if(m*m > a) right = m - 1;
        else if(m*m < a) left = m + 1;
        else return true;
    }

    return false;
}

Thuật toán kiểm tra xem một số có là số nguyên tố hay không

bool IsPrimeNumber(int a)
{
    if(a < 2) return false;

    for(int i = 2; i*i <= a; i++)
        if(a % i == 0) return false;
            return true;
}

Thuật toán tạo một mảng đánh dấu các số nguyên tố không lớn hơn n

bool* CreatePrimeArray(int n)
{
    bool *Prime = new bool[n+1];

    for(int i = 0; i <= n; i++)
        Prime[i] = true;
    Prime[0] = Prime[1] = false;

    for(int i = 2; i*i <= n; i++)
        if(Prime[i] == true)
        {
            int j = 2;
            while(i*j <= n)
            {
                Prime[i*j] = false;
                j++;
            }
        }

    return Prime;
}

Thuật toán tìm ước số chung lớn nhất

Ta sẽ tìm ước chung lớn nhất của hai số dựa vào thuật toán Euclid

int GCD(int a, int b)
{
    if(a == 0 && b == 0) return -1;
    if(b == 0 || a == 0) return a + b;
    return GCD(b, a%b);
}

Thuật toán tìm bội số chung nhỏ nhất

Ta sẽ tìm bội số chung nhỏ nhất dựa vào thuật toán tìm ước số chung lớn nhất như trên

int LCM(int a, int b)
{
    if(a == 0 || b == 0) return -1;
    return (abs(a * b) / GCD(a, b));
}

Thuật toán tính giai thừa: n!

int Factorial(int n)
{
    int r = 1;
    for(int i = 1; i <= n; i++)
        r *= i;
    return r;
}

Thuật toán tính tổ hợp chập k của n: C(k,n)

int Combination(int k, int n)
{
    int r = 1;
    for (int i = 1; i <= k; i++,n--)
        r = r * n / i;
    return r;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Thuật toán cơ bản