×

We use cookies to help make LingQ better. By visiting the site, you agree to our cookie policy.

image

李永乐老师 Youtube, 复工复产找工作？先来看看这道面试题：双蛋问题

复工 复产 找 工作 ？先 来 看看 这道 面试题 ：双蛋 问题

各位 同学 大家 好 我 是 李永乐 老师 有 一个 小朋友 跟 我 说 他 年底 的 时候 刚刚 把 工作 辞 了 准备 过 完年 找 工作 结果 就 来 了 疫情 那 现在 复工 复产 的 节奏 越来越近 了 他 就 开始 着手 准备 找 工作 的 事 了 他 最近 发现 了 一个 面试题 据说 是 微软 还是 Google 的 一个 面试题 挺 有意思 的 想 让 我 讲 一 讲 那 今天 咱们 就 一 起来 讨论一下 这个 面试题 我们 称之为 双蛋 问题 鸡蛋 的 蛋 双蛋 问题 实际上 是 一个 计算机 的 问题 这个 问题 是 这样 描述 的 说 有 一个 大楼 这个 大楼 非常 高 这 大楼 一共 有 100 层 那么 高 这 100 层楼 1 2 3 4 ... 一直 到 100 层 然后 有 一个 鸡蛋 这个 鸡蛋 特别 神勇 它 在 低 楼层 往下 扔 的 时候 到 地上 都 不会 碎 在 高 楼层 往下 扔 的 时候 到 地面 上 才 会 碎 而 中间 有 一个 临界 的 楼层 这个 临界 的 楼层 以下 不管 你 在 临近 楼层 以下 扔 多少次 鸡蛋 都 是 不碎 的 然后 如果 你 超过 了 这个 临界 楼层 往下 扔 这回 鸡蛋 才 碎 碎 了 之后 就 不能 再 反复 用 了 现在 我 就 问 你 这个 人 如果 要是 一共 有 N 个 蛋 可以 用来 做 检测 注意 如果 这个 蛋 没有 碎 就 还 可以 接着 扔 如果 这个 蛋碎 了 就 不能 再用 了 如果 有 N 个 蛋 的话 那么 他 最少 要 扔 多少次 这个 次数 叫 M 才能 找出 这个 临界 的 楼层 找出 这个 临界 的 楼层 就是 这一 楼层 以上 就 都 会 碎 这个 楼层 以下 就 都 不碎 这个 就是 扔 鸡蛋 的 问题 那么 这个 扔 鸡蛋 的 问题 你 有 多少 个 鸡蛋 会 影响 到 这个 问题 的 答案 对 吧 首先 我们 先 来 分析 最 简单 的 情况 如果 这个 人 他 只有 一个 蛋 如果 只有 一个 蛋 也 就是 N 等于 1 那 我 就 问 你 最少 得 扔 多少次 才能 确定 出 临界 楼层 大家 注意 这个 确定 出 临界 楼层 的 意思 是 你 即使 是 最坏 的 情况 下 也 能够 通过 扔 这么 多次 鸡蛋 就 确定 出 这个 楼层 对 吧 比如说 你 只有 一个 鸡蛋 的话 你 不 可能 上来 就 从 50 层 开始 扔 那 一旦 要是 碎 了 你 只能 知道 这个 临界 楼层 在 1 到 50 之间 但是 你 却 不 知道 是 哪 一个 对 吧 所以 如果 你 只有 一个 鸡蛋 的话 没有 别的 办法 你 只能 是 先 在 第一层 扔 如果 碎 了 那 就是 一层 如果 不碎 就 从 第二层 扔 第二层 碎 了 就是 二层 不碎 他 就 再 从 第三层 扔 一个 一个 地往 上试 这样一来 你 没有 别的 好 方法 了 对 吧 所以 一层 一层 去试 最差 的 情况 是 到 100 层碎 了 或者 到 100 层 也 不碎 因此 你 最差 的 情况 下要 扔 100 次 那 这个 就是 扔 的 次数 比较 多 了 因为 它 鸡蛋 太少 了 他 只有 一个 蛋 好 了 那么 假如 说 这个 人 的 蛋 比较 多 他 有 无限 多个 蛋 他 有 无限 个 蛋 那 这回 需要 扔 多少次 呢 这时候 我们 就要 采用 计算机 里边 一种 常用 的 方法 了 那 就是 二分法 是 吧 二分法 也 是 牛顿 最早 提出 来 的 但 当时 是 用来 去 找 一个 方程 的 根 的 这个 研究 起来 也 很 容易 就是说 我们 把 1 到 100 是 吧 1 到 100 层 我们 画 在 一个 数轴 上 然后 我们 第一个 鸡蛋 我 在 50 层 的 地方 扔 如果 这个 鸡蛋 要是 碎 了 那 就 说明 临界 楼层 一定 是 在 1 到 50 之间 对 吧 如果 50 层 这个 鸡蛋 它 不碎 那 就 说明 临界 楼层 应该 是 在 50 到 100 层 之间 这 就是 第一个 鸡蛋 的 扔 法 那么 如果说 你 确定 了 它 在 1 到 50 之间 碎 了 那 于是 我们 可以 第二个 鸡蛋 在 25 层 的 地方 扔 如果 碎 了 说明 临界 楼层 在 这 如果 不碎 说明 临界 楼层 在 这 这样一来 我 每 扔 一个 鸡蛋 都 可以 把 这个 间隔 除以 2 对 不 对 所以 叫 二分法 那 我们 知道 你 除了 几次 2 之后 最后 如果 间隔 小于 1 了 就 不用 再 去 试 了 对 不 对 因此 如果 我们 想 把 它 确定 出来 是 哪 一个 的话 我们 就 需要 扔 的 次数 2ᴹ 它 得 大于 等于 100 最后 M 就 大于 等于 log₂¹⁰⁰ 我们 试一试 也 能 试出来 这个 数 应该 是 6.64 6.64 我们 就 取 7 好 了 所以 这个 时候 你 需要 扔 7 次 在 最坏 的 情况 下 你 也 需要 扔 7 次 好 这是 这个 人有 无限 个 蛋 的 时候 是 这个 样子 的 那么 这个 面试题 一般 是 这么 问 的 如果 这个 人有 两个 蛋 的话 那么 他 要 扔 多少次 才能 保证 一定 把 这个 临界 楼层 找 出来 所以 就 叫 双蛋 问题 所以 他 如果 有 两个 蛋 那么 这个 时候 怎么样 呢 叫 N 等于 2 我们 来看 一下 这个 情况 我们 先想 这样 一个 方法 如果 第一个 蛋 某些 原因 下 它 碎 了 那 我 就 只 剩下 一个 蛋 了 剩下 一个 蛋 之后 我 只能 一个 层 一层 一层 一层 这样 往 上试 了 就 回到 第一种 情况 了 对 吧 所以 我 第一个 蛋 的 作用 应该 是 用来 把 这个 范围 尽量 的 缩小 然后 用 第二个 蛋 一个 一个 的 去 试 只能 是 这样 吧 好 那 我们 还是 把 这个 图画 出来 说 有 这个 1 到 100 层 对 不 对 然后 我 有 两个 蛋 A 和 B 我们 先 让 A 这个 鸡蛋 怎么 做 呢 我 先 让 A 这个 鸡蛋 第一次 扔 我 让 它 在 10 层楼 往下 扔 它 如果 要是 碎 了 就 说明 临界 楼层 在 1 到 10 之间 对 吧 如果 不碎 我 就让 它 在 20 层 的 地方 扔 如果 碎 了 在 这 如果 不碎 就 在 30 层 的 地方 扔 也就是说 我 可以 让 A 这个 蛋 它 在 10 20 30 ... 一直 到 100 这些 个 楼层 扔 A 最多 可以 扔 10 次 对 吧 好 如果 我 把 A 这个 确定 了 比如说 在 10 层 的 时候 没碎 在 20 层 的 时候 碎 了 那 就 说明 临界 楼层 在 这 然后 我用 第二个 鸡蛋 再 去 试 11 12 13 14 15 16 ... 一直 到 19 对 不 对 所以 B 这个 鸡蛋 它 扔 的 楼层 就是 x1 x2 x3 ... 一直 到 x9 好 通过 这样 的 方法 我 就 一定 能够 把 这个 楼层 给 试出来 对 吧 临界 楼层 给 试出来 那 咱们 想一想 最多会 扔 多少次 呢 假如 说 A 在 第 10 层楼 的 地方 就 碎 了 那么 B 最多 是 9 次 总共 就是 扔 10 次 就 能 试出来 了 对 吧 好 如果 A 在 100 层 的 时候 才 碎 了 那么 A 扔 了 10 次 然后 我 B 再 去 试 结果 试到 最后 一个 才 碎 那 就 说明 你 在 99 层 或者 100 层碎 了 此时 我们 就要 扔 19 次 对 不 对 所以 最坏 的 情况 下 我们 需要 扔 19 次 好 扔 19 次 咱们 思考 一下 还有 没有 一种 方法 能够 比 这个 方法 更好 呢 这个 方法 它 有 的 时候 是 10 次 有 的 时候 是 19 次 在 10~19 之间 它 不 平均 原因 是 什么 呢 原因 是因为 A 它 确定 的 间隔 是 等 间隔 的 等 间隔 的 就 造成 B 这个 鸡蛋 去试 的 时候 每 一次 扔 的 次数 最多 都 是 一样 的 对 吧 但是 如果 这个 临界 楼层 靠 后 的话 A 扔 的 次数 就 多 了 是不是 所以 我们 在 思考 能 不能 让 这个 间隔 变得 不等 我们 让 间隔 变得 不等 就是说 让 A 每多 扔 一次 B 的 这个 间隔 就 缩小 一点 A 扔 一次 B 就 间隔 缩小 一点 这样一来 让 它 总 次数 能够 平均 一下 也许 这种 情况 会 更好 对 不 对 好 咱们 再 来看 一个 方法 我们 换 一种 方法 如果 我 让 这个 间隔 还是 1 到 100 是 吧 但是 间隔 不 一样 我 A 鸡蛋 第一次 扔 的 时候 呢 我 让 它 的 间隔 是 n 层 然后 如果 它 不碎 第二次 扔 的 时候 我 让 这个 间隔 是 n-1 层 第三次 扔 的 时候 我 让 这个 间隔 是 n-2 层 直到 最后 一次 扔 的 时候 呢 我 让 这个 间隔 是 1 层 也 就是 A 每多 扔 一次 它 的 间隔 就 小 了 一点 这样一来 B 所 需要 检验 的 次数 就会少 1 A 多 扔 一次 B 就 少 扔 一次 这样一来 总 次数 不 就 平均 了 一些 吗 也许 这种 方法 会 更好 咱们 思考 一下 假如 按照 这种 方法 的话 我们 算一算 这个 n 应该 得 几 这个 并 不难 就是 1+2+3+ ... 一直 加 加到 n 它 的 最后 我们 都 知道 用 高斯 公式 它 应该 等于 n(n+1)/2 对 吧 那么 这个 结果 它 必须 要 大于 等于 100 所以 我们 可以 计算 出 这个 n 来 这个 n 要 大于 等于 13.65 于是 我们 就 取 n 等于 14 n 等于 14 什么 意思 呢 就是说 我们 不 考虑 那种 加 1 减 1 的 临界 情况 了 就是说 A 鸡蛋 我们 这么 扔 第一次 我 让 它 跨越 14 个 间隔 也 就是 在 14 层楼 去 扔 14 层楼 如果 碎 了 就 说明 在 1~14 层 之间 然后 我用 B 鸡蛋 试 1 2 3 4 ... 一直 到 13 对 吧 如果 第一个 14 层 没碎 我 就让 它加 13 层 要 减 1 对 吧 加 13 14 加 13 27 层 如果 27 层不碎 我 就 再加 12 39 层 不碎 我 再加 11 是 50 层 不碎加 10 60 层 不碎加 9 69 层 然后 加 8 77 层 加 7 84 层 然后 加 6 是 90 层 加 5 95 层 加 4 99 层 加 1 100 层 最后 加不上 3 了 为什么 呢 因为 我 这个 实际上 是 13.65 你 取 了 个 14 自然而然 最后 它 就 会 差 了 一点点 好 那么 A 它 最 多 扔 多少次 1 2 3 4 5 6 7 8 9 10 11 12 A 最多 是 扔 12 次 那 如果 第一次 A 就 碎 了 那 我 就 需要 用 B 鸡蛋 去 检验 1~13 层 再 加上 A 扔 的 一次 一共 是 扔 了 14 次 如果 A 扔 到 27 层 的 时候 碎 了 那 我 B 就 需要 检验 15 层到 26 层 再 加上 A 扔 的 那 两次 最后 结果 还是 14 次 对 吧 那 当然 如果 A 扔 到 100 层碎 了 或者 是 100 层 还 没碎 的话 那 你 就 不 需要 用 B 去 检验 了 那 最少 的 是 12 次 于是 用 这种 方法 你 扔 鸡蛋 的 次数 是 在 12~14 之间 最差 的 情况 下 是 14 次 所以 这样 一看 你 看 两个 鸡蛋 的 情况 下 这 M 不是 19 最差 的 情况 下 我 只 需要 扔 14 次 就 能 保证 你 一定 能够 找到 那个 临界 的 楼层 了 对 吧 好 那 这个 面试题 其实 我们 就 说完 了 不过 咱们 想 如果 仅仅 是 这样 一个 问题 的话 其实 意义 并不大 你 能够 保证 这种 方法 就是 最好 的 吗 也 不见得 吧 而且 这个 人 一定 有 两个 蛋 不 一定 他 可能 有 3 个 蛋 4 个 蛋 5 个 蛋 6 个 蛋 ... 那么 如果 我们 的 蛋 数量 不是 2 的话 这个 问题 又 该 如何 去 解决 呢 所以 说 这道题 的 精髓 其实 在于 其他 的 情况 下 我们 需要 使用 递归 的 思想 来 进行 求解 其实 递归 思想 我们 在 之前 讲 汉诺塔 还有 拜占庭 将军 问题 的 时候 都 用到 过 但是 这个 递归 要 比 汉诺塔 那种 递归 稍微 复杂 一点 这个 思想 是 这样 的 我们 把 这个 问题 普遍化 一点 就 假如 说 这 一层楼 它 有 T 层 这个 楼有 T 层 然后 我们 一共 有 N 个 蛋 这个 时候 我们 要 找到 在 最 不利 的 情况 下 至少 要 扔 多少次 才能 一定 找到 这个 临界 楼层 这个 次数 叫 M 那么 M 自然 是 T 和 N 的 一个 函数 我 就 问 这个 函数 值 到底 应该 是 多少 对 吧 这个 问题 我们 首先 先 从 最 简单 的 情况 说起 首先 我们 画 一个 表格 这个 表格 呢 这个 表格 它 的 一列 表示 的 是 这个 楼层 数 T T 可以 是 1 2 3 或者 一直 到 100 是 吧 然后 蛋 的 数目 也 可以 是 1 2 3 4 或者 是 更 多 的 蛋 对 吧 好 的 现在 有 一些 情况 是 比较 好 填 的 比如说 吧 如果 你 只有 一个 鸡蛋 的话 你 有 一层楼 你 就 至少 得 扔 一次 对 不 对 你 有 两层楼 就 得 扔 两次 有 三层楼 就 得 扔 三次 所以 这 一列 是 非常 好 填 的 那么 如果 是 只有 一层楼 呢 只有 一层楼 的话 不管 你 有 几个 鸡蛋 都 只 需要 扔 一次 所以 这 一行 也 是 很 好 填 的 也就是说 这 两个 边界 其实 都 是 非常 非常 好 填 的 当然 后面 还有 我 就 没有 再往 下 写 这 两个 边界 很 好 填 关键 是 中间 这 一大堆 比如说 有 3 层楼 2 个 鸡蛋 你 至少 要 扔 几次 100 层楼 2 个 鸡蛋 你 要 扔 几次 5000 层楼 3 个 鸡蛋 你 要 扔 几次 所以 这个 问题 就 比较复杂 我们 怎么 去 研究 它 呢 我们 就要 使用 递归 的 思想 了 这个 思想 是 这样 的 不管 你 有 多少 个 鸡蛋 在 扔 的 时候 你 首先 必须 得选 一层 然后 扔 第一个 鸡蛋 对 不 对 好 那么 第一个 鸡蛋 扔 在 哪 呢 我们 其实 也 并 不 清楚 扔 在 哪 比如说 这个 楼层 是 1 到 T 这么 多层 第一个 鸡蛋 你 随便 给 我 找个 地方 叫 第 k 层 你 就 扔 吧 扔 完 了 之后 两种 结果 一种 是 碎 一种 是 不碎 如果 碎 就 说明 这个 临界 楼层 一定 在 前面 如果 不碎 就 说明 临界 楼层 一定 在 后面 对 不 对 好 那么 如果 碎 了 你 还 需要 扔 多少次 鸡蛋 才能 确定 这 k 个 楼层 里边 哪 一层 是 临界 楼层 呢 我们 可以 说 这个 数 其实 就是 M 什么 呀 k 层楼 N-1 个 蛋 为什么 呢 因为 你 第一个 鸡蛋 已经 碎 了 所以 你 的 蛋 只能 变成 N-1 个 了 而 楼层 原来 是 T 层 现在 你 已经 知道 不在 后面 只 在 前面 所以 楼层 变成 k 了 因此 你 会 有 这样 的 一个 数据 好 这 是 你 再 往后 还 需要 确定 多少次 再往 下 如果 它 不碎 的话 也 是 一样 的 此时 楼层 就 变成 了 这么 多层 这个 层数 应该 是 T-k 层 而 蛋 的 数目 还是 N 个 对 吧 于是 我们 可能 还 需要 找 这么 多次 才能 确定 具体 是 在 哪 一层 因为 我们 要 找 的 是 最 不利 的 情况 下 需要 扔 多少 层 所以 在 这 两种 可能 下 我们 要 把 它 取 一个 最大值 这 两种 可能 中 比较 大 的 那个 值 就是 我 第一个 鸡蛋 扔 到 k 层 的 时候 我 需要 数 的 个数 对 吧 最少 需要 数 这么 多次 但是 同时 你 不要 忘 了 你 开始 还 扔 了 一层 对 不 对 所以 你 还要 把 这个 数字 再 加上 一个 1 就 这 两个 数中 较大 那个 数再加 1 它 就 等于 什么 呢 它 就 等于 当 你 第一个 鸡蛋 扔 到 第 k 层时 如果 原来 你 有 T 层楼 和 N 个 鸡蛋 你 需要 扔 鸡蛋 的 个数 但是 你 第一个 这个 k 你 怎么 确定 呢 对 不 对 我们 的 一个 方法 就是 枚举 就是 把 k 等于 1 2 3 4 5 6 7... 一直 到 T 我 全数 一遍 我 再 画 一个 表格 这个 表格 是 我们 知道 你 这个 k 它 有 很 多种 可能 你 第一个 鸡蛋 可以 扔 在 第一层 你 也 可以 扔 到 第二层 可以 扔 第三层 一直 到 你 可以 扔 到 最后 一层 就是 第 T 层 那么 你 在 每 扔 一次 你 都 可以 做 这个 运算 对 不 对 找到 那种 最 不利 的 情况 下 你 需要 扔 鸡蛋 的 次数 Mᴋ 是 吧 所以 如果 你 第一个 鸡蛋 扔 到 第一层 了 就是 M₁ 扔 到 第二层 就 M₂ 扔 到 第三层 就 M₃ 一直 到 如果 第一个 鸡蛋 扔 到 T 层 了 那 就是 Mᴛ 对 不 对 好 第一个 鸡蛋 你 是 可以 选 的 你 可以 扔 在 任何 一层 所以 我 需要 在 这 里面 所有 的 值 中 我选 一个 最 什么 的 值 最小 的 值 所以 最终 的 结果 是 M 在 T 层楼 N 个 鸡蛋 的 情况 下 它 等于 最小值 M₁ M₂ ... 一直 到 Mᴛ 这样一来 我们 就 把 这个 数据 给 确定 了 有人 说 那 这个 运算 这么 复杂 我 到底 怎么 算 其实 很 简单 你 看 你 在 每 一次 计算 的 过程 中 不管 你 从 哪 一层楼 去 扔 你 都 要不然 是 把 这个 楼层 数给 减少 了 T 变成 k 了 或者 T 变成 T-k 了 要不然 就是 把 鸡蛋 的 个数 减少 了 或者 没有 减少 对 不 对 所以 我们 已经 知道 了 楼层 少 和 鸡蛋 少 的 时候 的 情况 我们 就 可以 一点一点 算 出 楼层 多 和 鸡蛋 多 的 情况 也就是说 我们 可以 先算 两层楼 两个 鸡蛋 的 时候 三层楼 两个 鸡蛋 的 时候 把 这 一列 都 算 完 然后 利用 这个 数据 我 再 去 算 三个 鸡蛋 的 时候 两层楼 如何 三层楼 如何 我 把 这 一列 也 算 完 然后 我 再 算 四个 鸡蛋 的 时候 这个 数 这个 数 分别 是 多 大 这样 一点一点 的 递归 就 把 这个 东西 给 弄出来 了 所以 大家 看 这个 思想 其实 还是 挺 复杂 的 对 吧 这是 一个 递归 的 这样 一个 思想 那么 既然 说 到 面试题 了 咱们 不妨 出 一个 简单 一点 的 面试题 给 大家 想一想 假如 有 一个 圆形 的 小岛 然后 有 一条 鳄鱼 在 圆形 小岛 周围 游弋 鳄鱼 的 速度 是 人 的 四倍 而且 鳄鱼 总是 希望 找到 一个 离 人 最近 的 位置 而 这个 人 最 开始 在 这个 小岛 的 正 中心 那么 我 问 这个 人该 如何 运动 才 能够 比 鳄鱼 先 到达 这个 岛 的 边缘 从而 逃离 这个 岛 呢 大家 如果 有 答案 的话 不妨 在 下方 留言 大家 如果 喜欢 我 的 视频 可以 在 YouTube 账号 李永乐 老师 里 订阅 我 点击 小 铃铛 可以 第一 时间 获得 更新 信息


复工 复产 找 工作 ？先 来 看看 这道 面试题 ：双蛋 问题 Returning to work and looking for a job? First, let's take a look at this interview question: double egg question

各位 同学 大家 好 我 是 李永乐 老师 Hello everyone, I'm Mr. Li! 有 一个 小朋友 跟 我 说 A friend told me 他 年底 的 时候 刚刚 把 工作 辞 了 that he left his job at the end of last year 准备 过 完年 找 工作 and was planning to find a new job after the Chinese New Year 结果 就 来 了 疫情 but the coronavirus stroke China at the beginning of 2020. 那 现在 复工 复产 的 节奏 越来越近 了 Now, as the economy is recovering back to the normal state, 他 就 开始 着手 准备 找 工作 的 事 了 he is starting to prepare for job interviews. 他 最近 发现 了 一个 面试题 He recently found an interview question. 据说 是 微软 还是 Google 的 一个 面试题 Allegedly, it's an interview question from Microsoft or Google. 挺 有意思 的 想 让 我 讲 一 讲 It is very interesting, and he wanted me to explain it. 那 今天 咱们 就 一 起来 讨论一下 这个 面试题 so today, let's talk about this interview question. 我们 称之为 双蛋 问题 鸡蛋 的 蛋 It is called the Two Eggs Problem. 双蛋 问题 实际上 是 一个 计算机 的 问题 Actually, this is a computer science problem. 这个 问题 是 这样 描述 的 Here is the question. 说 有 一个 大楼 There is a Skyscraper that has a total of 100 floors. 这个 大楼 非常 高 这 大楼 一共 有 100 层 那么 高 这 100 层楼 These 100 floors, 1 2 3 4 ... 一直 到 100 层 1, 2, 3, 4 ... to floor 100. 然后 有 一个 鸡蛋 这个 鸡蛋 特别 神勇 There is an egg being very strong. 它 在 低 楼层 往下 扔 的 时候 It won't break when falling from low floors. 到 地上 都 不会 碎 在 高 楼层 往下 扔 的 时候 到 地面 上 才 会 碎 It will only break when falling from high floors. 而 中间 有 一个 临界 的 楼层 There is a boundary floor between the top and the bottom floors. 这个 临界 的 楼层 以下 Below this boundary floor, 不管 你 在 临近 楼层 以下 扔 多少次 no matter how many times you drop the egg, 鸡蛋 都 是 不碎 的 the egg will not break. 然后 如果 你 超过 了 这个 临界 楼层 往下 扔 If you drop above the boundary floor 这回 鸡蛋 才 碎 the egg will break immediately, 碎 了 之后 就 不能 再 反复 用 了 and it cannot be reused after broken. 现在 我 就 问 你 Now the question is 这个 人 如果 要是 一共 有 N 个 蛋 可以 用来 做 检测 注意 如果 这个 蛋 没有 碎 就 还 可以 接着 扔 Notice that if an egg can be reused if not broken. 如果 这个 蛋碎 了 就 不能 再用 了 If it is broken, then you would have to use a new egg. 如果 有 N 个 蛋 的话 If there are N eggs, 那么 他 最少 要 扔 多少次 then what is the minimum number of drops, M, that is required to find the boundary floor? 这个 次数 叫 M 才能 找出 这个 临界 的 楼层 找出 这个 临界 的 楼层 就是 这一 楼层 以上 就 都 会 碎 Above this floor, all eggs break 这个 楼层 以下 就 都 不碎 Below this floor, no egg breaks 这个 就是 扔 鸡蛋 的 问题 This is a question about dropping eggs, 那么 这个 扔 鸡蛋 的 问题 so the number of eggs that you have will affect the answer. 你 有 多少 个 鸡蛋 会 影响 到 这个 问题 的 答案 对 吧 首先 我们 先 来 分析 最 简单 的 情况 Firstly, let's look at the simplest case 如果 这个 人 他 只有 一个 蛋 如果 只有 一个 蛋 If the person has only one egg, 也 就是 N 等于 1 N=1, 那 我 就 问 I would ask: 你 最少 得 扔 多少次 才能 确定 出 临界 楼层 What is the minimum number of drops required to find the boundary floor? 大家 注意 这个 确定 出 临界 楼层 的 意思 是 Notice that this is the minimum number of tests required even in the worst-case scenario. 你 即使 是 最坏 的 情况 下 也 能够 通过 扔 这么 多次 鸡蛋 就 确定 出 这个 楼层 对 吧 to find the boundary. 比如说 你 只有 一个 鸡蛋 的话 For example, if you have only one egg, 你 不 可能 上来 就 从 50 层 开始 扔 you cannot start it from the fifth floor. 那 一旦 要是 碎 了 If it breaks, 你 只能 知道 这个 临界 楼层 在 1 到 50 之间 then you only know the boundary floor is a floor between 1 and 50. 但是 你 却 不 知道 是 哪 一个 对 吧 所以 如果 你 只有 一个 鸡蛋 的话 So, if you have only one egg, 没有 别的 办法 你 只能 是 先 在 第一层 扔 and there is no other way, you could only drop it from the first floor 如果 碎 了 那 就是 一层 If it breaks, then the boundary is the first floor. 如果 不碎 就 从 第二层 扔 If it doesn't, then drop it again from the second floor. 第二层 碎 了 就是 二层 If it breaks, then it is on the second floor. 不碎 他 就 再 从 第三层 扔 if not, try the third floor. 一个 一个 地往 上试 Going up, floor-by-floor. 这样一来 你 没有 别的 好 方法 了 对 吧 Since you have no better way, you have to try each floor. 所以 一层 一层 去试 最差 的 情况 是 到 100 层碎 了 The worst case is that it breaks when it reaches floor 100. 或者 到 100 层 也 不碎 Or it doesn't break even from floor 100. 因此 你 最差 的 情况 下要 扔 100 次 Therefore, the worst case is 100 tests. 那 这个 就是 扔 的 次数 比较 多 了 This scenario has a very large number of tests because it has only one egg. 因为 它 鸡蛋 太少 了 他 只有 一个 蛋 好 了 那么 假如 说 这个 人 的 蛋 比较 多 Well, let's say that he has more eggs. 他 有 无限 多个 蛋 他 有 无限 个 蛋 An unlimited number of eggs. 那 这回 需要 扔 多少次 呢 This time, how many drops are required? 这时候 我们 就要 采用 Now we need to use an algorithm. 计算机 里边 一种 常用 的 方法 了 那 就是 二分法 是 吧 Binary search, right? 二分法 也 是 牛顿 最早 提出 来 的 The binary search was first discovered by Newton. 但 当时 是 用来 去 找 一个 方程 的 根 的 At that time, however, it was used to find the roots of an equation. 这个 研究 起来 也 很 容易 It is easy to analyze. 就是说 我们 把 1 到 100 是 吧 We have 1 to 100. 1 到 100 层 我们 画 在 一个 数轴 上 We draw them on a number line, 然后 我们 第一个 鸡蛋 and then, our first egg 我 在 50 层 的 地方 扔 will be dropped on floor 50. 如果 这个 鸡蛋 要是 碎 了 If this egg breaks, 那 就 说明 临界 楼层 一定 是 在 1 到 50 之间 对 吧 then the boundary floor must be between 1 and 50, right? 如果 50 层 这个 鸡蛋 它 不碎 If it doesn't break on floor 50, 那 就 说明 that the boundary must be between 50 and 100. 临界 楼层 应该 是 在 50 到 100 层 之间 这 就是 第一个 鸡蛋 的 扔 法 This is the way to drop the first egg. 那么 如果说 你 确定 了 它 在 1 到 50 之间 碎 了 Afterwards, if you find that it is between 1 and 50, 那 于是 我们 可以 第二个 鸡蛋 在 25 层 的 地方 扔 we can drop the second egg on floor 25. 如果 碎 了 说明 临界 楼层 在 这 If it breaks, then the boundary floor is here. 如果 不碎 说明 临界 楼层 在 这 If it doesn't then it is not here. 这样一来 我 每 扔 一个 鸡蛋 Every time I test, 都 可以 把 这个 间隔 除以 2 对 不 对 I can divide the possible range into two, right? 所以 叫 二分法 This method is called a binary search. 那 我们 知道 你 除了 几次 2 之后 Afterwards, we know how many times you divided by 2. 最后 如果 间隔 小于 1 了 If at the end, the range is smaller than 1 就 不用 再 去 试 了 对 不 对 you don't need to test it out by drop another egg. 因此 如果 我们 想 把 它 确定 出来 是 哪 一个 的话 Therefore, if we want to find out the right floor, 我们 就 需要 扔 的 次数 2ᴹ then the number of drops needs to be 2^M 它 得 大于 等于 100 It must be larger than or equal to 100 (>=100) 最后 M 就 大于 等于 log₂¹⁰⁰ so M is larger than or equal to log base 2 of 8 我们 试一试 也 能 试出来 We could solve this by guessing 这个 数 应该 是 6.64 This number should be 6.64 6.64 我们 就 取 7 好 了 Round up 6.64, and we get 7 所以 这个 时候 你 需要 扔 7 次 Therefore, in this case, you need to drop 7 times. 在 最坏 的 情况 下 你 也 需要 扔 7 次 In the worst case, you need to drop it for 7 times. 好 这是 这个 人有 无限 个 蛋 的 时候 是 这个 样子 的 Ok, so this is the case with an unlimited number of eggs. 那么 这个 面试题 一般 是 这么 问 的 Usually, this interview question asks 如果 这个 人有 两个 蛋 的话 那么 他 要 扔 多少次 才能 保证 一定 把 这个 临界 楼层 找 出来 所以 就 叫 双蛋 问题 Hence, it is called the Two Eggs Problem. 所以 他 如果 有 两个 蛋 so if he has 2 eggs 那么 这个 时候 怎么样 呢 what should he do this time? 叫 N 等于 2 Let N = 2. 我们 来看 一下 这个 情况 Let's look at this case 我们 先想 这样 一个 方法 First, let's think about the followings: 如果 第一个 蛋 某些 原因 下 它 碎 了 if the first egg breaks out of some reasons, 那 我 就 只 剩下 一个 蛋 了 then I have 1 egg remaining. 剩下 一个 蛋 之后 Since I have only 1 我 只能 一个 层 一层 一层 一层 这样 往 上试 了 I can only test it floor-by-floor, all the way to 100. 就 回到 第一种 情况 了 对 吧 We returned to the first case, isn't it? 所以 我 第一个 蛋 的 作用 The goal of my first egg 应该 是 用来 把 这个 范围 尽量 的 缩小 is to shorten the range of floors that I need to try. 然后 用 第二个 蛋 一个 一个 的 去 试 Then I use the second egg for the remaining floors. 只能 是 这样 吧 Let's also draw a diagram. 好 那 我们 还是 把 这个 图画 出来 说 有 这个 1 到 100 层 对 不 对 We have 1 to 100 floors, 然后 我 有 两个 蛋 and then we have 2 eggs, A 和 B 我们 先 让 A 这个 鸡蛋 怎么 做 呢 A and B. What shall we do with egg A first? 我 先 让 A 这个 鸡蛋 I will drop A first. 第一次 扔 I will drop it from floor 10. 我 让 它 在 10 层楼 往下 扔 它 如果 要是 碎 了 If it breaks, 就 说明 临界 楼层 在 1 到 10 之间 对 吧 then that the boundary floor is between 1 and 10, isn't it? 如果 不碎 If not, 我 就让 它 在 20 层 的 地方 扔 then I will drop it from floor 20. 如果 碎 了 在 这 if it breaks then the boundary is there. 如果 不碎 就 在 30 层 的 地方 扔 if not, drop it again from floor 30. 也就是说 我 可以 让 A 这个 蛋 This means that I can drop egg A 它 在 10 20 30 ... 一直 到 100 from floors 10, 20, 30... 100. 这些 个 楼层 扔 A 最多 可以 扔 10 次 对 吧 The maximum number of dropping A is 10, right? 好 如果 我 把 A 这个 确定 了 If A has a fixed number, 比如说 在 10 层 的 时候 没碎 say, it didn't break from floor 10 在 20 层 的 时候 碎 了 but it broke when dropping from floor 20. 那 就 说明 临界 楼层 在 这 Then the boundary floor is there. 然后 我用 第二个 鸡蛋 再 去 试 Now I use my second egg, 11 12 13 14 15 16 ... 一直 到 19 对 不 对 11, 12, 13,14,15,16 ... 19, isn't it? 所以 B 这个 鸡蛋 The number of floors from which B will be dropped: 它 扔 的 楼层 就是 x1 x2 x3 ... 一直 到 x9 x1, x2, x3 ... x9. 好 通过 这样 的 方法 This way, 我 就 一定 能够 把 这个 楼层 给 试出来 对 吧 I will surely find the boundary, right? 临界 楼层 给 试出来 Finding the boundary through tests. 那 咱们 想一想 Now let's think 最多会 扔 多少次 呢 What is the maximum number of tests? 假如 说 A 在 第 10 层楼 的 地方 就 碎 了 Let's say that A breaks when dropping from floor 10. 那么 B 最多 是 9 次 Then B will be dropped a maximum of 9 times. 总共 就是 扔 10 次 就 能 试出来 了 对 吧 This is a total of 10 tests. 好 如果 A 在 100 层 的 时候 才 碎 了 Ok, if A breaks when on floor 100 那么 A 扔 了 10 次 then A was dropped for 10 times 然后 我 B 再 去 试 After, I try with B 结果 试到 最后 一个 才 碎 It breaks on the last try 那 就 说明 你 在 99 层 或者 100 层碎 了 This means it broke when dropping from floor 99 or 100 此时 我们 就要 扔 19 次 对 不 对 This time we had to drop them for 19 times, isn't it? 所以 最坏 的 情况 下 我们 需要 扔 19 次 In the worst case, we need to test 19 times. 好 扔 19 次 咱们 思考 一下 Let's think about this a bit. 还有 没有 一种 方法 能够 比 这个 方法 更好 呢 Does there exist a better way? 这个 方法 它 有 的 时候 是 10 次 With this method, sometimes 10 times, 有 的 时候 是 19 次 and at other times it is 19. 在 10~19 之间 它 不 平均 It is not consistent. It fluctuates between 10 and 19. 原因 是 什么 呢 What is the reason? 原因 是因为 A 它 确定 的 间隔 是 等 间隔 的 The reason is that the intervals of possibilities that A eliminates are evenly spaced. 等 间隔 的 就 造成 B 这个 鸡蛋 去试 的 时候 每 一次 扔 的 次数 最多 都 是 一样 的 对 吧 A's maximum number of drops is always the same. 但是 如果 这个 临界 楼层 靠 后 的话 If the boundary is very high A 扔 的 次数 就 多 了 是不是 The number of tests would be very large. 所以 我们 在 思考 能 不能 让 这个 间隔 变得 不等 I'm thinking of whether we could make the intervals uneven. 我们 让 间隔 变得 不等 To make them uneven means that, 就是说 让 A 每多 扔 一次 One additional test for A. B 的 这个 间隔 就 缩小 一点 Smaller intervals for B. A 扔 一次 B 就 间隔 缩小 一点 Drops A. Smaller B interval. 这样一来 让 它 总 次数 能够 平均 一下 This way, the total number would be smoothed out. 也许 这种 情况 会 更好 对 不 对 Maybe this is better than the previous? 好 咱们 再 来看 一个 方法 Let's explore this further. 我们 换 一种 方法 Let's use a different explanation. 如果 我 让 这个 间隔 还是 1 到 100 是 吧 The total interval is still 1 to 100, 但是 间隔 不 一样 but the smaller intervals are different. 我 A 鸡蛋 第一次 扔 的 时候 呢 The interval created when I first dropped A is n floors. 我 让 它 的 间隔 是 n 层 然后 如果 它 不碎 If it doesn't break, 第二次 扔 的 时候 我 让 这个 间隔 是 n-1 层 then at the second test, let this interval be n-1 floors. 第三次 扔 的 时候 我 让 这个 间隔 是 n-2 层 The third time, n-3 floors. 直到 最后 一次 扔 的 时候 呢 At the final test, n is 1 floor. 我 让 这个 间隔 是 1 层 也 就是 A 每多 扔 一次 So every time I drop A 它 的 间隔 就 小 了 一点 B's interval of possible floors become smaller. 这样一来 B 所 需要 检验 的 次数 就会少 1 The number of B tests is always decreased by 1. A 多 扔 一次 B 就 少 扔 一次 More A, less B. 这样一来 总 次数 不 就 平均 了 一些 吗 then our total would be constant, right? 也许 这种 方法 会 更好 Maybe this method is better? 咱们 思考 一下 Assume that we are using this method. 假如 按照 这种 方法 的话 我们 算一算 这个 n 应该 得 几 We calculate n. 这个 并 不难 This shoudn't be hard 就是 1+2+3+ ... 一直 加 加到 n It is 1+2+3... +n. 它 的 最后 我们 都 知道 用 高斯 公式 We know how to use Gauss' formula. 它 应该 等于 n(n+1)/2 对 吧 It should be equal to n(n+1/2), right? 那么 这个 结果 它 必须 要 大于 等于 100 and then the result must be greater or equal to 100. 所以 我们 可以 计算 出 这个 n 来 Calculate n. 这个 n 要 大于 等于 13.65 n must be greater or equal to 13.65. 于是 我们 就 取 n 等于 14 We will round up n. n=14 n 等于 14 什么 意思 呢 What does this mean? 就是说 我们 不 考虑 那种 加 1 减 1 的 临界 情况 了 This means that we no longer need to consider those +1 and -1's. 就是说 A 鸡蛋 我们 这么 扔 I will drop A on floor 14. 第一次 我 让 它 跨越 14 个 间隔 也 就是 在 14 层楼 去 扔 14 层楼 如果 碎 了 就 说明 在 1~14 层 之间 if it breaks, then the boundary is between 1 and 14. 然后 我用 B 鸡蛋 试 1 2 3 4 ... 一直 到 13 对 吧 I will use egg B to try out 1,2,3,4,...,13, right? 如果 第一个 14 层 没碎 If it doesn't break from floor 14. 我 就让 它加 13 层 要 减 1 对 吧 加 13 I will add 13 since it is deducted by 1. 14 加 13 27 层 14 plus 13 gives 27. 如果 27 层不碎 If it doesn't break from floor 27, 我 就 再加 12 39 层 I will add 12 more floors, so floor 39. 不碎 我 再加 11 是 50 层 Doesn't break. Add 11. Floor 50. 不碎加 10 60 层 Add 10 floors. Floor 60. 不碎加 9 69 层 No break Add 9. Floor 69. 然后 加 8 77 层 then add 8. Floor 77. 加 7 84 层 Add 7 Floor 84 然后 加 6 是 90 层 加 5 95 层 then adding 6 gives us floor 90 Adding 5 gives us floor 95 加 4 99 层 加 1 100 层 Add 4, floor 99. Add 1, floor 100. 最后 加不上 3 了 为什么 呢 Finally, we can't add 3. Why? 因为 我 这个 实际上 是 13.65 Because n is 13.65 and we used 14. 你 取 了 个 14 自然而然 最后 它 就 会 差 了 一点点 Naturally, a little would be left at the end. 好 那么 A 它 最 多 扔 多少次 Now, what is the maximum number for A? 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12 A 最多 是 扔 12 次 A's maximum is 12 那 如果 第一次 A 就 碎 了 If A got dropped the first time 那 我 就 需要 用 B 鸡蛋 去 检验 1~13 层 then I would need B to test out floors 1 to 13. 再 加上 A 扔 的 一次 一共 是 扔 了 14 次 Adding the 1 time from A, the total is 14 times 如果 A 扔 到 27 层 的 时候 碎 了 If A breaks when reaching floor 27 那 我 B 就 需要 检验 15 层到 26 层 then B would test out floors 15 to 26 再 加上 A 扔 的 那 两次 Adding the 2 times from A 最后 结果 还是 14 次 对 吧 the final number is still 14, right? 那 当然 如果 A 扔 到 100 层碎 了 of course, if A breaks on floor 100 或者 是 100 层 还 没碎 的话 or it doesn't break 那 你 就 不 需要 用 B 去 检验 了 then you don't need B anymore 那 最少 的 是 12 次 the minimum required number is 12 times 于是 用 这种 方法 so with this method 你 扔 鸡蛋 的 次数 是 在 12~14 之间 The number of egg drops is between 12 and 14 最差 的 情况 下 是 14 次 the worst case is 14 所以 这样 一看 你 看 两个 鸡蛋 的 情况 下 looking this way, when you have 2 eggs 这 M 不是 19 this M is not 19 最差 的 情况 下 in the worst case 我 只 需要 扔 14 次 we only need to test 14 times 就 能 保证 你 一定 能够 找到 那个 临界 的 楼层 了 对 吧 to guarantee that you can find the boundary floor 好 那 这个 面试题 其实 我们 就 说完 了 Ok, we have finished explaining this interview question 不过 咱们 想 如果 仅仅 是 这样 一个 问题 的话 but if we think about this, if we only have such a question 其实 意义 并不大 its significance isn't much. 你 能够 保证 这种 方法 就是 最好 的 吗 Is this method guaranteed to be the best? 也 不见得 吧 Not necessarily, 而且 这个 人 一定 有 两个 蛋 since we have 2 eggs. 不 一定 he could have 3 eggs, 4 eggs, 5 eggs, 6 eggs... 他 可能 有 3 个 蛋 4 个 蛋 5 个 蛋 6 个 蛋 ... 那么 如果 我们 的 蛋 数量 不是 2 的话 if the number of eggs is smaller than 2 这个 问题 又 该 如何 去 解决 呢 how shall we tackle it? 所以 说 这道题 的 精髓 Therefore, the main idea of this problem 其实 在于 其他 的 情况 下 is that under the other situations 我们 需要 使用 递归 的 思想 来 进行 求解 we need to use recursive thinking. 其实 递归 思想 我们 在 之前 讲 汉诺塔 还有 拜占庭 将军 问题 的 时候 都 用到 过 但是 这个 递归 要 比 汉诺塔 那种 递归 but the one covered here is slighly more complicated than the one we used to solve the Tower of Hanoi 稍微 复杂 一点 这个 思想 是 这样 的 The idea is this. 我们 把 这个 问题 普遍化 一点 Let's generalize this problem. 就 假如 说 这 一层楼 它 有 T 层 Let's say this building has T floors. 这个 楼有 T 层 This building has T floors, 然后 我们 一共 有 N 个 蛋 and then we have N eggs in total. 这个 时候 我们 要 找到 在 最 不利 的 情况 下 now we need to find the minimum number of drop times for the worst-case scenario 至少 要 扔 多少次 才能 一定 找到 这个 临界 楼层 这个 次数 叫 M this number is M 那么 M 自然 是 T 和 N 的 一个 函数 naturally, M is a function of T and N 我 就 问 这个 函数 值 到底 应该 是 多少 对 吧 What is this value of this function? 这个 问题 我们 首先 先 从 最 简单 的 情况 说起 To tackle this, we start from the most basic case 首先 我们 画 一个 表格 First, draw a table. 这个 表格 呢 这个 表格 它 的 一列 表示 的 是 这个 楼层 数 T Its first row represents its floor number. T 可以 是 1 2 3 或者 一直 到 100 是 吧 T can be 1,2,3,...,100. 然后 蛋 的 数目 The number of eggs 也 可以 是 1 2 3 4 或者 是 更 多 的 蛋 对 吧 could also be 1,2,3,4 or even more, right? 好 的 现在 有 一些 情况 是 比较 好 填 的 Some spaces are relatively easy to fill. 比如说 吧 如果 你 只有 一个 鸡蛋 的话 For example, you only have 1 egg and 1 floor. 你 有 一层楼 the minimum drop is 1, right? 你 就 至少 得 扔 一次 对 不 对 你 有 两层楼 就 得 扔 两次 2 floors, 2 drops 有 三层楼 就 得 扔 三次 3 floors, 3 drops 所以 这 一列 是 非常 好 填 的 so these are quite easy. 那么 如果 是 只有 一层楼 呢 When there is only 1 floor, 只有 一层楼 的话 不管 你 有 几个 鸡蛋 都 只 需要 扔 一次 No matter how many eggs you have, you only need 1 test, 所以 这 一行 也 是 很 好 填 的 so this column is also very easy. 也就是说 这 两个 边界 These 2 borders, 其实 都 是 非常 非常 好 填 的 are very easy to fill. 当然 后面 还有 我 就 没有 再往 下 写 There are more. 这 两个 边界 很 好 填 These are easy to fill. 关键 是 中间 这 一大堆 The harder part is these cells. 比如说 有 3 层楼 2 个 鸡蛋 For example, we have 3 floors and 2 eggs 你 至少 要 扔 几次 What is the minimum number of drops 100 层楼 2 个 鸡蛋 你 要 扔 几次 for floor 100, 2 eggs? 5000 层楼 3 个 鸡蛋 How about the 5000th floor and 3 eggs? 你 要 扔 几次 How many times? 所以 这个 问题 就 比较复杂 These are more complicated. 我们 怎么 去 研究 它 呢 How to tackle this? 我们 就要 使用 递归 的 思想 了 We should use recursion. 这个 思想 是 这样 的 No matter how many eggs you have, 不管 你 有 多少 个 鸡蛋 在 扔 的 时候 你 首先 必须 得选 一层 You must choose a floor 然后 扔 第一个 鸡蛋 对 不 对 to drop the first egg, isn't it? 好 那么 第一个 鸡蛋 扔 在 哪 呢 Where should it be dropped? 我们 其实 也 并 不 清楚 扔 在 哪 I'm not clear either. 比如说 这个 楼层 是 1 到 T 这么 多层 Say that this building has 1 to T floors. 第一个 鸡蛋 你 随便 给 我 找个 地方 叫 第 k 层 for the first egg, you find a random floor, called k 你 就 扔 吧 扔 完 了 之后 两种 结果 Dropping it results in 2 consequences: 一种 是 碎 一种 是 不碎 Broken, or not. 如果 碎 就 说明 这个 临界 楼层 一定 在 前面 If it is broken, then the boundary floor is lower. 如果 不碎 就 说明 临界 楼层 一定 在 后面 对 不 对 If not broken, then the floor must be higher. 好 那么 如果 碎 了 你 还 需要 扔 多少次 鸡蛋 If broken, then how many more trials are needed for these k floors? 才能 确定 这 k 个 楼层 里边 哪 一层 是 临界 楼层 呢 我们 可以 说 这个 数 This number is actually 其实 就是 M 什么 呀 k 层楼 N-1 个 蛋 M(k, N-1). 为什么 呢 因为 你 第一个 鸡蛋 已经 碎 了 Why? Because the first egg was broken, so you now have N-1 eggs. 所以 你 的 蛋 只能 变成 N-1 个 了 而 楼层 原来 是 T 层 Originally you had T floors. Now you know that the boundary floor is lower, 现在 你 已经 知道 不在 后面 只 在 前面 所以 楼层 变成 k 了 so T is replaced by k. 因此 你 会 有 这样 的 一个 数据 Therefore, you have M(k, N-1). 好 这 是 你 再 往后 还 需要 确定 多少次 Now, how many more times do we need to try? 再往 下 如果 它 不碎 的话 也 是 一样 的 In the previous case, if the egg doesn't break, the result is still be the same. 此时 楼层 就 变成 了 这么 多层 The number of floors is now T-k 这个 层数 应该 是 T-k 层 而 蛋 的 数目 还是 N 个 对 吧 The number of eggs is still N. Therefore, we still need M(T-k, N) tries. 于是 我们 可能 还 需要 找 这么 多次 才能 确定 具体 是 在 哪 一层 因为 我们 要 找 的 是 最 不利 的 情况 下 Since we are looking for the required trials in the worst case, 需要 扔 多少 层 所以 在 这 两种 可能 下 我们 要 把 它 取 一个 最大值 这 两种 可能 中 比较 大 的 那个 值 we will take the larger value. 就是 我 第一个 鸡蛋 扔 到 k 层 的 时候 This is the minimum number of trials required when we 我 需要 数 的 个数 对 吧 throw the first egg from floor k 最少 需要 数 这么 多次 但是 同时 你 不要 忘 了 你 开始 还 扔 了 一层 对 不 对 but don't forget you have tested one floor earlier 所以 你 还要 把 这个 数字 再 加上 一个 1 so we need to add 1 to it. 就 这 两个 数中 较大 那个 数再加 1 max{M(k, N-1), M(T-k, N)} + 1 它 就 等于 什么 呢 What is it equal to? 它 就 等于 当 你 第一个 鸡蛋 扔 到 第 k 层时 It is equal to the number of trials when you have T floors and N eggs, with the first trial on floor k. 如果 原来 你 有 T 层楼 和 N 个 鸡蛋 你 需要 扔 鸡蛋 的 个数 但是 你 第一个 这个 k 你 怎么 确定 呢 对 不 对 Now, how do we determine k? 我们 的 一个 方法 就是 枚举 One way is to list all k's from 1 to T. 就是 把 k 等于 1 2 3 4 5 6 7... 一直 到 T 我 全数 一遍 我 再 画 一个 表格 Let me draw another table. 这个 表格 是 我们 知道 你 这个 k 它 有 很 多种 可能 k can take any values. 你 第一个 鸡蛋 可以 扔 在 第一层 Your first try could be on floor 1. 你 也 可以 扔 到 第二层 可以 扔 第三层 It could also be floor 2 or 3. 一直 到 你 可以 扔 到 最后 一层 就是 第 T 层 All the way to floor T. 那么 你 在 每 扔 一次 你 都 可以 做 这个 运算 You could calculate M every time you try a different starting floor k. 对 不 对 找到 那种 最 不利 的 情况 下 Find the number of tries, M, in the worst case. 你 需要 扔 鸡蛋 的 次数 Mᴋ 是 吧 所以 如果 你 第一个 鸡蛋 扔 到 第一层 了 就是 M₁ First floor, M_1 Second, M_2 Third, M_3 扔 到 第二层 就 M₂ 扔 到 第三层 就 M₃ 一直 到 如果 第一个 鸡蛋 扔 到 T 层 了 那 就是 Mᴛ To M_T 对 不 对 好 第一个 鸡蛋 你 是 可以 选 的 你 可以 扔 在 任何 一层 所以 我 需要 在 这 里面 所有 的 值 中 Since I could choose k, I will pick the one with the lowest tries. 我选 一个 最 什么 的 值 最小 的 值 所以 最终 的 结果 是 Therefore, M 在 T 层楼 N 个 鸡蛋 的 情况 下 它 等于 M(T, N) = min {M_1, M_2, ... , M_3} 最小值 M₁ M₂ ... 一直 到 Mᴛ 这样一来 我们 就 把 这个 数据 给 确定 了 Now we have a function that we can use for this problem. 有人 说 那 这个 运算 这么 复杂 我 到底 怎么 算 You may say that this is too complicated to calculate. It is actually quite simple. 其实 很 简单 你 看 你 在 每 一次 计算 的 过程 中 At every drop, regardless of which floor, it is either T replaced by k, or T replaced by T-k. 不管 你 从 哪 一层楼 去 扔 你 都 要不然 是 把 这个 楼层 数给 减少 了 T 变成 k 了 或者 T 变成 T-k 了 要不然 就是 把 鸡蛋 的 个数 减少 了 It is either one less egg, 或者 没有 减少 对 不 对 or that the number of eggs stays the same. 所以 我们 已经 知道 了 Since we know what would happen 楼层 少 和 鸡蛋 少 的 时候 的 情况 when we have 1 egg and N floor, or 1 floor and N eggs, 我们 就 可以 一点一点 算 出 we can use them to calculate the subsequent cases 楼层 多 和 鸡蛋 多 的 情况 for larger N and T. 也就是说 我们 可以 先算 两层楼 两个 鸡蛋 的 时候 For example, we could first calculate T=2, N=2. 三层楼 两个 鸡蛋 的 时候 T=3, N=2. 把 这 一列 都 算 完 Finish this second row, 然后 利用 这个 数据 我 再 去 算 三个 鸡蛋 的 时候 and then use this data to calculate the next row N=3. 两层楼 如何 三层楼 如何 我 把 这 一列 也 算 完 然后 我 再 算 四个 鸡蛋 的 时候 then we calculate the row for N=3. 这个 数 这个 数 分别 是 多 大 这样 一点一点 的 递归 We will fill in this table recursively, step-by-step. 就 把 这个 东西 给 弄出来 了 所以 大家 看 这个 思想 其实 还是 挺 复杂 的 对 吧 After exploring this far, we see that this question is actually quite complicated. 这是 一个 递归 的 这样 一个 思想 It is a recurrence relationship. 那么 既然 说 到 面试题 了 Since we have been talking about an interview question, let me ask a relatively easier question, 咱们 不妨 出 一个 简单 一点 的 面试题 给 大家 想一想 for everyone to think about. 假如 有 一个 圆形 的 小岛 Let's say there is an island that has a the shape of a circle 然后 有 一条 鳄鱼 在 圆形 小岛 周围 游弋 A crocodile is swimming around the island. 鳄鱼 的 速度 是 人 的 四倍 The speed of the crocodile is 4 times that of the human. 而且 鳄鱼 总是 希望 找到 一个 离 人 最近 的 位置 It always finds a spot that is closest to the human. 而 这个 人 最 开始 在 这个 小岛 的 正 中心 The human starts at the center of the island. 那么 我 问 这个 人该 如何 运动 How should he move to reach the edge of the island before the crocodile? 才 能够 比 鳄鱼 先 到达 这个 岛 的 边缘 从而 逃离 这个 岛 呢 大家 如果 有 答案 的话 不妨 在 下方 留言 If you know the solution, do not hesitate to post a comment below. 大家 如果 喜欢 我 的 视频 If you like this video, 可以 在 YouTube 账号 李永乐 老师 里 订阅 我 you could subscribe to my Youtube channel Liyongle (李永乐老师). 点击 小 铃铛 可以 第一 时间 获得 更新 信息 Click on the bell near the subscribe button to be notified of updates.