在知乎上看到这么一道题, 原题描述的不太严谨, 其大意是:一幢 200 层的大楼,给你两个鸡蛋. 如果在第 n 层扔下鸡蛋,鸡蛋不碎,那么从前 n-1 层扔鸡蛋都不碎.
这两只鸡蛋一模一样,不碎的话可以扔无数次. 已知鸡蛋在0层扔不会碎.提出一个策略, 要保证能测出鸡蛋恰好会碎的楼层, 并使此策略在最坏情况下所扔次数最少.一看, 答案里票数多的都是扯淡的, 正解都没给详细说明所以被压下去了.面试Hulu的最后一轮,
是我现在的manager zhibing来面试, 他只问了我这一个问题.
不过把200层换成了100层, 把鸡蛋换成了瓶子(瓶子更科学!).首先搞清楚这题的意思:
第一个瓶子用来试探, 只要它从 $k$ 层楼扔下去没碎, 则目标就在$[k + 1, 100]$之间了.
但一旦运气不好碎了, 对于已知的区间, 我们只能用剩下一个瓶子从小到大一层层试,
因为我们要保证策略必须成功, 不能冒险了.面试时我得到的题目描述也不太严谨, 没有说"最坏情况下代价最小", 因此我愚昧了一会才明白这题的意思."最坏情况下代价最小"这句话十分重要, 它已经反映了题目的数学结构:我们如果把任何一种策略看成一个决策树,
每一次扔瓶子都会有两个子节点, 对应碎与不碎的情况下下一步应该扔的楼层.
那么, 策略的一次执行, 是树中的一条从根往下走的路,
当且仅当这条路上出现过形如 $k$ 没碎 与
...
继续阅读
(75)