最早公布在我的小站,对Mathjax
渲染比拟好,可能辨认行内公式。
Problem 329
一只懂质数的青蛙站在编号为1-500的方块内,它等概率的向左或者向右跳,当然不能出1-500这些方块,如果达到了边缘就只能向另外一个方向跳。
如果方块的编号是质数,那么有2/3的概率呱出 ‘P’ (PRIME),1/3的概率呱出 ‘N’ (NOT PRIME);反之如果编号不是质数,那么呱出’P’和’N’的概率别离是1/3和2/3。
如果它从随机的一点登程(等概率),收回 ‘PPPPNNPPPNPPNPN’ 的概率是多少呢?应用最简分数给出答案。
这个题目绝对比拟间接。
应用一个List
放一系列数值对,每一对示意概率的分子和分母。从1-500个编号登程,将每种状况的概率存起来。
var probabilities = new List<(long, long)>();
for (int i = 1; i <= 500; i++)
{
GetProbabilityAt(i, probabilities);
}
如果具体计算每种状况的概率呢?应用递归,假设第$k$步从第$i$个地位跳到第$j$的地位,在地位$i$的时候概率是$p$,接下来思考方向对应的概率和到了地位$j$之后依据题目失去呱出想要的字母的概率,两个之乘再乘以$p$就是达到地位$j$的概率,直至呱完所有的字母停下来就是一个可能的值,重复递归就失去了一系列的概率,求和就是对应每种状况的概率。不过我具体的实现没有求和,因为最初把500个系列的概率一起就和就能够了。
private void GetProbabilityAt(int i, List<(long, long)> p)
{
GetProbabilityAt(i, 0, 1, 1, p);
}
private void GetProbabilityAt(int i, int step, long numerator, long denominator, List<(long, long)> result)
{
var (n, d) = GetProbabilityWithCroak(i, croaks[step]);
numerator *= n;
denominator *= d;
step++;
if (step == croaks.Length)
{
result.Add((numerator, denominator));
return;
}
if (i == 1)
{
GetProbabilityAt(i + 1, step, numerator, denominator, result);
return;
}
if (i == 500)
{
GetProbabilityAt(i - 1, step, numerator, denominator, result);
return;
}
GetProbabilityAt(i + 1, step, numerator, denominator * 2, result);
GetProbabilityAt(i - 1, step, numerator, denominator * 2, result);
}
GetProbabilityWithCroak
计算达到每一个方块对应的概率,依据题意
private static (long, long) GetProbabilityWithCroak(int i, char p)
{
if (p == 'P')
{
if (primes[i] != 0)
{
return (2, 3);
}
else
{
return (1, 3);
}
}
else
{
if (primes[i] != 0)
{
return (1, 3);
}
else
{
return (2, 3);
}
}
}
失去一系列的概率之后须要求和了。分母不一样,须要通分,怎么找到最小公分母呢?其实很简略,15步,每步往左或者往右,分母乘了2,呱某个字母的概率是1/3或者2/3,那么分母乘了3,所有公分母是$6^{15}$。
var commonD = (long)Math.Pow(6, 15);
long numerator = 0;
foreach (var pair in probabilities)
{
numerator += pair.Item1 * commonD / pair.Item2;
}
间隔失去最初答案还有两步之遥。一是依据题意等概率的从某个格子登程,一开始咱们也for
循环了500次,所以分母还要乘以500;二是分子分母同除最大公约数化简。
commonD *= 500;
var gcd = Utils.GetGcd(numerator, commonD);
return $"{numerator / gcd}/{commonD / gcd}";
发表回复