Dada una array p[] de longitud impar N donde p[i] denota la probabilidad de obtener cara en la i -ésima moneda. Como las monedas están sesgadas, la probabilidad de obtener cara no siempre es igual a 0,5 . La tarea es encontrar la probabilidad de obtener caras más veces que cruces.
Ejemplos:
Entrada: p[] = {0.3, 0.4, 0.7}
Salida: 0.442
Probabilidad de cruz = (1 – Probabilidad de cara)
Para cara mayor que cruz, hay 4 posibilidades:
P({cara, cara, cruz}) = 0,3 x 0,4 x (1 – 0,7) = 0,036
P({cola, cara, cabeza}) = (1 – 0,3) x 0,4 x 0,7 = 0,196
P({cara, cola, cara}) = 0,3 x (1 – 0,4) x 0,7= 0,126
P({cabeza, cabeza, cabeza}) = 0,3 x 0,4 x 0,7 = 0,084
Sumando las probabilidades anteriores
0,036 + 0,196 + 0,126 + 0,084 = 0,442Entrada: p[] = {0,3, 0,5, 0,2, 0,6, 0,9}
Salida: 0,495
Enfoque ingenuo: el enfoque ingenuo sería crear todas las 2 n posibilidades de cara y cruz. Luego calcula las probabilidades para diferentes permutaciones y las suma cuando el número de caras es mayor que el número de cruces, como en la explicación del ejemplo. Esto daría TLE cuando n es grande.
Enfoque eficiente: La idea es usar programación dinámica . Supongamos que dp[i][j] es la probabilidad de obtener j caras con las primeras i monedas. Para obtener j caras en la i -ésima posición, hay dos posibilidades:
- Si el número de caras hasta (i – 1) monedas es igual a j , entonces sale cruz en i th .
- Si el número de caras hasta (i – 1) monedas es igual a (j – 1) , entonces aparece una cara en la i -ésima posición
Por lo tanto, se puede dividir en sus subproblemas de la siguiente manera:
dp[i][j] = dp[i – 1][j] * (1 – p[i]) + dp[i – 1][j – 1] * p[i]
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the probability when
// number of heads is greater than the number of tails
double Probability(double p[], int n)
{
// Declaring the DP table
double dp[n + 1][n + 1];
memset(dp, 0.0, sizeof(dp));
// Base case
dp[0][0] = 1.0;
// Iterating for every coin
for (int i = 1; i <= n; i += 1) {
// j represents the numbers of heads
for (int j = 0; j <= i; j += 1) {
// If number of heads is equal to zero
// there is only one possibility
if (j == 0)
dp[i][j] = dp[i - 1][j]
* (1.0 - p[i]);
else
dp[i][j] = dp[i - 1][j]
* (1.0 - p[i])
+ dp[i - 1][j - 1] * p[i];
}
}
double ans = 0.0;
// When the number of heads is greater than (n+1)/2
// it means that heads are greater than tails as
// no of tails + no of heads is equal to n for
// any permutation of heads and tails
for (int i = (n + 1) / 2; i <= n; i += 1)
ans += dp[n][i];
return ans;
}
// Driver Code
int main()
{
// 1 based indexing
double p[] = { 0.0, 0.3, 0.4, 0.7 };
// Number of coins
int n = sizeof(p) / sizeof(p[0]) - 1;
// Function call
cout << Probability(p, n);
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to return the probability when
// number of heads is greater than the number of tails
static double Probability(double p[], int n)
{
// Declaring the DP table
double [][]dp = new double[n + 1][n + 1];
// Base case
dp[0][0] = 1.0;
// Iterating for every coin
for (int i = 1; i <= n; i += 1)
{
// j represents the numbers of heads
for (int j = 0; j <= i; j += 1)
{
// If number of heads is equal to zero
// there is only one possibility
if (j == 0)
dp[i][j] = dp[i - 1][j]
* (1.0 - p[i]);
else
dp[i][j] = dp[i - 1][j]
* (1.0 - p[i])
+ dp[i - 1][j - 1] * p[i];
}
}
double ans = 0.0;
// When the number of heads is greater than (n+1)/2
// it means that heads are greater than tails as
// no of tails + no of heads is equal to n for
// any permutation of heads and tails
for (int i = (n + 1) / 2; i <= n; i += 1)
ans += dp[n][i];
return ans;
}
// Driver Code
public static void main(String[] args)
{
// 1 based indexing
double p[] = { 0.0, 0.3, 0.4, 0.7 };
// Number of coins
int n = p.length - 1;
// Function call
System.out.println(Probability(p, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach import numpy as np # Function to return the probability when # number of heads is greater than # the number of tails def Probability(p, n) : # Declaring the DP table dp = np.zeros((n + 1, n + 1)); for i in range(n + 1) : for j in range(n + 1) : dp[i][j] = 0.0 # Base case dp[0][0] = 1.0; # Iterating for every coin for i in range(1, n + 1) : # j represents the numbers of heads for j in range(i + 1) : # If number of heads is equal to zero # there is only one possibility if (j == 0) : dp[i][j] = dp[i - 1][j] * (1.0 - p[i]); else : dp[i][j] = (dp[i - 1][j] * (1.0 - p[i]) + dp[i - 1][j - 1] * p[i]); ans = 0.0; # When the number of heads is greater than (n+1)/2 # it means that heads are greater than tails as # no of tails + no of heads is equal to n for # any permutation of heads and tails for i in range((n + 1)// 2, n + 1) : ans += dp[n][i]; return ans; # Driver Code if __name__ == "__main__" : # 1 based indexing p = [ 0.0, 0.3, 0.4, 0.7 ]; # Number of coins n = len(p) - 1; # Function call print(Probability(p, n)); # This code is contributed by AnkitRai01
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to return the probability when
// number of heads is greater than the number of tails
static double Probability(double []p, int n)
{
// Declaring the DP table
double [,]dp = new double[n + 1, n + 1];
// Base case
dp[0, 0] = 1.0;
// Iterating for every coin
for (int i = 1; i <= n; i += 1)
{
// j represents the numbers of heads
for (int j = 0; j <= i; j += 1)
{
// If number of heads is equal to zero
// there is only one possibility
if (j == 0)
dp[i,j] = dp[i - 1,j]
* (1.0 - p[i]);
else
dp[i,j] = dp[i - 1,j]
* (1.0 - p[i])
+ dp[i - 1,j - 1] * p[i];
}
}
double ans = 0.0;
// When the number of heads is greater than (n+1)/2
// it means that heads are greater than tails as
// no of tails + no of heads is equal to n for
// any permutation of heads and tails
for (int i = (n + 1) / 2; i <= n; i += 1)
ans += dp[n,i];
return ans;
}
// Driver Code
static public void Main ()
{
// 1 based indexing
double []p = { 0.0, 0.3, 0.4, 0.7 };
// Number of coins
int n = p.Length - 1;
// Function call
Console.Write(Probability(p, n));
}
}
// This code is contributed by ajit.
Javascript
<script>
// Javascript implementation of the above approach
// Function to return the probability when
// number of heads is greater than the number of tails
function Probability(p , n)
{
// Declaring the DP table
var dp = Array(n + 1).fill(0).map(
x => Array(n + 1).fill(0));
// Base case
dp[0][0] = 1.0;
// Iterating for every coin
for(var i = 1; i <= n; i += 1)
{
// j represents the numbers of heads
for(var j = 0; j <= i; j += 1)
{
// If number of heads is equal to zero
// there is only one possibility
if (j == 0)
dp[i][j] = dp[i - 1][j] *
(1.0 - p[i]);
else
dp[i][j] = dp[i - 1][j] * (1.0 - p[i]) +
dp[i - 1][j - 1] * p[i];
}
}
var ans = 0.0;
// When the number of heads is greater than (n+1)/2
// it means that heads are greater than tails as
// no of tails + no of heads is equal to n for
// any permutation of heads and tails
for(var i = parseInt((n + 1) / 2); i <= n; i += 1)
ans += dp[n][i];
return ans;
}
// Driver Code
// 1 based indexing
var p = [ 0.0, 0.3, 0.4, 0.7 ];
// Number of coins
var n = p.length - 1;
// Function call
document.write(Probability(p, n));
// This code is contributed by Amit Katiyar
</script>
0.442