C++で奇妙なコインを投げる

コインがあるとします。 i番目のコインは投げられたときに頭に面する確率確率を持っています。すべてのコインを1回だけ投げた場合、頭に面しているコインの数が目標と等しくなる確率を示す必要があります。したがって、prob配列が[0.5,0.5,0.5,0.5,0.5]のようで、targetが0の場合、出力は0.03125になります。

これを解決するには、次の手順に従います-

• n：=確率配列のサイズ
• サイズnx（ターゲット+ 5）の2次元配列を1つ作成します
• set dp [0,0] =1 – prob[0]およびdp[0,1]：=prob [0]
• 1からn–1の範囲のiの場合
  • dp [i、0]：=（1 – prob [i]）* dp [i – 1、0]
  • 範囲1から最小i+1およびターゲットのjの場合
    • dp [i、j]：=（1 – prob [i]）* dp [i – 1、j] + prob [i] * dp [i – 1、j-1]
• return dp [n – 1、target]

理解を深めるために、次の実装を見てみましょう-

例

#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