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

Saturday, December 26, 2020
Edit this post


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;
}

.
Xin vui lòng chờ đợi
Dữ liệu bài viết đang được tải về

BÌNH LUẬN

Cảm ơn bạn đã đọc bài viết của Cuộc Sống Tối Giản. Đây là một blog cá nhân, được lập ra nhằm mục đích lưu trữ và chia sẻ mọi thứ hay ho theo chủ quan của chủ sở hữu. Có lẽ vì vậy mà bạn sẽ thấy blog này hơi (rất) tạp nham. Mọi chủ đề đều có thể được tìm thấy ở đây, từ tâm sự cá nhân, kinh nghiệm sống, phim ảnh, âm nhạc, lập trình... Phần lớn các bài đăng trong blog này đều được tự viết, trừ các bài có tag "Sponsored" là được tài trợ, quảng cáo, hoặc sưu tầm. Để ủng hộ blog, bạn có thể share những bài viết hay tới bạn bè, người thân, hoặc có thể follow Kênh YouTube của chúng tôi. Nếu cần liên hệ giải đáp thắc mắc hoặc đặt quảng cáo, vui lòng gửi mail theo địa chỉ phipgn@gmail.com. Một lần nữa xin được cảm ơn rất nhiều!!!
© Copyright by CUỘC SỐNG TỐI GIẢN
Loading...