Hiểu bài toán

Xây dựng và in ra tam giác Pascal với n dòng. Tam giác Pascal được định nghĩa: dòng đầu tiên (dòng 0) chỉ có số 1; mỗi dòng tiếp theo có số đầu và số cuối bằng 1; các số ở giữa là tổng hai số ở ngay phía trên của nó. Yêu cầu in ra n dòng, mỗi dòng i (từ 0 đến n-1) chứa i+1 số nguyên, cách nhau bởi dấu cách.

Các cách tiếp cận

Cách Mảng 2 chiều (Dynamic Programming)

#include <bits/stdc++.h>
using namespace std;
const int MAX = 51;
long long pas[MAX][MAX];
void sinhpas(int n){
    pas[0][0] = 1;
    pas[1][0] = 1;
    pas[1][1] = 1;
    for (int i = 2; i < n; i++){
        for (int j = 0; j <= i; j++){
            if ( j==0 || j == i) pas[i][j] = 1;
            else pas[i][j] = pas[i-1][j-1] + pas[i-1][j]; 
        } 
    } 
} 
void inpas(int n){
    for (int i = 0; i < n; i++){
        for (int j = 0; j <= i; j++){
            cout << pas[i][j] << " "; 
        } 
        cout << endl; 
    } 
} 
int main() {
    int n; cin >> n;
    // Khởi tạo dòng 0 và 1
    pas[0][0] = 1;
    if (n > 1) {
        pas[1][0] = 1;
        pas[1][1] = 1;
    }
    // Tính toán các dòng còn lại
    for (int i = 2; i < n; i++) {
        pas[i][0] = 1;
        pas[i][i] = 1;
        for (int j = 1; j < i; j++) {
            pas[i][j] = pas[i-1][j-1] + pas[i-1][j];
        }
    }
    // In ra
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << pas[i][j] << (j < i ? " " : "");
        }
        cout << "\n";
    }
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Phương pháp này sử dụng một mảng 2 chiều pas[n][n] để lưu trữ tất cả các giá trị của tam giác Pascal. Chúng ta điền vào mảng theo quy tắc: các biên bằng 1, và các phần tử bên trong bằng tổng hai phần tử ở dòng trên. Cuối cùng, chúng ta duyệt qua mảng để in ra kết quả. Đây là cách tiếp cận trực quan nhất, dễ hiểu và dễ cài đặt.

Cách Tính toán trực tiếp (Combinatorics)

#include <iostream>
using namespace std;

long long MulDiv(long long x, long long y, long long z) {
    long long m = x, n = z;
    while (n != 0) {
        long long r = m % n;
        m = n;
        n = r;
    }
    x /= m;
    z /= m;
    return x * (y / z);
}

void PrintALine(int n) {
    long long c = 1;
    for (int k = 0; k <= n; k++) {
        cout << c;
        if (k < n) cout << " ";
        c = MulDiv(c, n - k, k + 1);
    }
    cout << "\n";
}

int main() {
    int m;
    cin >> m;
    for (int n = 0; n < m; n++)
        PrintALine(n);
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(1)

Cách tiếp cận này dựa trên công thức tính tổ hợp chập k của n (hay phần tử thứ k của dòng thứ n). Thay vì lưu trữ toàn bộ tam giác, ta chỉ cần tính toán từng giá trị một cách trực tiếp.

Giả sử ta đang ở dòng n và cần tính các giá trị C(n, k):

• C(n, 0) = 1
• C(n, k) = C(n, k-1) * (n - k + 1) / k

Để tránh tràn số nguyên (overflow) khi nhân chia, hàm MulDiv được sử dụng. Hàm này tìm ước chung lớn nhất (GCD) của x và z, rút gọn phân số x/z trước khi thực hiện phép nhân với y. Điều này đảm bảo các phép tính được thực hiện trên số nguyên và giữ giá trị đúng trong giới hạn của long long.

Phương pháp này tối ưu về mặt bộ nhớ (O(1)) vì không cần mảng lưu trữ.

Cách Duyệt theo hàng ngang (In-place Update)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> row;

    for (int i = 0; i < n; ++i) {
        // Mở rộng vector cho dòng mới
        if (row.empty()) {
            row.push_back(1);
        } else {
            row.push_back(0); // Thêm phần tử 0 vào cuối để tính toán
            // Tính toán từ phải sang trái để không ghi đè giá trị cũ
            for (int j = row.size() - 1; j > 0; --j) {
                row[j] = row[j - 1] + row[j];
            }
        }

        // In ra dòng hiện tại
        for (int j = 0; j < row.size(); ++j) {
            cout << row[j] << (j < row.size() - 1 ? " " : "");
        }
        cout << "\n";
    }

    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Phương pháp này tối ưu hóa mảng 2 chiều xuống mảng 1 chiều. Chúng ta chỉ cần lưu trữ dòng hiện tại để tính toán dòng tiếp theo.

Quy trình:

1. Bắt đầu với dòng đầu tiên: [1].
2. Để tạo dòng tiếp theo, ta thêm 0 vào cuối mảng (ví dụ: [1, 0]).
3. Duyệt ngược từ cuối mảng về đầu (trừ phần tử đầu tiên), cập nhật a[j] = a[j] + a[j-1].
   • Ví dụ: 1 + 0 = 1 -> [1, 1].
4. In ra mảng sau khi cập nhật.

Cách này dùng O(n) bộ nhớ để lưu dòng hiện tại, tốt hơn so với mảng 2 chiều O(n^2) nhưng vẫn giữ được sự dễ hiểu.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Tam giác Pascal có tính chất đối xứng: C(n, k) = C(n, n-k). Tuy nhiên, với yêu cầu in đầy đủ, ta vẫn cần in cả hai nửa.
• Phần tử ở dòng thứ n, vị trí k có thể tính dựa trên phần tử ở vị trí k-1 cùng dòng: C(n, k) = C(n, k-1) * (n - k + 1) / k.
• Vì n nhỏ (≤ 50), số lớn nhất trong tam giác (ở giữa) có giá trị C(50, 25) xấp xỉ 1.26 * 10^14. Kiểu long long (tối đa ~9 * 10^18) là đủ để lưu trữ mọi giá trị mà không cần sử dụng số học modulo.

Lỗi thường gặp

• Lỗi tràn số (Overflow): Nếu tính toán không cẩn thận, ví dụ n * (n-1) * ... có thể vượt quá giới hạn của int hoặc long long rất nhanh. Cần thực hiện phép chia trước khi nhân hoặc dùng công thức tính tổ hợp lệch.
• Sai quy tắc in ấn: Yêu cầu là các số cách nhau một khoảng trắng. Lỗi thường gặp là in thêm dấu cách ở cuối dòng hoặc thiếu dấu cách giữa các số.
• Lỗi logic tính toán dòng 0 và dòng 1: Đảm bảo xử lý đúng các trường hợp cơ sở khi cài đặt thuật toán tính toán trực tiếp.