Probabilidad de obtener más cara que cruz cuando se lanzan N monedas sesgadas

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,442

Entrada: 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:  

  1. Si el número de caras hasta (i – 1) monedas es igual a j , entonces sale cruz en i th .
  2. 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>
Producción: 

0.442

 

Publicación traducida automáticamente

Artículo escrito por CrazyPro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *