資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++ 拋擲奇異硬幣
假設我們有一些硬幣。拋擲第 i 個硬幣時，正面朝上的機率為 prob[i]。如果我們恰好拋擲每一個硬幣一次，我們需要計算正面朝上硬幣數量等於目標值 target 的機率。例如，如果 prob 陣列為 [0.5,0.5,0.5,0.5,0.5]，target 為 0，則輸出為 0.03125。
為了解決這個問題，我們將遵循以下步驟：
- n := prob 陣列的大小
- 建立一個大小為 n x (target + 5) 的二維陣列
- 設定 dp[0,0] = 1 – prob[0] 和 dp[0,1] := prob[0]
- 對於 i 從 1 到 n – 1
- dp[i, 0] := (1 – prob[i]) * dp[i – 1, 0]
- 對於 j 從 1 到 min(i + 1, target)
- dp[i, j] := (1 – prob[i]) * dp[i – 1, j] + prob[i]*dp[i – 1, j - 1]
- 返回 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
更新於：2020年4月30日
591 次瀏覽
廣告