แฟกทอเรียลของจำนวนมาก

ในคอมพิวเตอร์ ตัวแปรจะถูกเก็บไว้ในตำแหน่งหน่วยความจำ แต่ขนาดของตำแหน่งหน่วยความจำคงที่ ดังนั้นเมื่อเราพยายามหาแฟคทอเรียลของค่าที่มากกว่าเช่น 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