量化笔面试概率题*2

一不小心鸽了快两周，最近暑期面试，没啥灵感写推文。现在基本上是暑期投递的尾巴了，今天总结下笔面试多次碰到两类概率题，供大家参考。我投的基本都是量化岗，到现在3/20的通过率，总之很艰难。

贝叶斯公式

我参加的现场笔试，都碰到了用贝叶斯公式算概率题，跟大一概率论书上的东西差不多，贝叶斯的思想是用先验概率来估计后验概率，总结成公式如下

这个不难，就是长时间不看可能会记不清楚，练练就好，举个例子

设某工厂有甲、乙、丙三个车间生产同一种产品，已知各车间的产量分别占全厂产量的25%，35%，40%，各车间的次品率依次为5%,4%,2%,现从待出场的产品中检查出一个次品，求他是甲车间生产的概率。

首先定义事件：A1,A2,A3分别表示产品由甲、乙、丙车间生产，B表示产品为次品，由已知

动态规划

动态规划是一种求解问题的思想，逻辑上跟递归是一样的，只是编程实现上有差别，举个例子

抛一枚硬币，正反面概率都是0.5，连续抛出四个正面就停止，问最小需要抛的次数的期望是多少？（平均需要抛多少次）

这个如果用传统的排列组合方法算，理论上可以算，算出每个整数n的情况下，最后四个都是正面，并且之前不连续超过四个正面的概率，再用期望公式求和，但是会非常麻烦，但是用动态规划就会简单很多。

设连续k次正面的期望为E(k),这里我们需要求的是E(4)的值，E(k)可以理解为平均需要抛k次。考虑E(k)和E(k+1)之间的关系，假设已经出现了连续k个正面，下一次抛硬币会有两种情况：

0.5的概率抛出来正面，这时候满足了连续k+1个正面的条件，总次数为E(k)+1;

0.5的概率抛出来反面，这时候要抛出连续k+1个正面，之前抛得都没有用了，需要重头再来，也就是在E(k)的基础上，再抛E(k+1)次；

从而可以得到E(k)与E(k+1)的关系如下

化简之后得到

这样就得到了E(k)和E(k+1)之间的关系，根据递推算通项得到

因此只需要算E(1)。考虑E(1),即前n-1次都是反面，最后一次是正面

求和计算过程如下

因此E(k) = 2^(k+1) - 2，这样，E(4) = 30

再举一个例子

有一楼梯共m级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第m级，共有多少走法？

注：规定从一级到一级有0种走法。

还是刚才的逻辑，假设走k级有f(k)种走法，显然f(1)=1,f(2)=2，如果第一次走了1级，剩下k-1级有f(k-1)种走法，如果第一次走了两级，剩下k-2级有f(k-2)种走法，即f(k)=f(k-1)+f(k-2)。已知递推式和边界条件，很容易写出来代码。

这里唯一需要注意的点是，写代码时候如果递归的化话速度会很慢，因为每次算的时候都要从边界条件f(1)和f(2)开始算，有很多部分是重复的，所以用动态规划好一点，也就是每次算完之后都保存之前的值，这样占用的内存会多一点，但速度会快很多，代码如下

def f(x):
    if x ==1:
        y = 1
    elif x ==2:
        y = 2
    else:
        s = [0 for i in range(x+1)]
        s[0] = 1
        s[1] = 1
        s[2] = 1
        for i in range(3,x+1):
            s[i] = s[i-1] + s[i-2]
        y = s[x]
    return y
       
n = int(raw_input())
for i in range(n):
    m = int(raw_input().split()[0])
    y = f(m)
    print(y)