Dada una moneda justa que se lanza N veces, la tarea es determinar la probabilidad de que no ocurran dos caras consecutivamente.
Ejemplos:
Entrada: N = 2
Salida: 0,75
Explicación:
Cuando la moneda se lanza 2 veces, los resultados posibles son {TH, HT, TT, HH}.
Ya que en 3 de 4 resultados, las caras no ocurren juntas.
Por lo tanto, la probabilidad requerida es (3/4) o 0.75Entrada: N = 3
Salida: 0.62
Explicación:
Cuando la moneda se lanza 3 veces, los resultados posibles son {TTT, HTT, THT, TTH, HHT, HTH, THH, HHH}.
Dado que en 5 de 8 resultados, las caras no aparecen juntas.
Por lo tanto, la probabilidad requerida es (5/8) o 0.62
Enfoque: Debe hacerse la siguiente observación sobre el número de resultados favorables.
- Cuando N = 1: Los resultados posibles son {T, H}. Hay dos resultados favorables de los dos.
- Cuando N = 2: Los resultados posibles son {TH, HT, TT, HH}. Hay tres resultados favorables de cuatro.
- Cuando N = 3: Del mismo modo, los resultados posibles son {TTT, HTT, THT, TTH, HHT, HTH, THH, HHH}. Hay cinco resultados favorables de ocho.
- Cuando N = 4: Del mismo modo, los resultados posibles son {TTTT, TTTH, TTHT, THTT, HTTT, TTHH, THTH, HTHT, HHTT, THHT, HTTH, THHH, HTHH, HHTH, HHHT, HHHH}. Hay ocho resultados favorables de dieciséis.
Claramente, el número de resultados favorables sigue una serie de Fibonacci donde Fn(1) = 2, Fn(2) = 3 y así sucesivamente. Por lo tanto, la idea es implementar la secuencia de Fibonacci para encontrar el número de casos favorables. Claramente, el número total de casos es 2 N .
Para calcular la probabilidad se utiliza la siguiente fórmula:
P = casos favorables / Número total de casos
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// probability of not getting two
// consecutive heads together when
// N coins are tossed
#include <bits/stdc++.h>
using namespace std;
float round(float var,int digit)
{
float value = (int)(var *
pow(10, digit) + .5);
return (float)value /
pow(10, digit);
}
// Function to compute the N-th
// Fibonacci number in the
// sequence where a = 2
// and b = 3
int probability(int N)
{
// The first two numbers in
// the sequence are initialized
int a = 2;
int b = 3;
// Base cases
if (N == 1)
{
return a;
}
else if(N == 2)
{
return b;
}
else
{
// Loop to compute the fibonacci
// sequence based on the first
// two initialized numbers
for(int i = 3; i <= N; i++)
{
int c = a + b;
a = b;
b = c;
}
return b;
}
}
// Function to find the probability
// of not getting two consecutive
// heads when N coins are tossed
float operations(int N)
{
// Computing the number of
// favourable cases
int x = probability(N);
// Computing the number of
// all possible outcomes for
// N tosses
int y = pow(2, N);
return round((float)x /
(float)y, 2);
}
// Driver code
int main()
{
int N = 10;
cout << (operations(N));
}
// Thus code is contributed by Rutvik_56
Java
// Java implementation to find the
// probability of not getting two
// consecutive heads together when
// N coins are tossed
class GFG{
public static float round(float var, int digit)
{
float value = (int)(var *
Math.pow(10, digit) + .5);
return (float)value /
(float)Math.pow(10, digit);
}
// Function to compute the N-th
// Fibonacci number in the
// sequence where a = 2
// and b = 3
public static int probability(int N)
{
// The first two numbers in
// the sequence are initialized
int a = 2;
int b = 3;
// Base cases
if (N == 1)
{
return a;
}
else if (N == 2)
{
return b;
}
else
{
// Loop to compute the fibonacci
// sequence based on the first
// two initialized numbers
for(int i = 3; i <= N; i++)
{
int c = a + b;
a = b;
b = c;
}
return b;
}
}
// Function to find the probability
// of not getting two consecutive
// heads when N coins are tossed
public static float operations(int N)
{
// Computing the number of
// favourable cases
int x = probability(N);
// Computing the number of
// all possible outcomes for
// N tosses
int y = (int)Math.pow(2, N);
return round((float)x /
(float)y, 2);
}
// Driver code
public static void main(String[] args)
{
int N = 10;
System.out.println((operations(N)));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation to find the # probability of not getting two # consecutive heads together when # N coins are tossed import math # Function to compute the N-th # Fibonacci number in the # sequence where a = 2 # and b = 3 def probability(N): # The first two numbers in # the sequence are initialized a = 2 b = 3 # Base cases if N == 1: return a elif N == 2: return b else: # Loop to compute the fibonacci # sequence based on the first # two initialized numbers for i in range(3, N + 1): c = a + b a = b b = c return b # Function to find the probability # of not getting two consecutive # heads when N coins are tossed def operations(N): # Computing the number of # favourable cases x = probability (N) # Computing the number of # all possible outcomes for # N tosses y = math.pow(2, N) return round(x / y, 2) # Driver code if __name__ == '__main__': N = 10 print(operations(N))
C#
// C# implementation to find the
// probability of not getting two
// consecutive heads together when
// N coins are tossed
using System;
class GFG{
public static float round(float var, int digit)
{
float value = (int)(var *
Math.Pow(10, digit) + .5);
return (float)value /
(float)Math.Pow(10, digit);
}
// Function to compute the N-th
// Fibonacci number in the
// sequence where a = 2
// and b = 3
public static int probability(int N)
{
// The first two numbers in
// the sequence are initialized
int a = 2;
int b = 3;
// Base cases
if (N == 1)
{
return a;
}
else if (N == 2)
{
return b;
}
else
{
// Loop to compute the fibonacci
// sequence based on the first
// two initialized numbers
for(int i = 3; i <= N; i++)
{
int c = a + b;
a = b;
b = c;
}
return b;
}
}
// Function to find the probability
// of not getting two consecutive
// heads when N coins are tossed
public static float operations(int N)
{
// Computing the number of
// favourable cases
int x = probability(N);
// Computing the number of
// all possible outcomes for
// N tosses
int y = (int)Math.Pow(2, N);
return round((float)x /
(float)y, 2);
}
// Driver code
public static void Main(string[] args)
{
int N = 10;
Console.WriteLine((operations(N)));
}
}
// This code is contributed by chitranayal
Javascript
<script>
// javascript implementation to find the
// probability of not getting two
// consecutive heads together when
// N coins are tossed
function round(vr, digit) {
var value = parseInt( (vr* Math.pow(10, digit) + .5));
return value / Math.pow(10, digit);
}
// Function to compute the N-th
// Fibonacci number in the
// sequence where a = 2
// and b = 3
function probability(N) {
// The first two numbers in
// the sequence are initialized
var a = 2;
var b = 3;
// Base cases
if (N == 1) {
return a;
} else if (N == 2) {
return b;
} else {
// Loop to compute the fibonacci
// sequence based on the first
// two initialized numbers
for (i = 3; i <= N; i++) {
var c = a + b;
a = b;
b = c;
}
return b;
}
}
// Function to find the probability
// of not getting two consecutive
// heads when N coins are tossed
function operations(N) {
// Computing the number of
// favourable cases
var x = probability(N);
// Computing the number of
// all possible outcomes for
// N tosses
var y = parseInt( Math.pow(2, N));
return round(x / y, 2);
}
// Driver code
var N = 10;
document.write((operations(N)));
// This code is contributed by aashish1995
</script>
Producción:
0.14
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)