Giai thừa của một số lớn

Trong máy tính, các biến được lưu trữ trong các vị trí bộ nhớ. Nhưng kích thước của vị trí bộ nhớ là cố định, vì vậy khi chúng ta cố gắng tìm giai thừa của một số giá trị lớn hơ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 các số lớn, chúng ta phải sử dụng một mảng để lưu trữ kết quả. Trong mỗi phần tử của mảng, đang lưu trữ các chữ số khác nhau của kết quả. Nhưng ở đây chúng ta không thể nhân trực tiếp một số với mảng, chúng ta phải thực hiện quy 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

Input:
A big number: 50
Output:
Factorial of given number is:
30414093201713378043612608166064768844377641568960512000000000000

Thuật toán

nhân (x, bội và)

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

Đầu ra: Kết quả sau khi 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
      insert (carry mod 10) at the end of multiplicand array
      carry := carry/10
   done
End

giai thừa (n)

Đầu vào: Số n.

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

Begin
   define result array.
   insert 1 in the result

   for i := 2 to n, do
      multiply(i, result)
   done

   reverse the result
   return result
End

Ví dụ

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

void multiply(int x, vector<int>&multiplicand) {    //multiply multiplicand with x
   int carry = 0;     // Initialize carry to 0
   vector<int>::iterator i;

   for (i=multiplicand.begin(); i!=multiplicand.end(); i++) {   //multiply x with all digit of multiplicand
      int prod = (*i) * x + carry;
      *i = prod % 10;       //put only the last digit of product
      carry  = prod/10;    //add remaining part with carry  
   }

   while (carry) {    //when carry is present
      multiplicand.push_back(carry%10);
      carry = carry/10;
   }
}

void factorial(int n) {
   vector<int> result;
   result.push_back(1);    //at first store 1 as result

   for (int i=2; i<=n; i++)
      multiply(i, result);   //multiply numbers 1*2*3*......*n

   cout << "Factorial of given number is: "<<endl;

   reverse(result.begin(), result.end());

   vector<int>::iterator it;    //reverse the order of result

   for(it = result.begin(); it != result.end(); it++)
      cout << *it;
}

int main() {
   factorial(50);
}

Đầu ra

Factorial of given number is:
30414093201713378043612608166064768844377641568960512000000000000