抛硬币正面期望_如果抛硬币，正面的数量多于反面的可能性

抛硬币正面期望

Problem statement:

问题陈述：

Let N be a positive odd number. There are N coins, numbered 1, 2 , ... , N. For each i (1≤i≤N), when Coin i is tossed, it comes up heads with probability pi and tails with probability 1-pi.

令N为正奇数。 有N个硬币，编号为1，2，...，N 。 对于每个i ( 1≤i≤N )，当投入硬币i时，它的出现概率为pi出现在正面 ，出现的概率为1-pi出现在尾部。

Find the probability of having more heads than tails if coins are tossed.

找到抛硬币后正面多于尾的概率。

Input:

输入：

The first line contains N, number of coins. The second line contains the probability of coming head in the coins.

第一行包含N个硬币数量。 第二行包含进入硬币的概率。

Output:

输出：

Output the probability of having more number of heads than tails if coins are tossed.

如果抛硬币，则输出正面比背面多的概率。

Example with explanation:

带有说明的示例：

Input: N=3[0.30, 0.60, 0.80]Output: 0.612The probability of having (Coin1,Coin2,Coin3) = (Head,Head,Head) is 0.3×0.6×0.8 = 0.144;The probability of having (Coin1,Coin2,Coin3) = (Tail,Head,Head) is 0.7×0.6×0.8 = 0.336;The probability of having (Coin1,Coin2,Coin3) = (Head,Tail,Head)is 0.3×0.4×0.8 = 0.096;The probability of having (Coin1,Coin2,Coin3) = (Head,Head,Tail)is 0.3×0.6×0.2 = 0.036Thus, the probability of having more heads than tails is 0.144 + 0.336 + 0.096 + 0.036 = 0.612

Solution Approach

解决方法

Dynamic Programming

动态编程

Since the problem can be solved with recursion with time complexity of O(2^n) which is not accepted as there are other better approach to solve the problem with time complexity of O(n*n);

由于可以用O(2 ^ n)的时间复杂度递归来解决问题，这是不被接受的，因为还有其他更好的方法可以解决O(n * n)的时间复杂度问题；

Let's assume prob[i][j] to be the probability of getting j heads with first i coins. To get j heads at the i^th position, there are two possibilities:

假设prob [i] [j]是第一个i个硬币获得j个头的概率。 为了使j个头位于第i ^个位置，有两种可能性：

If the number of heads till (i - 1) coins is equal to j then a tail comes at i^th. If the number of heads till (i - 1) coins is equal to (j - 1) then a head comes at i^th position.

如果直到(i-1)个硬币的正面数等于j，则^第 i ^个背面为^尾数 。 如果直到(i-1)个硬币的正面数等于(j-1)，则正面在^第 i ^个位置。

The probability of occurring jth head at ith coin toss depends on the number of heads in (i-1)^th coins, if (i-1) coin have (j-1) head then jth coin occurs at i^th coin(p[i]), and if (i-1) coins have already j coins then at jth toss tails come(1-p[i]).

第i个硬币抛掷第j个硬币的概率取决于第(i-1) ^个硬币的硬币的数目，如果(i-1)个硬币具有(j-1) 个硬币的硬币，则第j个硬币出现在^第 i ^个硬币( p [ i] )，如果(i-1)个硬币已经有j个硬币，则第j个抛尾出现( 1-p [i] )。

Pseudo Code:

伪代码：

// p[] is the probability array, // n is the size of array. solve(p[],n):// declare prob[n+1][n+1] array of having required head.prob[n+1][n+1] // no head out of 1 coinsprob[1][0]=1-p[0] // one head out of one coinsprob[1][1]=p[0] for(i=2;i<=n;i++)// probability of having no heads.prob[i][0]=prob[i-1][0]*(1-p[i]) for(i=2;i<=n;i++)for(j=1;j<=i;j++)prob[i][j]=prob[i-1][j-1]*p[i-1]+prob[i-1][j]*(1-p[i-1])// probability of having jth head can take // place in (i-1) coins or at (i)th coin.sum=0for(i=n/2+n%2;i<=n;i++)//probability of heads>tails.sum+=prob[n][i] return sum

Time complexity: In worst case O(n*n)

时间复杂度 ：在最坏的情况下O(n * n)

C++ Implementation:

C ++实现：

#include <bits/stdc++.h> using namespace std;typedef double ll;int main() {cout << "Enter number of test cases: ";int t;cin >> t;while (t--) {cout << "Enter the number of coins: ";int n;cin >> n;ll p[n];cout << "Enter the probabilities of head: ";for (int i = 0; i < n; i++)cin >> p[i];ll prob[n + 1][n + 1];// probability of one heads with one coinsprob[1][1] = p[0];// probability of no heads with one coinsprob[1][0] = 1 - p[0];for (int i = 2; i <= n; i++)// probability of no heads with i coins.prob[i][0] = prob[i - 1][0] * (1 - p[i - 1]);for (int i = 2; i <= n; i++) {for (int j = 1; j <= i; j++)// probability of head at ith coin it it occurs at(i-1)// then just multiply with tail probability otherwise// multiply with head probability.prob[i][j] = prob[i - 1][j - 1] * p[i - 1] + prob[i - 1][j] * (1 - p[i - 1]);}ll sum = 0;for (int i = n / 2 + n % 2; i <= n; i++)// take those probability which have more heads than tails.sum += prob[n][i];cout << "The probability of heads more than the tails is: ";cout << setprecision(10) << sum << "\n";}return 0; }

Output

输出量

Enter number of test cases: 3 Enter the number of coins: 5 Enter the probabilities of head: 0.42 0.01 0.42 0.99 0.42 The probability of heads more than the tails is: 0.3821815872 Enter the number of coins: 3 Enter the probabilities of head: 0.30 0.60 0.80 The probability of heads more than the tails is: 0.612 Enter the number of coins: 1 Enter the probabilities of head: 0.50 The probability of heads more than the tails is: 0.5

翻译自: https://www.includehelp.com/icp/probability-of-getting-more-number-of-heads-than-tails-if-coins-are-tossed.aspx

抛硬币正面期望

总结

以上是生活随笔为你收集整理的抛硬币正面期望_如果抛硬币，正面的数量多于反面的可能性的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。