最早发布在我的小站,对Mathjax渲染比较好,能够识别行内公式.
Problem 329
一只懂质数的青蛙站在编号为1-500的方块内,它等概率的向左或者向右跳,当然不能出1-500这些方块,如果到达了边缘就只能向另外一个方向跳.
如果它从随机的一点出发(等概率),发出 'PPPPNNPPPNPPNPN' 的概率是多少呢?使用最简分数给出答案.
这个题目相对比较直接.
使用一个List放一系列数值对,每一对表示概率的分子和分母.从1-500个编号出发,将每种情况的概率存起来.
如果具体计算每种情况的概率呢?使用递归,假定第$k$步从第$i$个位置跳到第$j$的位置,在位置$i$的时候概率是$p$,接下来考虑方向对应的概率和到了位置$j$之后根据题目得到呱出想要的字母的概率,两个之乘再乘以$p$就是到达位置$j$的概率,直至呱完所有的字母停下来就是一个可能的值,反复递归就得到了一系列的概率,求和就是对应每种情况的概率.不过我具体的实现没有求和,因为最后把500个系列的概率一起就和就可以了.
距离得到最后答案还有两步之遥.一是根据题意等概率的从某个格子出发,一开始我们也for循环了500次,所以分母还要乘以500;二是分子分母同除最大公约数化简.