Thuật toán tăng tốc trong c++

1. Bài toán minh họa cơ bản về tốc độ

Cho một số nguyên không âm n.

Hãy tính tổng các chữ số của n.

Ví dụ: n = 12345

Tổng chữ số = 1 + 2 + 3 + 4 + 5 = 15.

2. Các thuật toán tăng tốc

Thuật toán sử dụng vòng lặp while

Ý tưởng: Dùng phép chia lấy dư cho 10 để lấy chữ số cuối cùng, sau đó chia nguyên cho 10 để bỏ chữ số cuối cùng.

long long tongchuso(long long n)

{

    long long kq = 0;

    while (n > 0)

    {

        kq += n % 10;

        n /= 10;

    }
    return kq;

}

Đặc điểm:

• Không cần sử dụng mảng để lưu kết quả.
• Độ phức tạp thời gian: O(log n).
• Phù hợp khi chỉ cần tính tổng chữ số của một số hoặc một số lượng nhỏ các số.

Thuật toán Memoization (ghi nhớ kết quả)

Ý tưởng: Khi tính tổng chữ số của một số lần đầu, lưu kết quả vào mảng. Nếu cần tính lại số đó, lấy kết quả đã lưu thay vì tính lại từ đầu.

const int MAXN = 1000000;

long long tong[MAXN + 1];

bool daTinh[MAXN + 1];

long long tongchuso(long long s)

{

    if (s < 0 || s > MAXN)

        return -1;
    if (daTinh[s])

        return tong[s];
    long long n = s;

    long long kq = 0;
    while (n > 0)

    {

        kq += n % 10;

        n /= 10;

    }
    tong[s] = kq;

    daTinh[s] = true;
    return tong[s];

}

Đặc điểm:

• Lần đầu tính một số: O(log n).
• Lần sau tính lại số đó: O(1).
• Cần sử dụng mảng để lưu kết quả và mảng đánh dấu.
• Phù hợp khi có nhiều truy vấn nhưng thường xuyên lặp lại cùng một số.

Thuật toán Quy hoạch động (Dynamic Programming)

Ý tưởng: Tính trước tổng chữ số của tất cả các số từ 0 đến MAXN. Dựa vào kết quả của số đã bỏ đi chữ số cuối cùng để tính số hiện tại. Công thức:

tong[i] = tong[i / 10] + i % 10;

Ví dụ:

• tong[123] = tong[12] + 3.
• tong[12] = tong[1] + 2 = 3.
• tong[123] = 3 + 3 = 6.

Chương trình hoàn chỉnh:

#include <iostream>

using namespace std;

const int MAXN = 1000000;

long long tong[MAXN + 1];
int main()

{

    for (int i = 1; i <= MAXN; i++)

    {

        tong[i] = tong[i / 10] + i % 10;

    }
    cout << tong[12345] << endl;

    cout << tong[6789] << endl;
    return 0;

}

Đặc điểm:

• Thời gian tính trước toàn bộ bảng: O(MAXN).
• Mỗi truy vấn sau khi tính trước: O(1).
• Cần sử dụng mảng để lưu kết quả.
• Phù hợp khi có rất nhiều truy vấn và các số đều nằm trong giới hạn MAXN.

3. So sánh cơ bản

4. Kinh nghiệm về tăng tốc tính toán

• Nếu chỉ tính vài số, nên dùng vòng lặp while.
• Nếu thường xuyên tính lại cùng một số, có thể dùng Memoization.
• Nếu có hàng trăm nghìn hoặc hàng triệu truy vấn trong một giới hạn xác định, nên cân nhắc quy hoạch động để tính trước.

Lưu ý: Với số rất lớn như 10^12, không thể dùng mảng có kích thước 1.000.001 để lưu kết quả cho mọi số. Khi đó, vòng lặp while thường là lựa chọn phù hợp nếu không có thêm yêu cầu đặc biệt.