In tam giác Pascal trong C - 2 cách triển khai

Tam giác Pascal là gì?

Tam giác Pascal là mảng tam giác các số nguyên, trong đó mỗi số là tổng của hai số ngay trên nó. Các ứng dụng: hệ số nhị thức, tổ hợp, xác suất.

Công thức: C(n,k) = n! / (k!(n-k)!)

Cách 1: Sử dụng hàm giai thừa và mảng

#include <stdio.h>

int giaiThua(int n) {
    int ketQua = 1;
    for (int i = 1; i <= n; i++)
        ketQua *= i;
    return ketQua;
}

int main() {
    int rows, i, j;
    
    printf("Nhap so hang: ");
    scanf("%d", &rows);
    
    for (i = 0; i < rows; i++) {
        // In khoảng trắng để căn giữa
        for (j = 0; j <= rows - i - 2; j++)
            printf(" ");
        
        // In các giá trị C(i, j)
        for (j = 0; j <= i; j++) {
            int giaTri = giaiThua(i) / (giaiThua(j) * giaiThua(i - j));
            printf("%d ", giaTri);
        }
        printf("\n");
    }
    
    return 0;
}

Cách 2: Không dùng mảng, không dùng giai thừa (Hiệu quả hơn)

Sử dụng tính chất: C(n,k) = C(n,k-1) * (n-k+1) / k

#include <stdio.h>

int main() {
    int rows, i, j;
    
    printf("Nhap so hang: ");
    scanf("%d", &rows);
    
    for (i = 1; i <= rows; i++) {
        // In khoảng trắng căn giữa
        for (j = 1; j <= rows - i; j++)
            printf(" ");
        
        int giaTri = 1;  // C(i-1, 0) = 1
        for (j = 1; j <= i; j++) {
            printf("%d ", giaTri);
            // Tính giá trị tiếp theo: C(n,k) = C(n,k-1) * (n-k+1)/k
            giaTri = giaTri * (i - j) / j;
        }
        printf("\n");
    }
    
    return 0;
}

Kết quả (rows = 5)

Nhap so hang: 5
        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 1

So sánh 2 cách

Ứng dụng thực tế

• Khai triển nhị thức: (a+b)ⁿ = Σ C(n,k) aⁿ⁻ᵏ bᵏ
• Tổ hợp: số cách chọn k từ n phần tử
• Xác suất phân bố nhị thức