কম্বিনেশন
(ডায়নামিক
প্রোগ্রামিং + রিকার্শন)
তোমাকে যদি 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
0 comments:
Post a Comment