Tam giác Pascal trong C++

Tam giác Pascal là mảng các hệ số nhị thức. Hàng đầu n=0, mỗi hàng đánh số từ trái k=0. Mỗi số = tổng 2 số ở hàng trước ngay trên nó. Cũng bằng C(n,k) = n!/(k!(n-k)!).

Ví dụ n=10

                     1
                   1 1
                 1 2 1
               1 3 3 1
             1 4 6 4 1
           1 5 10 10 5 1
         1 6 15 20 15 6 1
       1 7 21 35 35 21 7 1
     1 8 28 56 70 56 28 8 1
   1 9 36 84 126 126 84 36 9 1

Thuật toán

• Với i = 0 đến n-1:
  • In khoảng trắng cho hình tam giác
  • Với j = 0 đến i: tính C(i, j)

Chương trình C++

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

long fact(long n) {
    int i, fact = 1;
    for (i = n; i > 1; i--) fact *= i;
    return fact;
}

long nCr(long n, long r) {
    long nume = 1, i;
    for (i = n; i > r; i--) nume *= i;
    return long(nume / fact(n - r));
}

void genPascalsTriangle(long n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (n - i - 1); j++)
            cout << setw(3) << " ";
        for (int j = 0; j < (i + 1); j++)
            cout << setw(3) << nCr(i, j) << setw(3) << " ";
        cout << endl;
    }
}

int main() {
    int n;
    cout << "Enter Number of lines: "; cin >> n;
    genPascalsTriangle(n);
}

Kết quả n=10

                         1
                       1 1
                     1 2 1
                   1 3 3 1
                 1 4 6 4 1
               1 5 10 10 5 1
             1 6 15 20 15 6 1
           1 7 21 35 35 21 7 1
         1 8 28 56 70 56 28 8 1
       1 9 36 84 126 126 84 36 9 1

Tối ưu hóa

Thay vì tính giai thừa, có thể dùng công thức truy hồi: C(n,k) = C(n,k-1) × (n-k+1)/k để tránh tràn số và nhanh hơn.