Donat el nombre N de monedes, la tasca és trobar probabilitat d'obtenir almenys K nombre de caps després de llançar totes les N monedes simultàniament.
Exemple:
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 probabilitat d'èxit exactament k en n proves amb probabilitat p d'èxit en qualsevol assaig ve donat per:
{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)!}}
Així que probabilitat (aconseguir almenys 4 caps)=
{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}
{estil de visualització =frac {1}{2^6} a l'esquerra (frac {6!}{4!2!}+frac {6!}{5!1!}+frac {6!}{6!0!}dreta)}
Mètode 1 (ingenu)
Un enfocament ingenu és emmagatzemar el valor de factorial a la matriu dp[] i truca'l directament sempre que sigui necessari. Però el problema d'aquest enfocament és que només podem emmagatzemar-lo fins a un determinat valor després d'això provocarà un desbordament.
A continuació es mostra la implementació de l'enfocament anterior
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 ?> Sortida
0.5 0.65625 0.118942
Complexitat temporal: O(n) on n< 20
Espai auxiliar: O(n)
Mètode 2 (programació dinàmica i registre)
Una altra manera és utilitzar la programació dinàmica i el logaritme. log() és realment útil per emmagatzemar el fitxer factorial de qualsevol nombre sense preocupar-se del desbordament. Vegem com el fem servir:
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.
A continuació es mostren els codis per il·lustrar-ho:
// 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 ?> Sortida
0.5 0.65625 0.512613
Complexitat temporal: O(n)
Espai auxiliar: O(n)
Aquest enfocament és beneficiós per a un gran valor de n que oscil·la entre 1 i 10 6