큰 수의 계승

컴퓨터에서 변수는 메모리 위치에 저장됩니다. 그러나 메모리 위치의 크기는 고정되어 있으므로 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