FCTRL2 - Small factorials SPOJ Problem Solution & Full Logic

http://www.spoj.com/problems/FCTRL2/

ফ্যাক্টোরিয়াল খুবই মজার ও পরিচিত একটা বিষয় , কিন্তু , যখনই - অনেক বড়ো একটি সংখ্যার ফ্যাক্টোরিয়াল বের করতে বলে , তখন বেশ ঝামেলায় পড়তে হয় । যেমন , যদি ৫০ এর ফ্যাক্টরিয়াল বের করো তাহলে হবে , 30414093201713378043612608166064768844377641568960512000000000000

এত্ত বড়ো সংখ্যা তো , int টাইপ variable স্টোর করতে পারবে না , তাই একটু কষ্ট করে এমন একটা ব্যবস্থা করতে হবে , যেনো , এই সংখ্যা'র ডিজিটগুলোকে একটা int টাইপ অ্যারে'তে ঢুকাতে হবে ।
তারপর , সেটাকে প্রিন্ট করলেই হয়ে যাবে ।

এখন প্রথমে , কোড দেখো - তারপর ,কিভাবে কাজ করছে ? ? সেটা ব্যাখ্যা করলে , মনে হয় একটু ইজি হবে -----

#include <bits/stdc++.h>

using namespace std;

#define max 500

int multiply(int x,int res[],int res_size);

void factorial(int n)

{
    int res[max];

    res[0]=1;

    int res_size=1;

    for(int x=2;x<=n;x++)
    {
        res_size=multiply(x,res,res_size);
    }

    for(int i=res_size-1;i>=0;i--)
    {
        cout<<res[i];
    }
    cout<<endl;
}




int multiply(int x,int res[],int res_size)
{
    int carry=0;

    for(int i=0;i<res_size;i++)
    {
        int prod=res[i]*x+carry;
        res[i]=prod%10;
        carry=prod/10;
    }

    while(carry)
    {
        res[res_size]=carry%10;
        carry=carry/10;
        res_size++;
    }

    return res_size;
}

int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>n;
        factorial(n);
    }
    return 0;
}






কোড দেখে ভয় পাবার কিছুই নেই , ধরো , ৫ এর ফ্যাক্টোরিয়াল বের করতে হবে । তাহলে ,কিভাবে কাজ করবে ? চলো , দেখে নেয়া যাক ।

প্রথমে , factorial() নামক  void function কে call করা হবে , সুতরাং-----আমরা সেই   factorial()  ফাংশন-এ চলে যাবো ---------------

প্রথমেই , একটি res  নামে একটি  অ্যারে  decalre করলাম ,যার সাইজ নির্ধারণ করলাম ৫০০ এর মতো,সর্বাধিক ৫০০ ডিজিট অবদি , অ্যারেটি ধারণ করতে পারবে ।

প্রথমে ,  res[0]=1 মানে , প্রথম ভ্যালু ১ -এ ইনিশিয়ালাইজ করলাম -সুতরাং  int res_size=1;যেহেতু , অ্যারেতে কেবল একটি'র মান বসানো আছে । যেহেতু , ৫ এর ফ্যাক্টোরিয়াল হবে , ৫ * ৪ * ৩* ২*১ ।
১ গুণ করলেই কি ? আর না করলেই কি ? কিছুই না , তাই ১ কে ইগনোর করে

      for(int x=2;x<=n;x++)
      {
          res_size=multiply(x,res,res_size);
       }

এই লুপটা ঘুরালাম , যেটা   ২*৩*৪*৫  এর মান  generate  করবে । এখন , গুণ এর কাজ করার জন্য ,

  int multiply(int x,int res[],int res_size)

নামক একটি ফাংশন ইউজ করেছি । এখন , প্রথমে যখন লুপ ঘুরবে , x এর মান ২ যেটা  multiply
ফাংশনে ঢূকবে , এবং

for(int i=0;i<res_size;i++)
    {
        int prod=res[i]*x+carry;
        res[i]=prod%10;
        carry=prod/10;
    }

লুপটির দ্বারা , গুণ করবে আর যদি কখনো  carry থাকে , মানে কোনো কিছুর গুণফল যদি - ২ ডিজিট বিশিষ্ট হয় - তাহলে প্রথম ডিজিট'টি হবে carry , মানে - যেমন ৬*৭= ৪২ , এখানে ক্যারি হলো - ৪ ।

while(carry)
    {
        res[res_size]=carry%10;
        carry=carry/10;
        res_size++;
    }

 carry কে , ইমপ্লিমেন্ট করার জন্য - এই লুপ ইউজ করলাম । এখন শুধু , দেখে নেই , ৫ এর ফ্যাক্টরিয়াল এ কোড কি করছে ??

res[0]=1;

res[0]=2; ( 2 দিয়ে ১গুণ করে)

res[0]=6; ( ৩ দিয়ে ২ গুণ করে)

res[0]=4, res[1]=2; ( ৬ কে ৪ দিয়ে গুণ করে)

res[0]=0 , res[1]=2, res[2]=1; ( অনুরুপভাবে)


for(int i=res_size-1;i>=0;i--)
    {
        cout<<res[i];
    }

লুপটি ইউজ করে , প্রিন্ট করলাম তাহলে , উত্তর হবে -    120