互联网概率智力面试题整理

# 1.半径为1的圆中随机选取一点
- 方法1：在x轴[-1,1]，y轴[-1,1]的正方形随机选取一点，如果此点在圆内，则即为所求的点。如果不在圆内，则重新随机直到选到了为止。
- 方法2：从[0, 2*pi)随机选取一个角度，再在这个方向的半径上随机选取一个点。`但半径上的点不能均匀选取，选取的概率要和离圆心的距离成正比`，这样才能保证随机点在圆内是均匀分布的。

# 2.一根木棒，截成三截，组成三角形的概率是多少？
- 设第一段截`x`，第二段截`y`，第三段`1-x-y`。
- 考虑所有可能的截法。可能的截法中必须保证三条边都是正数且小于原来边长，则有`0<x<1，0<y<1，0<1-x-y<1`，画图可知，(x,y)必须在单位正方形的左下角的半个直角三角形里，面积为1/2。
- 然后考虑能形成三角形的截法。首先要满足刚才的三个条件`0<x<1，0<y<1，0<1-x-y<1`，然后必须符合三角形的边的要求，即两边之和大于第三边，`x+y>1-x-y，x+1-x-y>y，y+1-x-y>x`，化简即得`0<x<1/2，0<y<1/2，1/2<x+y<1`画图可知，此时`(x,y)`必须在边长为1/2的三角形的右上角的半个直角三角形里，面积为`1/8`。于是最终概率为`(1/8)/(1/2) = 1/4`。

# 3. 抛色子求期望问题
- 抛一个六面的色子，连续抛直到抛到6为止，问期望的抛的次数是多少
- 方法1：因为每次抛到6的概率相等，都是1/6，于是期望的次数就是1/(1/6)=6次。
- 方法2：下面用一种不一样的方法解答，假设期望的次数为`E`。考虑第一次抛，如果已经抛到6了（概率为1/6），那么就不用再抛了。如果没抛到6（概率为5/6），那么还需要继续抛，可是还要抛多少次呢？显然，现在开始知道抛到6的次数仍然是E，但是刚刚已经抛了一次了于是可以得到这个等式
$E = 1 \times \frac{1}{6} + (1 + E) \times \frac{5}{6} $，
解得$ E = 6 $。即期望的次数为6次。
- 方法3：我们任然设期望的次数为`E,f(n)`表示前n次抛出了6的概率,那么，我们可以不像方法2那样考虑递推式，而是直接采用极限思想求和即可：
$E = {\lim\limits_{n \to +\infty}}{f(n)} = 1 \times \frac{1}{6} + 2\times \frac{5}{6}\times\frac{1}{6} +  + 3 \times \frac{5}{6} \times \frac{5}{6}\times\frac{1}{6} + ... + n \times {(\frac{5}{6})}^{n-1} \times \frac{1}{6}.$
可以发现这是很明显的差比数列，错位相减得到通项公式为：
$E = {\lim\limits_{n \to +\infty}}{f(n)} = \lim\limits_{n \to +\infty}{( 6\times(1 - (\frac{5}{6})^n)- n \times (\frac{5}{6})^n )} = 6.$
# 4. 白球涂色问题
- 一个木桶里面有M个白球，每分钟从桶中随机取出一个球涂成红色（无论白或红都涂红）再放回，问将桶中球全部涂红的期望时间是多少？
- 令`桶中有i个红球后再把全部球涂红的期望时间为a[i]`，此时再取出一个球，如果是红色的（概率为i/M），则直接放回，且剩余的期望时间仍是a[i]。如果是白色的（概率为1-i/M），则涂红后放回，剩余的期望时间为a[i+1]，则
$a[i] = (1 + a[i]) * i/M + (1 + a[i+1]) * (1 – i/M)$
即 $a[i] = a[i+1] + M/(M-i)$
显然，有$a[M] = 0$,
可以解得 $a[0] = M/M + M/(M-1) + … + M/1 + 0 $

# 5. 宝剑升级问题
- **你有一把宝剑。每使用一个宝石，有50%的概率会成功让宝剑升一级，50%的概率会失败。如果宝剑的级数大于等于5的话，那么失败会使得宝剑降1级。如果宝剑的级数小于5的话，失败没有效果。问题是：期望用多少个宝石可以让一把1级的宝剑升到9级？**

- 问题比较简单，用`a[i]表示从第i-1级升到第i级期望使用的宝石数量`。
- 当i<=5时，因为不会降级，则期望的数量均为2，即a[2] = a[3] = a[4] = a[5] = 2
- 当i>5时，因为会降级，成功时一个宝石就够了，不成功时需要倒退一级，需要先使用a[i-1]个宝石先回到i-1级，再使用a[i]个宝石升到第i级，即
$a[i] = 1 * 1/2 + (1 + a[i-1] + a[i]) * 1/2;$
即$ a[i] = a[i-1] + 2$;
可知，$a[6]= 4, a[7] = 6, a[8] = 8, a[9] = 10;$
则1级到9级需要的宝石数为 $ a[2]+…+a[9] = 36 $。
# 6. rand7()转rand10()
- **已知有个rand7()的函数，返回1到7随机自然数，怎样利用这个rand7()构造rand10()，随机1~10**。
- 产生随机数的`主要原则是每个数出现的概率是相等的，如果可以得到一组等概率出现的数字，那么就可以从中找到映射为1~10的方法`。
`rand7()`返回1~7的自然数，构造新的函数 `(rand7()-1)*7 + rand7()`，这个函数会随机产生1~49的自然数。原因是1~49中的每个数只有唯一的第一个rand7()的值和第二个rand7()的值表示，于是它们出现的概率是相等。
但是这里的数字太多，可以丢弃41~49的数字，把1~40的数字分成10组，每组映射成1~10中的一个，于是可以得到随机的结果。
具体方法是，利用`(rand7()-1)*7 + rand7()`产生随机数x，如果大于40则继续随机直到小于等于40为止，如果小于等于40，则产生的随机数为`(x-1)/4+1`。
- 拓展：
    - **已知有个randM()的函数，返回1到M随机自然数，怎样利用这个randM()构造randN()，随机1~N**。
    - 当N<=M时可以直接得到。
    - 当N>M时，类似构造$(randM()-1)*M + randM()$，可以产生`1~M^2（即randM^2）`，可以在M^2中选出N个构造1~N的映射。如果$M^2$还是没有N大，则可以对于$rand{M^2}$继续构造，直到成功为止。

# 7. 构造等概率发生器
- **已知一随机发生器，产生0的概率是p，产生1的概率是1-p，现在要你构造一个发生器，使得它产生0和1的概率均为1/2。**
- 考虑连续产生两个随机数，结果只有四种可能：`00、01、10、11`，其中产生01和产生10的概率是相等的，均为`p*(1-p)`，于是可以利用这个概率相等的特性等概率地产生01随机数。
比如把01映射为0,10映射为1。于是整个方案就是：
产生两个随机数，如果结果是00或11就丢弃重来，如果结果是`01`则产生`0`，结果是`10`则产生`1`。
- 拓展：
    - **已知一随机发生器，产生的数字的分布不清楚，现在要你构造一个发生器，使得它产生0和1的概率均为1/2。**
    - 思路类似，考虑连续产生两个随机数a、b，结果有三种情况`a==b，a>b，a<b`，其中由于a和b的对称性，`a>b`和`a<b`出现的概率是相等的，于是可以利用这个概率相等的特性等概率地产生01随机数。方法类似。
    - 或者可以找到另一种概率相等的事件，比如选择一个`阈值th`，把随机数的结果分为小于阈值和大于等于阈值两种情况，于是连续产生两个随机数，他们一个小于阈值，另一个大于等于阈值的概率是相等。然后类似产生随机数。
    - **已知一随机发生器，产生0的概率是p，产生1的概率是1-p，构造一个发生器，使得它构造1、2、3的概率均为1/3；…。更一般地，构造一个发生器，使得它构造1、2、3、…n的概率均为1/n**
    - 此时我们已经知道，`要从n个数中等概率地产生一个随机数，关键是要找到n个或更多个出现概率相等的事件`，然后我们重复随机地产生事件，如果是跟这n个事件不同的事件直接忽略，直到产生这n个事件中的一个，然后就产生跟这个事件匹配的随机数。由于n个事件发生的概率相等，于是产生的随机数的概率也是相等的。
    - 考虑连续产生x个随机数，结果应该是x个0跟1的组合，为了使某些结果出现的概率相等，我们应该要让这个结果中0和1出现的次数相等，即各占一半。于是x的长度必须是偶数的，为了方便，`考虑连续产生2x个随机数`。每个0跟1各出现一半的结果可以赋予1到n的某个数，为了能够表示这n个数，需要0跟1各出现一半的总结果数大于等于n，即
    $C_{2*x}^{x} >= n $
    解出最小的x即为效率最高的x。
    然后把前n个0和1个出现一半的结果分别赋予1到n的值。随机时连续产生`2*x`个数，如果不是这n个结果中的一个则重新随机，如果是的话则产生对应的值作为随机结果。
# 8. 黑白球取球放球问题
- **一个桶里面有白球、黑球各100个，现在按下述规则取球**： 
    - i 、每次从桶里面拿出来两个球； 
    - ii、如果取出的是两个同色的求，就再放入一个黑球； 
    - iii、如果取出的是两个异色的求，就再放入一个白球。 
- **问：最后桶里面只剩下一个黑球的概率是多少？**
- 动态规划，令`f[i,j]表示有i个白球，j个黑球的概率`。 
已知f[100,100] = 1, 求f[0,1]。 
拿到两个白球: $f[i-2,j+1] = i/(i+j) * (i-1)/(i+j-1) * f[i,j]$ 
拿到两个黑球: $f[i, j-1] = j/(i+j) * (j-1)/(i+j-1) * f[i,j] $
拿到一黑一白: $f[i, j-1] =2 * i/(i+j) * j/(i+j-1) * f[i,j]$

# 9. 最后的人最可能到达的时间
- **10个人出去玩，集合时间有10分钟，每个人都在该时间内到达，概率均匀分布，彼此独立，那么最后一个人最有可能到达的时间是？**
- 遇到这种想不明白，最好的方法就是枚举。 
- 若最后一个人在10分钟到达（概率`1/10`），其他人也都已经到达了（概率是1），总概率是 $(1)^9 * (1/10)$ 
- 若最后一个人在9分钟到达（概率`1/10`），其他人全部在此之前到达的概率是$(9/10)^9$，总概率是 $(9/10)^9 * (1/10)$ 
- 依此类推，可见概率最大的是第10分钟。

# 10. 让最少人死亡的策略
- **100个人排队，每个人只能看到自己之前的人的帽子的颜色（假设只有黑白两色），每个人都得猜自己帽子的颜色，只能说一次，说错就死掉，别人可以听到之前的人的答案以及是否死掉。请问用什么策略可以让死掉的人最少（死掉的概率最小即可）。**
- 方法1：假设只有3个人，假设`true = 白，false = 黑`，用这个公式`x3 = (x1 == x2)`，用人话就是1和2的帽子颜色一样的话就说白，不一样的话就说黑。这个策略第一个人死的概率是1/2，剩下的两个都不会死。 
推广到4个人，也就是`x4 = (x3 == (x1 == x2))`，照理可以推广到100人。但问题就是人很难判断，只能靠计算机来算。 
- 方法2：“最后一个人看一下`前面白帽子的个数是奇数还是偶数`，比如约定奇数说黑，偶数说白。这样前面的人都可以推断出来正确的结果。”
# 11.扑克牌分三堆，大小王在同一堆的概率
- **54张牌，平均分成三堆，求大小王在同一堆的概率?**
- 方法1：排列组合：$\frac{C^{16}_{52} C^{18}_{36}C^{18}_{18}/A_2^2}{C^{18}_{54}C^{18}_{36}C^{18}_{18}/A_3^3}=17/53$
- 方法2：或者这样更简单：先平均分三堆，大王在第一堆的概率是1/3, 小王在剩下的53张牌中，有17/53的概率和大王同一堆。依此类推，大王还可能在2,3堆，因此 
`1/3∗17/53∗3=17/53`
# 12.买饮料问题
- **买饮料，三个瓶盖可以换一瓶，请问要买100瓶饮料，最少需要买多少瓶？**
- 设最少需要买$x$瓶：则有$x+x/3+x/9+...+x/3n>=100$
这又是等比数列求和，$\frac {x(1 - (\frac{1}{3})^n)}{1 - \frac{1}{3}} >= 100$,
$\frac{3}{2} * x >= 100$
需要向上取整，所以取$x = 68$.
原文这里说$x = 69$，我认为是错的，就是应该是$x = 68$

# 13.从大输入流中等概率取数字
- **有一个很大很大的输入流，大到没有存储器可以将其存储下来，而且只输入一次，如何从这个输入流中等概率随机取得m个记录？（即从中等概率地随机取m个数）**
- 如果可以输入两次，那就可以统计出总数N, 再随机0到N-1数，去个重，然后第二次输入的适合就可以保存对应的数即可。
- 这里只能输入一次，这里给出两种方法。
    - 第一种。在输入的过程中，给每个记录一个[0,1]的随机数，最后取随机数最大的前m个记录。可以用size为m的小根堆来维护。
    - 第二种，`蓄水池抽样(reservoir sample)`。假设输入到第n个记录了，以m/n的概率取该数，如果取中则随机替换掉原来取中的m个记录中的一个。初始时，选中前m个记录。乍一看好像不靠谱，一证明就服了。证明也很简单。
假设n-1时成立，即前n-1个记录，均以m/(n-1)的概率来判断是否选中。我们要证明，`输入第n个记录后，前n个记录均以m/n的概率来判断是否选中`。 
对于第n个记录，以m/n的概率选择它，ok，满足要求。现在来看剩下的前n-1个记录。对于在前n-1记录中被选中的第`i`个记录，当前保持被选中的可能，要么是第n个记录没有被选中`(1-m/n) * (m/(n-1))`，要么是第n个记录选中了但是`i`没有被替换掉(替换的是其他的数字): `m/n * (m-1)/m * m/(n-1)`，两者相加正好等于`m/n`，由此得证。

# 14. 10分钟看到车的概率
- **在一条高速公路上，在30分钟内看到一辆汽车的可能性是0.95，那么在10分钟内看到一辆车的概率是多少?（假设过车的概率是恒定的）**
- 记10分钟内看到车的概率为p. 那么30分钟都没看到车的概率是$(1−p)^3=1−0.95=0.05 $
所以$p=1−0.05^{\frac{1}{3}} = 0.632$

# 15. 洗牌算法
- **给你一个数组，设计一个既高效又公平的方法随机打乱这个数组（此题和洗牌算法的思想一致）**
- 方法比较简单，基本思想是每次随机取一个数，然后把它交换到最后的位置。然后对前（n-1）个数使用递归的算法。
```
//递归版本
void suffle_dfs(int ar[], int n)  
{  
    if(n<=1)return;  
    swap(ar[n-1], ar[rand()%n]);  
    shuffle_dfs(ar,n-1);  
}  
//非递归版本
void suffle(int ar[], int n)  
{  
    while(n>1){  
        swap(ar[n-1], ar[rand()%n]);  
        n--;  
    }  
}
```
# 16.抛硬币吃苹果问题
- **有一苹果，两个人抛硬币来决定谁吃这个苹果，先抛到正面者吃。问先抛这吃到苹果的概率是多少？ **
- 给所有的抛硬币操作从1开始编号，显然先手者只可能在奇数`（1,3,5,7…）`次抛硬币得到苹果，而后手只可能在偶数次`（2,4,6,8…）`抛硬币得到苹果。
- 方法1：设先手者得到苹果的概率为p，第1次抛硬币得到苹果的概率为1/2，在第3次`（3,5,7…）`以后得到苹果的概率为`p/4`（这是因为这种只有在第1次和第2次抛硬币都没有抛到正面（概率为$1/4=1/2*1/2$）的时候才有可能发生，而且此时先手者在此面临和开始相同的局面）。所以可以列出等式$p=1/2+p/4$，所以：$p=\frac{2}{3}$。
- 方法2：设先手者得到苹果的概率为p，则把所有p可以获胜的情况考虑即可：$ p = \frac{1}{2} + \frac{1}{2} \times \frac{1}{2} \times \frac{1}{2}+...+ \frac{1}{2} \times (\frac{1}{2} \times \frac{1}{2})^n+... $
这是典型的等比数列求和后求极限的问题：
$ p = \frac{\frac{1}{2}(1 - (\frac{1}{4})^n)}{1 - \frac{1}{4}}= \frac{2}{3}$ 
# 17.重男轻女国家男女比例问题
- **一个国家人们只想要男孩，每个家庭都会一直要孩子，只到他们得到一个男孩。如果生的是女孩，他们就会再生一个。如果生了男孩，就不再生了。那么，这个国家里男女比例如何？**
- 一开始想当然的以为男多女少，毕竟都想要男孩。但是注意这句话“如果生了男孩，就不再生了”，一个家庭可能有多个女孩，只有一个男孩。再仔细分析，我们来计算期望值，只用计算一个家庭就行了。设一个家庭男孩个数的期望值为S1，女孩为S2. 
- 根据题目条件，男孩的个数期望值S1=1这个是不用计算了。主要计算S2
- 一个家庭的孩子数量可以为:`1,2,3,4,5,...` 对应的的男女分布为: `“男”,”女男”,”女女男”,”女女女男”,”女女女女男”,...`

- 对应的概率分布为`1/2, 1/4, 1/8, 1/16, 1/32` 。其中女孩的个数分别为 `0,1,2,3,4,...`

- 因此`S2=0*1/2 + 1*1/4 + 2*1/8 + 3*1/16 + 4*1/32 + ...`
- 可以按照题目2用级数求，也可以用错位相减法：`S2=1/4+2/8+3/16+4/32+…`  两边乘以2,得: `2*S2=1/2 + 2/4 + 3/8 + 4/16 + 5/32 + ...`

- 两个式子相减得`S2=1/2+1/4+1/8+1/16+1/32+…=1.` 所以期望值都为1，男女比例是一样的。

# 18. 怎样使用一个3升的杯子和一个5升的杯子,倒出4升水
- 1、将5升杯子装满，往bai3升杯子里倒，直到du满。
这时5升的杯子里还剩2升水。zhi
- 2、把3升杯子水倒掉，dao5升杯子里剩下的2升水倒入3升空杯里。
这时3升杯子里有2升水。
- 3、把5升杯子灌满，再用5升杯子将刚才没满的3升杯子倒满。
这时5升杯子里剩下的水就是4升了哦

# 19. 圆桌硬币问题
- 描述
两个人轮流往一张圆桌上放硬币（硬币须全部在桌面上），当一方没有位置可放的时候，另一方获胜。问是否有一种策略可以让判断是先手获胜还是后手获胜？如果有，策略是什么？
- 圆桌策略
使用对称原理，如果先手将硬币放在圆桌的中心，那么当后手每放一枚硬币的时候，先手都可以找到以中心硬币为对称点的硬币放置位置。因此先手获胜的策略是：在圆桌中心放置一枚硬币，然后当后手没放一枚硬币的时候，找到对称的位置，放置硬币，即可。

# 20. 山洞找狐狸问题
- 五个洞排成一排，其中一个洞里藏有一只狐狸。每个夜晚，狐狸都会跳到一个相邻的洞里；每个白天，你都只允许检查其中一个洞。怎样才能保证狐狸最终会被抓住？
- 答案：
按照`2, 3, 4, 2, 3, 4`的顺序检查狐狸洞可以保证抓住狐狸。为了说明这个方案是可行的，用集合F表示狐狸可能出现的位置，初始时F = {1, 2, 3, 4, 5}。如果它不在2号洞，则第二天狐狸已经跑到了F = {2, 3, 4, 5}。如果此时它不在3号洞，则第三天狐狸一定跑到了F = {1, 3, 4, 5}。如果此时它不在4号洞，则再过一晚后F = {2, 4}。如果此时它不在2号洞，则再过一天F = {3, 5}。如果此时它不在3号洞，再过一天它就一定跑到4号洞了。
- 方案不是唯一的，下面这些方案都是可行的：
    - 2, 3, 4, 4, 3, 2
    - 4, 3, 2, 2, 3, 4
    - 4, 3, 2, 4, 3, 2
    - https://blog.csdn.net/xishining/article/details/92027374

# 21.翻扑克牌问题
- 给一个瞎子52张扑克牌，并告诉他里面恰好有10张牌是正面朝上的。要求这个瞎子把牌分成两堆，使得每堆牌里正面朝上的牌的张数一样多。瞎子应该怎么做？
- 答案：把扑克牌分成两堆，一堆10张，一堆42张。然后，把小的那一堆里的所有牌全部翻过来。
- 拓展：如果有x张正面向上的，则分成x和52-x两堆，并翻转x那一堆

# 22. 抛硬币产生概率问题
- 如何用一枚硬币等概率地产生一个1到3之间的随机整数？如果这枚硬币是不公正的呢？
- 答案：如果是公正的硬币，则投掷两次，“正反”为1，“反正”为2，“正正”为3，“反反”重来。
- 如果是不公正的硬币，注意到出现“正反”和“反正”的概率一样，因此令“正反反正”、“反正正反”、“正反正反”分别为1、2、3，其余情况重来。另一种更妙的办法是，投掷三次硬币，“正反反”为1，“反正反”为2，“反反正”为3，其余情况重来。

# 23. 一排硬币
- 30枚面值不全相同的硬币摆成一排，甲、乙两个人轮流选择这排硬币的其中一端，并取走最外边的那枚硬币。如果你先取硬币，能保证得到的钱不会比对手少吗？
- 答案：
    - 先取者可以让自己总是取奇数位置上的硬币或者总是取偶数位置上的硬币。比如要是总是取奇数位置的话，那么取1，另一人只能取2或者30，这都是偶数位置，这时候根据另一人取的位置，又会暴露出一个奇数位置...
    - 数一数是奇数位置上的面值总和多还是偶数位置上的面值总和多，然后总是取这些位置上的硬币就可以了。

# 24. 环形加油站问题
-  一个环形轨道上有n个加油站，所有加油站的油量总和正好够车跑一圈。证明，总能找到其中一个加油站，使得初始时油箱为空的汽车从这里出发，能够顺利环行一圈回到起点。
-  答案：
    -  总存在一个加油站，仅用它的油就足够跑到下一个加油站（否则所有加油站的油量加起来将不够全程）。把下一个加油站的所有油都提前搬到这个加油站来，并把油已被搬走的加油站无视掉。在剩下的加油站中继续寻找油量足以到达下个加油站的地方，不断合并加油站，直到只剩一个加油站为止。显然从这里出发就能顺利跑完全程。
    - 另一种证明方法：先让汽车油箱里装好足够多的油，随便从哪个加油站出发试跑一圈。车每到一个加油站时，记录此时油箱里剩下的油量，然后把那个加油站的油全部装上。试跑完一圈后，检查刚才路上到哪个加油站时剩的油量最少，那么空着油箱从那里出发显然一定能跑完全程。

# 25 棋盘感染问题
- 考虑一个n*n的棋盘，把有公共边的两个格子叫做相邻的格子。初始时，有些格子里有病毒。每一秒钟后，只要一个格子至少有两个相邻格子染上了病毒，那么他自己也会被感染。为了让所有的格子都被感染，初始时最少需要有几个带病毒的格子？给出一种方案并证明最优性。
- 答案：至少要n个，比如一条对角线上的n个格子。n个格子也是必需的。当一个新的格子被感染后，全体被感染的格子所组成的图形的周长将减少0个、2个或4个单位（具体减少了多少要看它周围被感染的格子有多少个）。又因为当所有格子都被感染后，图形的周长为4n，因此初始时至少要有n个被感染的格子。

# 参考
https://blog.csdn.net/bertdai/article/details/78070092

lee-romantic 's Blog

导航

最近发表

友情链接