Dato il numero N di monete, il compito è trovarle probabilità di ottenere almeno K numero di teste dopo aver lanciato tutte le N monete contemporaneamente.
Esempio :
Suppose we have 3 unbiased coins and we have to
find the probability of getting at least 2 heads
so there are 23 = 8 ways to toss these
coins i.e.
HHH HHT HTH HTT THH THT TTH TTT
Out of which there are 4 set which contain at
least 2 Heads i.e.
HHH HHT HH THH
So the probability is 4/8 or 0.5
La probabilità di esattamente k successo in n prove con probabilità p di successo in ogni prova è dato da:
{displaystyle binom{n}{k}p^k(1-p)^{n-k}=^{n}textrm{c}_{k}(p)^k (1-p)^{n-k}=frac {n!(p)^k (1-p)^{n-k}}{(k)!(n-k)!}}
Quindi Probabilità (ottenere almeno 4 teste)=
{displaystyle binom{6}{4}binom{1}{2}^4binom{1}{2}^2+binom{6}{5}binom{1}{2}^5binom{1}{2}^1+binom{6}{6}binom{1}{2}^6binom{1}{2}^0}
{displaystyle =frac {1}{2^6} sinistra ( frac {6!}{4!2!}+ frac {6!}{5!1!}+ frac {6!}{6!0!}destra )}
Metodo 1 (ingenuo)
Un approccio ingenuo consiste nel memorizzare il valore di fattoriale nell'array dp[] e chiamalo direttamente ogni volta che è richiesto. Ma il problema di questo approccio è che possiamo immagazzinarlo solo fino a un certo valore, dopodiché porterà a un overflow.
Di seguito è riportata l'implementazione dell'approccio di cui sopra
C++
// Naive approach in C++ to find probability of // at least k heads #include
// JAVA Code for Probability of getting // atleast K heads in N tosses of Coins import java.io.*; class GFG { public static double fact[]; // Returns probability of getting at least k // heads in n tosses. public static double probability(int k int n) { double ans = 0; for (int i = k; i <= n; ++ i) // Probability of getting exactly i // heads out of n heads ans += fact[n] / (fact[i] * fact[n-i]); // Note: 1 << n = pow(2 n) ans = ans / (1 << n); return ans; } public static void precompute() { // Preprocess all factorial only upto 19 // as after that it will overflow fact[0] = fact[1] = 1; for (int i = 2; i < 20; ++i) fact[i] = fact[i - 1] * i; } // Driver code public static void main(String[] args) { fact = new double[100]; precompute(); // Probability of getting 2 head out // of 3 coins System.out.println(probability(2 3)); // Probability of getting 3 head out // of 6 coins System.out.println(probability(3 6)); // Probability of getting 12 head out // of 18 coins System.out.println(probability(12 18)); } } // This code is contributed by Arnav Kr. Mandal
# Naive approach in Python3 # to find probability of # at least k heads MAX=21 fact=[0]*MAX # Returns probability of # getting at least k # heads in n tosses. def probability(k n): ans = 0 for i in range(kn+1): # Probability of getting exactly i # heads out of n heads ans += fact[n] / (fact[i] * fact[n - i]) # Note: 1 << n = pow(2 n) ans = ans / (1 << n) return ans def precompute(): # Preprocess all factorial # only upto 19 # as after that it # will overflow fact[0] = 1 fact[1] = 1 for i in range(220): fact[i] = fact[i - 1] * i # Driver code if __name__=='__main__': precompute() # Probability of getting 2 # head out of 3 coins print(probability(2 3)) # Probability of getting # 3 head out of 6 coins print(probability(3 6)) # Probability of getting # 12 head out of 18 coins print(probability(12 18)) # This code is contributed by # mits
// C# Code for Probability of getting // atleast K heads in N tosses of Coins using System; class GFG { public static double []fact; // Returns probability of getting at least k // heads in n tosses. public static double probability(int k int n) { double ans = 0; for (int i = k; i <= n; ++ i) // Probability of getting exactly i // heads out of n heads ans += fact[n] / (fact[i] * fact[n - i]); // Note: 1 << n = pow(2 n) ans = ans / (1 << n); return ans; } public static void precompute() { // Preprocess all factorial only upto 19 // as after that it will overflow fact[0] = fact[1] = 1; for (int i = 2; i < 20; ++i) fact[i] = fact[i - 1] * i; } // Driver code public static void Main() { fact = new double[100]; precompute(); // Probability of getting 2 head out // of 3 coins Console.WriteLine(probability(2 3)); // Probability of getting 3 head out // of 6 coins Console.WriteLine(probability(3 6)); // Probability of getting 12 head out // of 18 coins Console.Write(probability(12 18)); } } // This code is contributed by nitin mittal.
<script> // javascript Code for Probability of getting // atleast K heads in N tosses of Coins let fact; // Returns probability of getting at least k // heads in n tosses. function probability( k n) { let ans = 0 i; for ( i = k; i <= n; ++i) // Probability of getting exactly i // heads out of n heads ans += fact[n] / (fact[i] * fact[n - i]); // Note: 1 << n = pow(2 n) ans = ans / (1 << n); return ans; } function precompute() { // Preprocess all factorial only upto 19 // as after that it will overflow fact[0] = fact[1] = 1; for ( let i = 2; i < 20; ++i) fact[i] = fact[i - 1] * i; } // Driver code fact = Array(100).fill(0); precompute(); // Probability of getting 2 head out // of 3 coins document.write(probability(2 3)+'
'); // Probability of getting 3 head out // of 6 coins document.write(probability(3 6)+'
'); // Probability of getting 12 head out // of 18 coins document.write(probability(12 18).toFixed(6)+'
'); // This code is contributed by shikhasingrajput </script>
// Naive approach in PHP to find // probability of at least k heads $MAX = 21; $fact = array_fill(0 $MAX 0); // Returns probability of getting // at least k heads in n tosses. function probability($k $n) { global $fact; $ans = 0; for ($i = $k; $i <= $n; ++$i) // Probability of getting exactly // i heads out of n heads $ans += $fact[$n] / ($fact[$i] * $fact[$n - $i]); // Note: 1 << n = pow(2 n) $ans = $ans / (1 << $n); return $ans; } function precompute() { global $fact; // Preprocess all factorial only // upto 19 as after that it // will overflow $fact[0] = $fact[1] = 1; for ($i = 2; $i < 20; ++$i) $fact[$i] = $fact[$i - 1] * $i; } // Driver code precompute(); // Probability of getting 2 // head out of 3 coins echo number_format(probability(2 3) 6) . 'n'; // Probability of getting 3 // head out of 6 coins echo number_format(probability(3 6) 6) . 'n'; // Probability of getting 12 // head out of 18 coins echo number_format(probability(12 18) 6); // This code is contributed by mits ?> Produzione
0.5 0.65625 0.118942
Complessità temporale: O(n) dove n< 20
Spazio ausiliario: SU)
Metodo 2 (Programmazione dinamica e registro)
Un altro modo è utilizzare la programmazione dinamica e il logaritmo. log() è davvero utile per memorizzare il file fattoriale di qualsiasi numero senza preoccuparsi dell'overflow. Vediamo come lo utilizziamo:
At first let see how n! can be written.
n! = n * (n-1) * (n-2) * (n-3) * ... * 3 * 2 * 1
Now take log on base 2 both the sides as:
=> log(n!) = log(n) + log(n-1) + log(n-2) + ... + log(3)
+ log(2) + log(1)
Now whenever we need to find the factorial of any number we can use
this precomputed value. For example:
Suppose if we want to find the value of nC i which can be written as:
=> nCi = n! / (i! * (n-i)! )
Taking log 2() both sides as:
=> log2 (nCi) = log2 ( n! / (i! * (n-i)! ) )
=> log2 (nCi) = log2 ( n! ) - log2(i!) - log2( (n-i)! ) `
Putting dp[num] = log 2 (num!) we get:
=> log2 (nCi) = dp[n] - dp[i] - dp[n-i]
But as we see in above relation there is an extra factor of 2 n which
tells the probability of getting i heads so
=> log2 (2n) = n.
We will subtract this n from above result to get the final answer:
=> Pi (log2 (nCi)) = dp[n] - dp[i] - dp[n-i] - n
Now: Pi (nCi) = 2 dp[n] - dp[i] - dp[n-i] - n
Tada! Now the questions boils down the summation of P i for all i in
[k n] will yield the answer which can be calculated easily without
overflow.
Di seguito sono riportati i codici per illustrarlo:
// Dynamic and Logarithm approach find probability of // at least k heads #include
// Dynamic and Logarithm approach find probability of // at least k heads import java.io.*; import java.math.*; class GFG { static int MAX = 100001; // dp[i] is going to store Log ( i !) in base 2 static double dp[] = new double[MAX]; static double probability(int k int n) { double ans = 0.0; // Initialize result // Iterate from k heads to n heads for (int i=k; i <= n; ++i) { double res = dp[n] - dp[i] - dp[n-i] - n; ans += Math.pow(2.0 res); } return ans; } static void precompute() { // Preprocess all the logarithm value on base 2 for (int i=2; i < MAX; ++i) dp[i] = (Math.log(i)/Math.log(2)) + dp[i-1]; } // Driver code public static void main(String args[]) { precompute(); // Probability of getting 2 head out of 3 coins System.out.println(probability(2 3)); // Probability of getting 3 head out of 6 coins System.out.println(probability(3 6)); // Probability of getting 500 head out of 10000 coins System.out.println(probability(500 1000)); } }
# Dynamic and Logarithm approach find probability of # at least k heads from math import log2 MAX=100001 # dp[i] is going to store Log ( i !) in base 2 dp=[0]*MAX def probability( k n): ans = 0 # Initialize result # Iterate from k heads to n heads for i in range(kn+1): res = dp[n] - dp[i] - dp[n-i] - n ans = ans + pow(2.0 res) return ans def precompute(): # Preprocess all the logarithm value on base 2 for i in range(2MAX): dp[i] = log2(i) + dp[i-1] # Driver code if __name__=='__main__': precompute() # Probability of getting 2 head out of 3 coins print(probability(2 3)) # Probability of getting 3 head out of 6 coins print(probability(3 6)) # Probability of getting 500 head out of 10000 coins print(probability(500 1000)) #this code is contributed by ash264
// Dynamic and Logarithm approach find probability of // at least k heads using System; class GFG { static int MAX = 100001; // dp[i] is going to store Log ( i !) in base 2 static double[] dp = new double[MAX]; static double probability(int k int n) { double ans = 0.0; // Initialize result // Iterate from k heads to n heads for (int i = k; i <= n; ++i) { double res = dp[n] - dp[i] - dp[n-i] - n; ans += Math.Pow(2.0 res); } return ans; } static void precompute() { // Preprocess all the logarithm value on base 2 for (int i = 2; i < MAX; ++i) dp[i] = (Math.Log(i) / Math.Log(2)) + dp[i - 1]; } // Driver code public static void Main() { precompute(); // Probability of getting 2 head out of 3 coins Console.WriteLine(probability(2 3)); // Probability of getting 3 head out of 6 coins Console.WriteLine(probability(3 6)); // Probability of getting 500 head out of 10000 coins Console.WriteLine(Math.Round(probability(500 1000)6)); } } // This code is contributed by mits
<script> // Dynamic and Logarithm approach find probability of // at least k heads let MAX = 100001; // dp[i] is going to store Log ( i !) in base 2 let dp = new Array(MAX).fill(0); function probability(k n) { var ans = 0.0; // Initialize result // Iterate from k heads to n heads for (let i = k; i <= n; ++i) { var res = dp[n] - dp[i] - dp[n - i] - n; ans += Math.pow(2.0 res); } return ans; } function precompute() { // Preprocess all the logarithm value on base 2 for (let i = 2; i < MAX; ++i) dp[i] = (Math.log(i) / Math.log(2)) + dp[i - 1]; } // Driver code precompute(); // Probability of getting 2 head out of 3 coins document.write(probability(2 3).toFixed(2)+'
'); // Probability of getting 3 head out of 6 coins document.write(probability(3 6).toFixed(5)+'
'); // Probability of getting 500 head out of 10000 coins document.write(probability(500 1000).toFixed(6)+'
'); // This code is contributed by Amit Katiyar </script>
// Dynamic and Logarithm approach // find probability of at least k heads $MAX = 100001; // dp[i] is going to store // Log ( i !) in base 2 $dp = array_fill(0 $MAX 0); function probability($k $n) { global $MAX $dp; $ans = 0; // Initialize result // Iterate from k heads to n heads for ($i = $k; $i <= $n; ++$i) { $res = $dp[$n] - $dp[$i] - $dp[$n - $i] - $n; $ans += pow(2.0 $res); } return $ans; } function precompute() { global $MAX $dp; // Preprocess all the logarithm // value on base 2 for ($i = 2; $i < $MAX; ++$i) // Note : log2() function is not in php // Some OUTPUT very in their decimal point // Basically log(valuebase) is work as // this logic : 'log10(value)/log10(2)' // equals to log2(value) $dp[$i] = log($i 2) + $dp[$i - 1]; } // Driver code precompute(); // Probability of getting 2 // head out of 3 coins echo probability(2 3).'n'; // Probability of getting 3 // head out of 6 coins echo probability(3 6).'n'; // Probability of getting 500 // head out of 10000 coins echo probability(500 1000); // This code is contributed by mits ?> Produzione
0.5 0.65625 0.512613
Complessità temporale: SU)
Spazio ausiliario: SU)
Questo approccio è vantaggioso per grandi valori di n compresi tra 1 e 10 6