一不小心鸽了快两周,最近暑期面试,没啥灵感写推文。现在基本上是暑期投递的尾巴了,今天总结下笔面试多次碰到两类概率题,供大家参考。我投的基本都是量化岗,到现在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个正面,下一次抛硬币会有两种情况:
从而可以得到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)