सी ++ में अजीब सिक्के टॉस करें

मान लीजिए हमारे पास कुछ सिक्के हैं। i-वें सिक्के में उछाले जाने पर चित आने की प्रायिकता [i] होती है। यदि आप प्रत्येक सिक्के को ठीक एक बार उछालते हैं, तो हमें यह प्रायिकता दिखानी होगी कि शीर्षों का सामना करने वाले सिक्कों की संख्या लक्ष्य के बराबर होगी। तो अगर प्रोब ऐरे [0.5,0.5,0.5,0.5,0.5] जैसा है और टारगेट 0 है, तो आउटपुट 0.03125 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• n :=प्रोब ऐरे का आकार
• n x आकार का एक 2d सरणी बनाएं (लक्ष्य + 5)
• सेट डीपी[0,0] =1 - प्रोब[0] और डीपी[0,1] :=प्रोब[0]
• मैं के लिए 1 से n - 1 की सीमा में
  • dp[i, 0] :=(1 – prob[i]) * dp[i – 1, 0]
  • जे के लिए श्रेणी 1 से न्यूनतम i + 1 और लक्ष्य
    • dp[i, j] :=(1 – prob[i]) * dp[i – 1, j] + prob[i]*dp[i – 1, j-1]
• रिटर्न डीपी[एन -1, लक्ष्य]

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   double probabilityOfHeads(vector<double>& prob, int target) {
      int n = prob.size();
      vector < vector <double> > dp(n, vector <double>(target+5));
      dp[0][0] = 1- prob[0];
      dp[0][1] = prob[0];
      for(int i =1;i<n;i++){
         dp[i][0] = (1-prob[i])*dp[i-1][0];
         for(int j =1;j<=min(i+1,target);j++){
            dp[i][j] = (1-prob[i])*dp[i-1][j] + prob[i]*dp[i-1][j-1];
         }
      }
      return dp[n-1][target];
   }
};
main(){
   vector<double> v = {0.5,0.5,0.5,0.5,0.5};
   Solution ob;
   cout << (ob.probabilityOfHeads(v, 0));
}

इनपुट

[0.5,0.5,0.5,0.5,0.5]
0

आउटपुट

0.03125