※ 引述《bleed1979 (十三)》之铭言：
: ※ [本文转录自 Soft_Job 看板 #1JI2zrVk ]
: 作者: bleed1979 (十三) 看板: Soft_Job
: 标题: [讨论] Google面试问题
: 时间: Sat Apr 12 02:07:46 2014
: 问题：
: 假设你有两颗蛋，然后有一栋100层楼高的大楼。
: 而蛋的特性有的可能很坚固，坚固到从一百层楼跌下都没事，
: 有的可能很脆弱，一楼就可以摔破。
: 现在你只知道这这两颗蛋是完全相同的，
: 你想要知道蛋最高从哪一层楼摔下来不会摔破。
: 问题是：你要摔几次才能计算出来？
: （如果你低于高度摔下蛋，蛋就没事，如果高于那个楼层，蛋就完蛋）
: 在这过程你可以摔破蛋。
先假设蛋的硬度是uniform distribution
以100层来说，我们分成1~101级
1级表示1楼摔下来就破
100级表示100楼摔下来破
101级表示100楼摔下来也不破
所以我们有101个级距，uniform distributed
你可以挑战这个假设，例如使用normal distribution
或是增加级数，例如200个级距，但101级后就只能确定属于100层
但我们先讨论最简单的case
1. 在此假设下，我们从n楼丢下，蛋破的机率是 n/101
延伸此假设，在最高m楼的情况下，从n楼将蛋丢下
蛋破的机率是 n/(m+1)
2. 假设蛋在x楼破了，我们就被迫从1楼开始丢起
此时的期望值为 g(x) = (x*x + x - 2)/ 2x
我们先假设x是6 (从第6层丢下结果破了)
可能的情况有
1破 => 1次
2破 => 2次
3破 => 3次
4破 => 4次
5破 => 5次
5不破6破 => 5次
每种情况的机率是 1/6
(1+2+3+4+5+5)/6 = 20/6 = g(6)
3. 假设蛋在x楼丢下不破
等于是变成 x+1楼 ~ m楼的问题
问题可以转化成 1楼 ~ m-x楼的问题
总共 m - x + 1 个级距 (包括m-x楼不破)
3. 综合(1) (2) (3)
在最高m楼的情况下，将二颗蛋从n楼丢下次数的问题
可以看成是 蛋破的机率 * 一颗蛋在最高n楼丢下次数的问题
+ 蛋不破的机率 * 二颗蛋从n+1楼~m楼丢下次数的问题
f(n, m) = n/(m+1) * g(n) + (1-n/(m+1)) * f(m-n, k) + 1
(记得加一，已经丢一次了)
新变量k表示第二次从k楼丢下
f(n, 100) = n/(101) * g(n) + (1-n/101) * f(100-n, k) + 1
4. f'(m)表示f(n, m)值域的min (我们要求的)
f'(1) = 1
f'(2) = 5/3
照这样一路求到f'(100)