多数の階乗

コンピューターでは、変数はメモリ位置に格納されます。ただし、メモリ位置のサイズは固定されているため、15などのより大きな値の階乗を見つけようとすると！または20！階乗の値がメモリ範囲を超え、間違った結果を返します。

大きな数を計算するには、配列を使用して結果を格納する必要があります。配列の各要素に、結果の異なる桁を格納しています。ただし、ここでは、ある数値を配列で直接乗算することはできません。結果の配列のすべての桁に対して手動の乗算プロセスを実行する必要があります。

入力と出力

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

アルゴリズム

multiply（x、multiplicand）

入力： 数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