大量的阶乘

在计算机中，变量存储在内存位置。但是内存位置的大小是固定的，因此当我们尝试查找值更大的阶乘时，例如15！或20！阶乘值超出了存储范围，并返回了错误的结果。

对于大数的计算，我们必须使用数组来存储结果。在数组的每个元素中，存储结果的不同数字。但是在这里我们不能直接将某个数字与数组相乘，我们必须对结果数组的所有数字执行手动相乘过程。

输入输出

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

算法

乘（x，被乘数）

输入：数字x和大被乘数作为数组。

输出： 相乘后的结果。

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

阶乘(n)

输入： 数字n。

输出：查找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

示例

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

输出结果

Factorial of given number is:
30414093201713378043612608166064768844377641568960512000000000000