抛奇怪硬币在C ++中

假设我们有一些硬币。第i个硬币具有概率概率扔当磁头面对的[i]中。我们必须表明,面临头硬币的数目等于目标,如果你抛硬币每一次准确的概率。因此,如果概率数组像[0.5,0.5,0.5,0.5,0.5]并且目标为0,那么输出将为0.03125。

为了解决这个问题,我们将遵循以下步骤-

  • n:=概率数组的大小

  • 创建大小为nx的一个2D阵列(靶+ 5)

  • 组DP [0,0] = 1  - 概率[0]和DP [0,1]:=概率[0]

  • 当我在1到n – 1的范围内时

    • dp [i,j]:=(1-prob [i])* dp [i – 1,j] + prob [i] * dp [i – 1,j-1]

    • dp [i,0]:=(1 –概率[i])* dp [i – 1,0]

    • 对于范围在1到i + 1最小值之间的j并目标

    • 返回dp [n – 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