ডায়নামিক প্রোগ্রামিং এবং রিকার্শন দিয়ে NCR কম্বিনেশন


                                      

                                                কম্বিনেশন
                                    (ডায়নামিক প্রোগ্রামিং + রিকার্শন)

তোমাকে যদি N এবং R দেয়া হয় এবং এখানে থেকে NCR বের করতে বলা হয় তাহলে সাধারনত আমরা সবাই NCR এর সূত্র অনুযায়ী বের করব। কিন্তু যখন N এর মান ১৫ এর মত হয় তখন এই পদ্ধতি আর কাজ করবে না কারন তখন Long Long এও এত বড় মান আর ধরে না। এক্ষেত্রে ডায়নামিক প্রোগ্রামিং + রিকার্শন এর কন্সেপ্ট কাজে দিবে। প্রথমে আমি প্রোগ্রাম এর ফাংশনটি লিখব । তারপর ধাপে ধাপে বর্ননা করব।

long long int ncr(int n,int r)

{

    if(r==1)

    {

        return n;

    }

    if(n==r)

    {

        return 1;

    }

    if(r==0)

    {

        return 1;

    }

    if(dp[n][r]!=-1)

    {

        return dp[n][r];

    }

    else

    {

        dp[n][r]=ncr(n-1,r)+ncr(n-1,r-1);

        return dp[n][r];

    }

}

NCR ফাংশনে প্রথমে বেস কেস দেয়া আছে কিছু। যেমনঃ R এর মান ১ হলে কিন্তু NCR এর ভ্যালু সব সময় N হয়। N=R হলে ১ হয় এবং R=0 হলেও ১ হয়।
এরপর আসল খেলা শুরু। dp[n][r]  এর সব ভ্যালু প্রথমে -১ করে দিতে হবে ।  তারপর আমরা রিকার্শন এর মাধ্যমে এর ভ্যালুগুলো বের করব এবং dp[n][r] এ সেভ করে রাখব । ধরা যাক N=6 এবং R=2 । তাহলে উপরের প্রোগ্রাম অনুযায়ী else ব্লক এ যাবে।

                 dp[6][2]= ncr(6-1,2)                          +                             ncr(6-1,2-1)
                               = ncr(5,2)                               +                              ncr(5,1)

এখন ncr(5,2)  আবার একইভাবে একই সূত্রে পরবে এবং else ব্লকে যাবে। কিন্তু R=1 এর কারনে +  এর পরের ncr(5,1) রিটার্ন করবে N . এভাবে প্রতি বার ফাংশনে যাবে এবং বেস কেস এর সাথে মিলে গেলে রিটার্ন করবে। নিচে ধাপে ধাপে 6C2 এর ভ্যালু কিভাবে বের করা হয় দেখানো হল।

                   dp[6][2] = ncr(5,2)                     +    ncr(5,1)
                     = ncr(5-1,2)+ncr(5-1,2-1)                  +   5
                                  =ncr(4,2)+ncr(4,1) +5
                                  =ncr(4,2)+ 4+5
                                  =ncr(4-1,2)+ncr(4-1,2-1)+4+5
                                  =ncr(3,2)+ncr(3,1)+4+5
                                  =ncr(3,2)+3+4+5
                                  =ncr(3-1,2)+ncr(3-1,2-1)+3+4+5
                                  = ncr(2,2)+ncr(2,1)+3+4+5        [n=r]
                                  = 1+2+3+4+5
                                  =15

কিছু প্রব্লেম সল্ভ করলে আরো বেশি ক্লিয়ার হবে। পুরো কোড নিচের লিঙ্ক গুলো তে দেয়া আছে।
রিলেটেড প্রব্লেম সলুশন : UVA 369 Combination , Devskill 61 Divide and Grid
Share on Google Plus

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment