面试概率题

1、一根木棒，截成三截，组成三角形的概率是多少？

设第一段截 x，第二段截 y，第三段 1 - x - y。

考虑所有可能的截法。可能的截法中必须保证三条边都是正数且小于原来边长，则有 0

画图可知，(x, y) 必须在单位正方形的左下角的半个直角三角形里，面积为 1 / 2。

然后考虑能形成三角形的截法。首先要满足刚才的三个条件：

0

0

0 <1 - x - y <1

然后必须符合三角形的边的要求，即两边之和大于第三边：

x + y > 1 - x - y

x + 1 - x - y > y

y + 1 - x - y > x

化简即得：

0

0

1/2

画图可知，此时 (x, y) 必须在边长为 1/2 的三角形的右上角的半个直角三角形里，面积为 1/8。于是最终概率为 (1/8) / (1/2) = 1/4。

2、有一苹果，两个人抛硬币来决定谁吃这个苹果，先抛到正面者吃。问先抛这吃到苹果的概率是多少？

题目一看似乎答案就是 1/2，但其实认真细想并不是这么回事。

给所有的抛硬币操作从 1 开始编号，显然先手者只可能在奇数（1，3，5，7…）次抛硬币得到苹果，而后手只可能在偶数次（2，4，6，8…）抛硬币得到苹果。

设先手者得到苹果的概率为 p，第 1 次抛硬币得到苹果的概率为 p = 1/2，在第 3 次（3，5，7…）以后得到苹果的概率为 p/4（这是因为这种只有在第1次和第2次抛硬币都没有抛到正面，概率为 1/4 = 1/2 * 1/2 的时候才有可能发生，而且此时先手者此刻面临和开始相同的局面）；所以可以列出等式 p = 1/2 + p /4，p = 2/3（注意 p 表示先手者得到苹果的概率）。

3、一个三角形， 三个端点上有三只蚂蚁，蚂蚁可以绕任意边走，问蚂蚁不相撞的概率是多少？

乍一看好像和三角形三边长度有关系，事实上是无关的。

首先，每个蚂蚁在方向的选择上有且只有 2 种可能，共有 3 只蚂蚁，所以共有 2 的 3 次方种可能，而不相撞有有 2 种可能，即全为顺时针方向或全为逆时针方向。

不相撞概率 = 不相撞 / 全部 = 2/8 = 1/4。

4、扔筛子游戏

问题描述： 商家发明一种扔筛子游戏，顾客扔到多少点就得到多少钱，但扔筛子之前顾客需要付一定数量的钱 x，假设商家和顾客都足够聪明（1）顾客付一次钱可以扔一次的情况下，顾客能接受的最大 x 是多少（2）现在规则改为顾客付一次钱可以扔两次，顾客扔了第一次之后可以选择是否继续扔第二次，如果扔了第二次则以第二次的结果为准，如果没有扔第二次就以第一次的结果为准，这时顾客能接受的最大 x 为多少。

第一问：可以直接算顾客收益的期望为 1/6 (1 + 2 + 3 + 4 + 5 + 6) = 3.5，顾客能接受的最大 x 就是他收益的期望值。

第二问：考虑顾客什么情况下会扔第二次，就是扔第二次得到钱变多的概率相对较大的时候，那么当顾客第一次扔到 1，2，3 的时候他会选择继续扔第二次，则这时候期望变为 1/6 (4 + 5 + 6) + 1/2 (1/6 (1 + 2 + 3 + 4 + 5 + 6)) = 4.25

5、已知一随机发生器，产生 0 的概率是 p，产生 1 的概率是 1-p，现在要你构造一个发生器，使得它产生 0 和 1 的概率均为 1/2（随机数生成）

由题目有： 0 : p 1 : 1 - p

连续产生两个数，其组合以及概率如下：

00 : p2 01 : p(1 - p) 10 : (1 - p) p 11 : (1 - p)(1 - p)

可以发现 01 和 10 组合的概率是相等的，只需要将其分别映射到 0 和 1 即可。

即每次随机产生两个数，如果组合为00或11则丢弃，若为 01 则映射到 1，若为 10 则映射到 0，这样一来产生 0 和 1 的概率均为 1 / 2 。

6、已知一随机发生器，产生的数字的分布不清楚，现在要你构造一个发生器，使得它产生 0 和 1 的概率均为 1/2（随机数生成）

使用该随机发生器产生随机数 a，b，有以下 3 种情况：

1. a
2. a == b
3. a > b

其中情况（1）和（3）是对称的，发生的概率相等，只需要将这两种情况分别映射到 0 和 1 即可，其中遇到 a == b 时忽略。

7、已知有个 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。

参考：https://zhuanlan.zhihu.com/p/46592195