面试常问智力题

1. 赛马次数

有 25 匹马和 5 条赛道，赛马过程无法进行计时，只能知道相对快慢。问最少需要几场赛马可以知道前 3 名。

1. 先把 25 匹马分成 5 组，进行 5 场赛马，得到每组的排名。
2. 再将每组的第 1 名选出，进行 1 场赛马，按照这场的排名将 5 组先后标为 A、B、C、D、E。
3. 可以知道，A 组的第 1 名就是所有 25 匹马的第 1 名。而第 2、3 名只可能在 A 组的 2、3 名，B 组的第 1、2 名，和 C 组的第 1 名，总共 5 匹马，让这 5 匹马再进行 1 场赛马，前两名就是第 2、3 名。
4. 所以总共是 5+1+1=7 场赛马。

A 组：1，2，3，4，5
B 组：1，2，3，4，5
C 组：1，2，3，4，5
D 组：1，2，3，4，5
E 组：1，2，3，4，5

2. 用绳子计时 15 分钟

给定两条绳子，每条绳子烧完正好一个小时，并且绳子是不均匀的。问要怎么准确测量 15 分钟。

1. 点燃第一条绳子 R1 两头的同时，点燃第二条绳子 R2 的一头；
2. 当 R1 烧完，正好过去 30 分钟，而 R2 还可以再烧 30 分钟；
3. 点燃 R2 的另一头，15 分钟后，R2 将全部烧完。

3. 九球称重

有 9 个球，其中 8 个球质量相同，有 1 个球比较重。要求用 2 次天平，找出比较重的那个球。

1. 将这些球均分成 3 个一组，共 3 组，选出 2 组称重，
2. 如果 1 组比较重，那么重球在比较重的那 1 组；如果 1 组重量相等，那么重球在另外 1 组。
3. 对比较重的那 1 组的 3 个球再分成 3 组，重复上面的步骤。

4. 药丸称重

有 20 瓶药丸，其中 19 瓶药丸质量相同为 1 克，剩下一瓶药丸质量为 1.1 克。瓶子中有无数个药丸。要求用一次天平找出药丸质量 1.1 克的药瓶。

可以从药丸的数量上来制造差异：从第 i 瓶药丸中取出 i 个药丸，然后一起称重。可以知道，如果第 i 瓶药丸重 1.1 克/粒，那么称重结果就会比正常情况下重 0.1 * i 克。

5. 得到 4 升的水

有两个杯子，容量分别为 5 升和 3 升，水的供应不断。问怎么用这两个杯子得到 4 升的水。

可以理解为用若干个 5 和 3 做减法得到 4。

• 不能从 3 做减法得到 4，那么只能从 5 做减法得到 4，即最后一个运算应该为 5 - 1 = 4，此时问题转换为得到 1 升的水；
• 1 升的水可以由 3 做减法得到，3 - 2 = 1，此时问题转换为得到 2 升的水；
• 5 - 3 = 2。

所以：

1. 将3升的装满倒入5升的；
2. 再一次将3升的转满，倒入5升的，把5升装满；
3. 3 升杯里剩下的就是1升水；
4. 倒掉5升的，把1升水倒入5升杯；
5. 第三次加满3升杯，倒入5升杯，得到4升水。

6. 扔鸡蛋

一栋楼有 100 层，在第 N 层或者更高扔鸡蛋会破，而第 N 层往下则不会。给 2 个鸡蛋，求 N，要求最差的情况下扔鸡蛋的次数最少。

• 可以将楼层划分成多个区间，第一个鸡蛋 E1 用来确定 N 属于哪个区间，第二个鸡蛋 E2 按顺序遍历该区间找到 N。那么问题就转换为怎么划分区间满足最坏情况下扔鸡蛋次数最少。
• E1 需要从第一个区间开始遍历到最后一个区间。如果按等大小的方式划分区间，即 E2 的遍历次数固定。那么最坏的情况是 N 在最后一个区间，此时 E1 遍历的次数最多。为了使最坏情况下 E1 和 E2 总共遍历的次数比较少，那么后面的区间大小要比前面的区间更小。
• 具体来说，E1 每多遍历一次，E2 要少遍历一次，才使得 N 无论在哪个区间，总共遍历的次数一样。设第一个区间大小为 X，那么第二个区间的大小为 X-1，以此类推。那么 X + (X-1) + (X-2) + … + 1 = 100，得到 X (X + 1) / 2 = 100 ，即 X = 14。

7. 砝码秤盐

140g 盐,一天平,7g 、2g 砝码各一个,如何只利用这些东西 3 次把盐分成 50g 和 90g ?

• 第一次： 7g、2g砝码称出 9g 盐，结果盐分成 9g 与 131g
• 第二次：将 9g 盐与 7g、2g 都作为砝码，结果将盐分为 18g 与 113g （注意：这时盐已经分为三份：9g、18g、113g，还有两个砝码）
• 第三次：将 18g 盐与 7g 砝码发在左托盘，将2g砝码放在右托盘，然后在 113g 盐中取盐添置右托盘中，可获取 23g 盐。
  这时盐分为9g，18g，23g与90g。

即三次，可以得到90g与（9+18+23）50g。

8. 拿到最后一本书（腾讯）

100本书，两个人轮流拿，每次拿1~5本，你先拿，有没有啥策略可以保证你可以拿到最后一本？

1. 要想拿到最后的书，则最后要剩下6本，则前面要拿94本书，这样无论对方怎么拿，我都能拿到最后的书
2. 对方每次拿1-5 之前的N本书，所以我可以每次拿6-N本，保证我俩每次拿的书之和相加 = 6
3. 94/6 取余 = 4，所以要先拿 $4$ 本，其余的只要保证相加为6就行了

9. 裁绳子 2 刀形成三角形的概率

一段绳子，裁两刀，变成3段，可以拼成一个三角形的概率有多大

设线段长度为a，任意分成三段长分别为x，y和 a-x-y ，显然有 x>0，y>0，a-x-y>0，将这三个约束条件画到(x,y)二维平面坐标系上，这三条直线围成了一个直角三角形即为可行域（图1），其面积为 $(1/2)a^2$。

而这三段长能构成三角形的条件是：任意两边之和大于第三边，也就是下面三个不等式得同时成立：

$x+y>a-x-y(x+y>a/2)$
$x+a-x-y>y(y<a/2)$
$y+a-x-y>x(x<a/2)$

我们把上面三个不等式也画在平面直角坐标系中，可以看到可行域为图 2 中绿色的小三角形，其面积为:$(1/8)a^2$ ，占整个三角形的1/4。

故此三段能构成三角形的概率为 1/4。

10. 抛硬币，先抛到正面获胜

两个人玩抛硬币的游戏，谁先抛到正面就获胜。那么先抛的人获胜概率为

$2/3$

第一次：正
第三次：反反正
第五次：反反反反正
…第N次：反反。。。。正

$$p=1/2+(1/2{)}^3+(1/2{)}^5+\cdot \cdot \cdot \cdot \cdot \cdot +（1/2{）}^{(2n+1)}$$

$$=1/2\ast (1+1/4+(1/4{)}^2+\dots \dots +(1/4{)}^n)$$

当公比不为1时，等比数列的求和公式为：

$$Sn=[a1(1-q^n)]/(1-q)$$

对于一个无穷递降数列，数列的公比小于1,当上式得n趋向于正无穷大时，分子括号中的值趋近于1，取极限即得无穷递减数列求和公式

$$S=a1/(1-q)$$

所以:
$$S=\frac{\frac{1}{2}}{1-\frac{1}{2^2}}=\frac{2}{3}$$

11. 1-100的灯最后关的灯的编号

对一批编号为1-100，全部开关开着的灯进行以下操作：凡是1的倍数反方向拨一次开关；2的倍数 方向又拨一次开关；3的倍数反方向又拨一次开关……问：最后为关状态的灯的编号是哪些

def setSwitch(temp, i):
    if (temp[i] == 0):
        temp[i] = 1
    elif (temp[i] == 1):
        temp[i] = 0

def light_list():
    light = [0] * 100
    for i in range(100):
        for n in range(1, 101):
            if ((i + 1) % n == 0):
                setSwitch(light, i)

    sum = 0
    print("亮着的灯：")
    for i in range(100):
        if (light[i] == 1):
            sum += 1
            print(i, end=" ")
    print("")
    print("亮着的灯总共：", sum)

if __name__ == '__main__':
    light_list()

输出：

亮着的灯：
0 3 8 15 24 35 48 63 80 99 
亮着的灯总共： 10

那么关着的灯就容易得到了

12. n个人中至少有两个人生日相同的概率

把问题转换成 “计算完全没有相同生日的概率A(n)”，再用 $1$ 减去这个概率即可求出至少两个人生日相同的概率 $P(n)$。

分析：
第1个人的生日是随意的，有365种可能，概率是365/365＝1；
第2个人的生日不能与第1个人相同，只有365－1＝364种可能，概率是364/365；
第3个人的生日不能与前面2人相同，只有365－2＝363种可能，概率是363/365；……；
……
第n个人的生日不能与前面n-1人相同，只有365－(n-1)＝365-n+1种可能，概率是(365-n+1)/365.
完全没有相同生日的概率：
$$A(n)=365/365\ast 364/365\ast 363/365\ast \dots \dots \ast (365-n+1)/365$$

因此至少两人生日相同的概率： P(n)=1-A(n)
如果用n表示人数，p(n)表示n人中至少2人生日相同的概率，计算得到：
p(5)＝0.03
p(10)＝0.12
p(15)＝0.25 　
p(20)＝0.41
p(25)＝0.57
p(30)＝0.71
p(35)＝0.81 　
p(40)＝0.89
p(45)＝0.94
p(50)＝0.97
p(55)＝0.99
可以看出，当人数超过55人时，至少2人生日相同的概率就会超过99%。所以，如果一个班的学生超过55人，几乎可以肯定地说，一定有2人的生日相同。

13. 怎样估算上海市理发师的数量？

参考：
【面试官手记】数量估算类面试题应该如何应对？

14. 一个孩子是女孩的情况下，另一个孩子也是女孩的概率

其实题目应该是，在至少一个为女孩的情况下，两个都为女孩的概率是多少。这样描述比较容易想清楚

答案： 1 / 3

$$P(女|女)=P(女女)/P(女)$$

夫妻有两个小孩，则样本空间为 女女，男女，女男，男男，则
$$P(女女)=1/4$$

$$P（女）=1-P(男男)=3/4$$

所以最后1/3。(条件概率)主要是大家条件概率下面那个P（女）没弄对吧，是有一个是女孩的概率条件下。

（简单版本：第一个为女一共就 3 种可能，女女、女男、男女；
已知一个为女的 第二个也为女的概率为三分之一）

参考：

1. 面试常问智力题
2. (牛客热帖) 概率论面经汇总(持续更新)