একজন ব্যক্তি "A" শুরুর পজিশন X=0 থেকে চলতে শুরু করে। টাস্ক হলো সে ঠিক X=num-এ পৌঁছাবে কিনা তার প্রোবাবিলিটি বের করা, যদি সে প্রতিবার ২ বা ৩ ধাপ চলে। ২ ধাপ চলার প্রোবাবিলিটি = P, ৩ ধাপ চলার প্রোবাবিলিটি = 1-P।
ইনপুট − num=5, p=0.2
আউটপুট − 0.32
ব্যাখ্যা − ৫-এ পৌঁছানোর ২ পথ:
- ২+৩: প্রোবাবিলিটি = ০.২ × ০.৮ = ০.১৬
- ৩+২: প্রোবাবিলিটি = ০.৮ × ০.২ = ০.১৬
ইনপুট − num=2, p=0.1
আউটপুট − 0.1
প্রোগ্রামে ব্যবহৃত পদ্ধতি (Dynamic Programming)
probab[]অ্যারে ডিক্লেয়ার করুন সাইজnum+1।probab[0]=1,probab[1]=0,probab[2]=p,probab[3]=1-p
i=4থেকেnumপর্যন্ত লুপ:probab[i] = p*probab[i-2] + (1-p)*probab[i-3]
probab[num]রিটার্ন করুন।
অ্যালগরিদম
Start
function probab(num, p)
probab[0]=1, probab[1]=0, probab[2]=p, probab[3]=1-p
for i=4 to num
probab[i] = p*probab[i-2] + (1-p)*probab[i-3]
return probab[num]
Stop
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
float probab(int num, float p) {
vector dp(num + 1);
dp[0] = 1;
dp[1] = 0;
dp[2] = p;
dp[3] = 1 - p;
for (int i = 4; i <= num; ++i)
dp[i] = p * dp[i-2] + (1-p) * dp[i-3];
return dp[num];
}
int main() {
int num = 2;
float p = 0.1;
cout << "probability is: " << probab(num, p);
return 0;
} আউটপুট
probability is: 0.1
