Thuật toán

#Thuật toán là gì

Định nghĩa này có trước máy tính rất lâu. Thuật toán Euclid tìm ước chung lớn nhất ra đời khoảng năm 300 trước Công nguyên và vẫn là cách tốt nhất tới hôm nay. Chính từ đó cho thấy: thuật toán độc lập với ngôn ngữ lập trình và độc lập với cả máy tính.

Thuật toán Euclid, viết bằng lời:

    Cho hai số nguyên dương a và b.
    Chừng nào b còn khác 0:
        Đặt r là phần dư của a chia b.
        Đặt a là b, đặt b là r.
    Khi b bằng 0 thì a chính là ước chung lớn nhất.

int ucln(int a, int b)
{
    while (b != 0) {
        int r = a % b;

        a = b;
        b = r;
    }

    return a;
}

#Năm tính chất bắt buộc

#Khác gì chương trình

Một thuật toán có thể cài thành nhiều chương trình khác nhau bằng nhiều ngôn ngữ khác nhau. Ngược lại, một chương trình thường là tổ hợp của nhiều thuật toán. Khi bạn học cấu trúc dữ liệu ở Phần 10 và giải thuật ở Phần 11, thứ bạn học là thuật toán, và nó dùng được cho mọi ngôn ngữ bạn học sau này.

#Cùng bài toán, chênh vạn lần

Đây là phần cho thấy vì sao thuật toán đáng học. Xét bài toán rất đơn giản: tính tổng các số từ 1 tới n.

long long tong(int n)
{
    long long s = 0;

    for (int i = 1; i <= n; ++i) {
        s += i;
    }

    return s;
}

long long tong(int n)
{
    return (long long)n * (n + 1) / 2;
}

Không phải bài nào cũng có công thức đóng như trên. Nhưng gần như bài nào cũng có nhiều hướng giải với độ phức tạp khác nhau, và bước 3 của quy trình ở Bài 7.1 tồn tại chính là để bạn cân nhắc chúng.

#Ví dụ: lũy thừa nhanh

Bài toán: tính a mũ n với n là số nguyên không âm. Đây là ví dụ kinh điển cho thấy chia để trị mạnh tới mức nào.

Cách ngây thơ

long long luy_thua_cham(long long a, int n)
{
    long long r = 1;

    for (int i = 0; i < n; ++i) {
        r *= a;
    }

    return r;
}
/* n phép nhân */

Ý tưởng chia đôi

a^n  =  (a^(n/2))^2            nếu n chẵn
a^n  =  a * (a^((n-1)/2))^2    nếu n lẻ

Ví dụ tính 3^10:
    3^10 = (3^5)^2
    3^5  = 3 * (3^2)^2
    3^2  = (3^1)^2
    3^1  = 3 * (3^0)^2

Chỉ cần 4 tầng chia đôi, tổng cộng 6 phép nhân thay vì 10.

Cài đặt bằng vòng lặp

long long luy_thua_nhanh(long long a, int n)
{
    long long r = 1;

    while (n > 0) {
        if (n % 2 == 1) {    /* n lẻ thì nhân thêm một lần a hiện tại */
            r *= a;
        }

        a *= a;              /* bình phương cơ số */
        n /= 2;              /* giảm nửa số mũ */
    }

    return r;
}

cách chậm: 3.812 giây
cách nhanh: 0.000 giây

Cùng ý tưởng cho phép nhân

/* Nhân hai số chỉ bằng phép cộng và phép dịch, cùng ý tưởng chia đôi */
long long nhan_nhanh(long long a, long long b)
{
    long long r = 0;

    while (b > 0) {
        if (b % 2 == 1) {
            r += a;
        }

        a += a;
        b /= 2;
    }

    return r;
}

Nhận ra một ý tưởng dùng lại được ở nhiều bài toán khác nhau chính là điều làm nên người giải thuật giỏi. Phần 11 sẽ hệ thống hóa các nhóm ý tưởng như vậy: chia để trị, tham lam, quy hoạch động và quay lui.