Giai thừa của số lớn (Factorial of Large Number)

Giới thiệu

Trong máy tính, các biến được lưu trữ trong vị trí bộ nhớ. Nhưng kích thước vị trí bộ nhớ là cố định, nên khi ta thử tìm giai thừa của một số lớn như 15! hoặc 20!, giá trị giai thừa vượt quá phạm vi bộ nhớ và trả về kết quả sai.

Để tính toán số lớn, ta phải dùng mảng để lưu kết quả. Mỗi phần tử của mảng lưu một chữ số khác nhau của kết quả. Nhưng ở đây ta không thể nhân một số với mảng trực tiếp, ta phải thực hiện quá trình nhân thủ công cho tất cả các chữ số của mảng kết quả.

Đầu vào và Đầu ra

Đầu vào: Số lớn: 50
Đầu ra: Giai thừa của số cho trước là: 30414093201713378043612608166064768844377641568960512000000000000

Thuật toán

multiply(x, multiplicand)

Đầu vào: Số x, và số lớn multiplicand dưới dạng mảng.

Đầu ra: Kết quả sau nhân.

Begin
    carry := 0
    for all digits i of multiplicand, do
        prod := i*x+carry
        i := prod mod 10
        carry := prod / 10
    done
    while carry ≠ 0, do
        chèn (carry mod 10) vào cuối mảng multiplicand
        carry := carry/10
    done
End

factorial(n)

Đầu vào: Số n.

Đầu ra: Tìm giai thừa của n.

Begin
    định nghĩa mảng result.
    chèn 1 vào result
    for i := 2 to n, do
        multiply(i, result)
    done
    đảo ngược result
    return result
End

Ví dụ (C++)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void multiply(int x, vector<int>& multiplicand) {
    // nhân multiplicand với x
    int carry = 0;  // khởi tạo carry = 0
    vector<int>::iterator i;
    for (i = multiplicand.begin(); i != multiplicand.end(); i++) {
        // nhân x với tất cả chữ số của multiplicand
        int prod = (*i) * x + carry;
        *i = prod % 10;  // chỉ giữ chữ số cuối của tích
        carry = prod/10;  // phần còn lại cộng vào carry
    }
    while (carry) {  // khi còn carry
        multiplicand.push_back(carry%10);
        carry = carry/10;
    }
}

void factorial(int n) {
    vector<int> result;
    result.push_back(1);  // ban đầu lưu 1 làm kết quả
    for (int i=2; i<=n; i++)
        multiply(i, result);  // nhân 1*2*3*......*n
    cout << "Factorial of given number is: " << endl;
    reverse(result.begin(), result.end());  // đảo ngược thứ tự kết quả
    vector<int>::iterator it;
    for(it = result.begin(); it != result.end(); it++)
        cout << *it;
}

int main() {
    factorial(50);
}

Kết quả

Factorial of given number is: 30414093201713378043612608166064768844377641568960512000000000000