[Lập trình C] Extra long factorials - Giai thừa siêu lớn

Giai thừa của một số n > 20 thậm chí không thể được lưu trữ trong một biến kiểu long 64-bit. Với những tính toán như vậy, chúng ta cần phải sử dụng Big Integers. Các ngôn ngữ lập trình như Java, Python, Ruby v.v... có thể giúp chúng ta handle Big Integers một cách tương đối dễ dàng. Tuy vậy, đối với C/C++ thì chúng ta cần phải tự xử lý những giá trị lớn như vậy. Đây là một bài tập mà tôi vừa mới làm trên HackerRank, thấy hay nên chia sẻ lại với mọi người.

Yêu cầu:

Nhập vào một số nguyên n sao cho 20 <= n <= 100. Hãy tính và in ra giai thừa của n dựa vào công thức bên dưới.

Ví dụ giai thừa của 30 được tính như sau: 30! = 30 * 29 * 28 * 27 * ... * 3 * 2 * 1 = 265252859812191058636308480000000 (kết quả là một số có tổng cộng 33 chữ số).

Gợi ý:

Tôi sẽ dùng một mảng a có độ lớn khoảng 1000 phần tử với mỗi ô nhớ của mảng sẽ lưu trữ 1 số duy nhất của kết quả cho mỗi bước tính. Ví dụ khi tính 10! thì qua từng bước tính mảng a trông sẽ như sau:

Cách giải này không phải do tôi nghĩ ra mà được tôi tham khảo ở link sau: Extra Long Factorials in C. Để hiểu được một cách cặn kẽ, tôi khuyên bạn nên lấy giấy bút và thử debug lại từng bước lặp bằng tay, khi đó bạn sẽ hiểu rất rõ.

Cài đặt:

Như trong code bên dưới, biến number dùng để duyệt lần lượt các giá trị từ 2 cho đến n. Biến len dùng để chứa độ dài hiện tại của dãy kết quả. Trong bài tập này tôi sử dụng mảng có độ dài cố định 1000 nhưng để tối ưu hơn, các bạn có thể cải tiến sử dụng mảng cấp phát động. Biến carry dùng để chứa số dư. Ví dụ, giả sử tôi đang duyệt ô nhớ có giá trị = 2 và number = 7. Khi đó 2 * 7 = 14 > 10. Tôi sẽ cập nhật giá trị ô nhớ hiện tại = 14 % 10 (lấy dư). Còn biến carry = 14 / 10 = 4. Phần dư carry này sẽ được tôi mang qua tính toán ở ô nhớ tiếp theo.

#include <stdio.h>

void extraLongFactorials(int n) {
    int a[1000] = {0};
    a[0] = 1;
    int number = 2;
    int len = 1;
    
    while (number <= n) {
        int carry = 0;
        int i = 0;
        
        while (i < len) {
            a[i] *= number;
            a[i] += carry;
            carry = a[i] / 10;
            a[i] %= 10;
            i++;
        }
        
        while (carry != 0) {
            a[len] = carry % 10;
            carry /= 10;
            len++;
        }
        
        number++;
    }
    
    len--;
    while(len >=0) printf("%d", a[len--]);
}

int main()
{
    int n;
    printf("n=");
    scanf("%d", &n);
    extraLongFactorials(n);
    return 0;
}