【直观算法】Egg Puzzle 鸡蛋难题 | Go Further | Stay Hungry, Stay Foolish

【直观算法】Egg Puzzle 鸡蛋难题

2018-10-11 1738

【阅读时间】10000+字 | 17 - 22 min
【阅读内容】Google面试题：100层楼，两个鸡蛋最少用多少次能测出鸡蛋的会在哪一层碎

1. 题目描述

有栋楼高100层，一个鸡蛋从第x层以上( $>$ )的楼层落下来会摔碎，在第x层和以下( $\leqslant$ )的楼层落下不会摔碎。给你2个鸡蛋，设计方案找出x，保证在最坏情况下， 最小扔鸡蛋尝试的次数

有时候仍的东西会变，比如瓶子

这道题目的整个解答过程涉及给类逻辑思维，工程思维，当真是一道海纳百川的面试题，也难怪Goolge会以这道题做了多年的试金石

1.1 求什么？

利用抽象思维，符号化题目描述

⭐️〔题目要求〕找到 $x$ 层落下不会碎， $x+1$ 层落下会碎的临界层所需要的最少尝试次数 $r$ (r for result)

2. 解题思路

使用等价思维，如何计算出最小的尝试次数？使用函数方法表示为：如何计算出这个结果，找出公式 $r = f()$

2.1 一个鸡蛋

假设最后结果设为 $r$ 次（r for result）。使用归纳思维，先看只拥有1个鸡蛋的情况，思考什么是最坏情况。你可能说可以直接使用二分法，请注意，只有1个鸡蛋，必须保证找到临界层。所以，1个鸡蛋的情况下，最坏情况为 $r = 100$ （楼高）

大多数情况下，我们都低估了理解题意的重要性

这么思考还不够究竟，缺乏抽象思维

通过逻辑思考，可得 $r =100$ ，但有没有一个抽象的公式化结论？或者说，如何通过一个公式算出 $r$ ？接下来就来解决这个问题

假设临界层分别为 $x = 1,2,3 \dots 100$ ，因为你只有1个鸡蛋，不知道会在哪层碎，所以唯一策略是从1层开始一层一层试，对应的每个策略都有一个尝试步数（比如 $x = 95$ ，从1层开始尝试为95次），可得到临界层 $x$ 在所有可能取值下对应的 $r = 1,2,3 \dots 99,100$ ，最终选择最坏情况，即 $r = 100$

可抽象化得到待求的符号表达式
$r = \max_{1 \leqslant x \leqslant N}(\forall S_i(x)) \tag{1}$
公式的语言型描述是：对于每一个可能的临界层 $x$ ，得到使用可选择策略 $S_i()$ 需要的尝试步数。在每一轮 $x$ 的遍历中，取最大值（即最坏情况），为 $r$ 。无论临界层 $x$ 在哪一层，只有一个鸡蛋的情况下，总需考虑最坏情况

Read full article from 【直观算法】Egg Puzzle 鸡蛋难题 | Go Further | Stay Hungry, Stay Foolish