原文:
给定一枚投掷 n 次的公平硬币，任务是确定没有两个头像连续出现的概率。
示例:
输入: n = 2 输出: 0.75 说明: 硬币掷 2 次，可能的结果是{th，ht，tt，hh}。 因为在四分之三的结果中，头部不会同时出现。 因此，所需概率为(3/4)或 0.75
输入: n = 3 输出: 0.62 说明: 硬币掷 3 次，可能的结果是{ttt、htt、tht、tth、hht、hth、thh、hhh}。 因为八分之五的结果中，头部不会同时出现。 因此，所需概率为(5/8)或 0.62
方法:必须对有利结果的数量进行以下观察。
- n = 1 时:可能的结果是{t，h}。两者中有两个有利的结果。
- n = 2 时:可能的结果是{th，ht，tt，hh}。四个中有三个有利结果。
- n = 3 时:同样，可能的结果是{ttt、htt、tht、tth、hht、hth、thh、hhh}。八个中有五个有利结果。
- n = 4 时:同样，可能的结果有{tttt、ttth、ttht、thtt、httt、tthh、thth、htht、hhtt、thht、htth、thhh、hthh、hhth、hhht、hhhhhh }。十六个中有八个有利结果。
显然，有利结果的数量遵循斐波那契数列，其中 fn(1) = 2，fn(2) = 3，依此类推。因此，想法是实现斐波那契序列，以便找到有利案例的数量。显然，病例总数为 2 n 。 为了计算概率，使用以下公式:
p =有利案例/案例总数
下面是上述方法的实现:
c
// c implementation to find the
// probability of not getting two
// consecutive heads together when
// n coins are tossed
#include
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
python 3
# 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
java 描述语言
output:
0.14
时间复杂度:0(n)
辅助空间:0(1)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
