Hiểu bài toán

Bài toán yêu cầu tính giai thừa của một số tự nhiên n (n ≤ 12). Giai thừa n! được định nghĩa là tích của các số từ 1 đến n (n! = 1 * 2 * ... * n). Với ràng buộc n ≤ 12, giá trị n! nhỏ hơn 2^31, do đó có thể lưu trữ trong kiểu số nguyên 32-bit.

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

Cách Vòng lặp (Iteration)

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    int gt = 1;
    for (int i = 1; i <= n; i++) {
        gt *= i;
    }
    printf("%d", gt);
    return 0;
}

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

Phương pháp này sử dụng một biến để lưu tích lũy (ví dụ: gt), khởi tạo bằng 1. Sau đó, sử dụng một vòng lặp từ 1 đến n, nhân từng số vào biến tích lũy. Đây là cách tiếp cận trực quan và hiệu quả nhất về mặt thời gian chạy cho bài toán này.

Cách Mảng giá trị事先 (Lookup Table)

#include <stdio.h>
int main() {
    int n;
    scanf("%d", &n);
    static const int res[] = {
        1, 1, 2, 6, 24, 120, 720, 5040, 
        40320, 362880, 3628800, 39916800, 479001600
    };
    printf("%d", res[n]);
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Vì n bị giới hạn nhỏ (n ≤ 12), ta có thể pre-calculate (tính toán trước) tất cả các giá trị giai thừa và lưu vào một mảng cố định. Khi chạy chương trình, chỉ cần truy cập mảng theo chỉ số n để lấy kết quả. Phương pháp này có độ phức tạp thời gian là hằng số O(1).

Cách Sử dụng biến kiểu lớn (Long Long)

#include <stdio.h>
int main (){
    int n;
    long long tich = 1;
    scanf ("%d", &n);
    for (int i = 1; i <= n; i++){
        tich *= i;
    }
    printf ("%lld", tich);
}

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

Đây là biến thể của phương pháp vòng lặp, sử dụng kiểu dữ liệu long long để lưu trữ kết quả thay vì int. Mặc dù với n ≤ 12 thì int là đủ (vì 12! = 479,001,600 < 2^31), nhưng việc sử dụng long long là một thói quen tốt để tránh tràn số (overflow) nếu ràng buộc bài toán thay đổi.

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

Bài học kinh nghiệm

• Với n ≤ 12, giá trị n! không vượt quá 479,001,600, phù hợp với kiểu số nguyên 32-bit.
• Phương pháp tính toán trực tiếp bằng vòng lặp là linh hoạt nhất nếu n có thể thay đổi, trong khi phương pháp mảng lookup table tối ưu nhất về tốc độ cho các giá trị n cố định nhỏ.

Lỗi thường gặp

• Quên khởi tạo biến tích lũy bằng 1 (không phải 0)会导致 kết quả nhân sai.
• Sử dụng kiểu dữ liệu quá nhỏ (như short hoặc int nếu n lớn hơn 12) có thể导致 tràn số (integer overflow).