关于数学:欧拉项目-329题-一只懂质数的青蛙

最早公布在我的小站，对 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}";