2023-09-23:用go语言,假设每一次获得随机数的时候,这个数字大于100的概率是P。
尝试N次,其中大于100的次数在A次~B次之间的概率是多少?
0 < P < 1, P是double类型,
1
来自左程云。
答案2023-09-23:
首先,我们可以使用动态规划来解决这个问题。我们可以定义一个二维数组dp,其中dp[i][j]表示在i次尝试中,获得j次大于100的随机数的概率。
然后,我们可以使用递归的方式计算dp[i][j]。具体地说,我们可以将每一次尝试分为两种情况:获得大于100的随机数和获得小于等于100的随机数。如果我们获得大于100的随机数,则剩余的i-1次尝试中,我们需要获得j-1次大于100的随机数;如果我们获得小于等于100的随机数,则剩余的i-1次尝试中,我们还需要获得j次大于100的随机数。我们可以使用更大的P表示获得大于100的随机数的概率,用1-P表示获得小于等于100的随机数的概率。
递归的边界条件是如果i为0且j为0,则表示已经没有剩余的尝试次数,并且已经获得了所需的j次大于100的随机数,所以概率为1;如果i为0且j不为0,则表示已经没有剩余的尝试次数,但是还没有满足所需的j次大于100的随机数,所以概率为0。
为了避免重复计算,我们可以使用一个二维数组dp来保存计算过的结果。在每次计算前,先检查dp[i][j]是否已经计算过,如果是,则直接返回结果。
最后,在主函数中,我们可以调用probability函数来计算概率,并打印结果。
总的时间复杂度和额外空间复杂度分别为O(N^2),因为需要计算dp数组的所有元素。
go完整代码如下:
package?main
import?"fmt"
func?probability(P?float64,?N?int,?A?int,?B?int)?float64?{
dp?:=?make([][]float64,?N+1)
for?i?:=?0;?i?
dp[i]?=?make([]float64,?N+1)
for?j?:=?0;?j?
dp[i][j]?=?-1
}
}
ans?:=?0.0
for?j?:=?A;?j?
ans?+=?process(P,?1-P,?N,?j,?dp)
}
return?ans
}
func?process(more,?less?float64,?i,?j?int,?dp?[][]float64)?float64?{
if?i?
return?0
}
if?i?==?0?&&?j?==?0?{
return?1
}
if?dp[i][j]?!=?-1?{
return?dp[i][j]
}
ans?:=?more*process(more,?less,?i-1,?j-1,?dp)?+?less*process(more,?less,?i-1,?j,?dp)
dp[i][j]?=?ans
return?ans
}
func?main()?{
P?:=?0.6
N?:=?100
A?:=?30
B?:=?50
fmt.Println(probability(P,?N,?A,?B))
}
在这里插入图片描述rust完整代码如下:
fn?probability(p:?f64,?n:?i32,?a:?i32,?b:?i32)?->?f64?{
let?mut?dp:?Vec?=?vec![vec![-1.0;?(n?+?1)?as?usize];?(n?+?1)?as?usize];
let?mut?ans?=?0.0;
for?j?in?a..=b?{
ans?+=?process(p,?1.0?-?p,?n,?j,?&mut?dp);
}
ans
}
fn?process(more:?f64,?less:?f64,?i:?i32,?j:?i32,?dp:?&mut?Vec)?->?f64?{
if?i?
return?0.0;
}
if?i?==?0?&&?j?==?0?{
return?1.0;
}
if?dp[i?as?usize][j?as?usize]?!=?-1.0?{
return?dp[i?as?usize][j?as?usize];
}
let?ans?=?more?*?process(more,?less,?i?-?1,?j?-?1,?dp)?+?less?*?process(more,?less,?i?-?1,?j,?dp);
dp[i?as?usize][j?as?usize]?=?ans;
ans
}
fn?main()?{
let?p?=?0.6;
let?n?=?100;
let?a?=?30;
let?b?=?50;
println!("{}",?probability(p,?n,?a,?b));
}
在这里插入图片描述c++完整代码如下:
#include?
#include?
double?process(double?more,?double?less,?int?i,?int?j,?std::vector&?dp);
double?probability(double?P,?int?N,?int?A,?int?B)?{
std::vector?dp(N?+?1,?std::vector(N?+?1,?-1));
double?ans?=?0;
for?(int?j?=?A;?j?
ans?+=?process(P,?1?-?P,?N,?j,?dp);
}
return?ans;
}
double?process(double?more,?double?less,?int?i,?int?j,?std::vector&?dp)?{
if?(i?
return?0;
}
if?(i?==?0?&&?j?==?0)?{
return?1;
}
if?(dp[i][j]?!=?-1)?{
return?dp[i][j];
}
double?ans?=?more?*?process(more,?less,?i?-?1,?j?-?1,?dp)?+?less?*?process(more,?less,?i?-?1,?j,?dp);
dp[i][j]?=?ans;
return?ans;
}
int?main()?{
double?P?=?0.6;
int?N?=?100;
int?A?=?30;
int?B?=?50;
std::cout?
return?0;
}
在这里插入图片描述c完整代码如下:
#include?
#include?
double?probability(double?P,?int?N,?int?A,?int?B);
double?process(double?more,?double?less,?int?i,?int?j,?double**?dp);
double?probability(double?P,?int?N,?int?A,?int?B)?{
double**?dp?=?(double**)malloc((N?+?1)?*?sizeof(double*));
for?(int?i?=?0;?i?
dp[i]?=?(double*)malloc((N?+?1)?*?sizeof(double));
}
for?(int?i?=?0;?i?
for?(int?j?=?0;?j?
dp[i][j]?=?-1;
}
}
double?ans?=?0;
for?(int?j?=?A;?j?
ans?+=?process(P,?1?-?P,?N,?j,?dp);
}
for?(int?i?=?0;?i?
free(dp[i]);
}
free(dp);
return?ans;
}
double?process(double?more,?double?less,?int?i,?int?j,?double**?dp)?{
if?(i?
return?0;
}
if?(i?==?0?&&?j?==?0)?{
return?1;
}
if?(dp[i][j]?!=?-1)?{
return?dp[i][j];
}
double?ans?=?more?*?process(more,?less,?i?-?1,?j?-?1,?dp)?+?less?*?process(more,?less,?i?-?1,?j,?dp);
dp[i][j]?=?ans;
return?ans;
}
int?main()?{
double?P?=?0.6;
int?N?=?100;
int?A?=?30;
int?B?=?50;
printf("%f\n",?probability(P,?N,?A,?B));
return?0;
}
在这里插入图片描述
领取专属 10元无门槛券
私享最新 技术干货