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

各位 同学 大家 好 我 是 李永乐 老师 有 一个 小朋友 跟 我 说 他 年底 的时候 刚刚 把 工作 辞 了 准备 过 完 年 找 工作 结果 就 来 了 疫情 那 现在 复工 复产 的 节奏 越来越 近 了 他 就 开始 着手 准备 找 工作 的 事 了 他 最近 发现 了 一个 面试题 据说 是 微软 还是 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 这个 蛋 它 在 102030 ... 一直 到 100 这些 个 楼层 扔 A 最多 可以 扔 10 次 对吧 好 如果 我 把 A 这个 确定 了 比如说 在 10层 的 时候 没 碎 在 20层 的 时候 碎 了 那 就 说明 临界 楼层 在 这 然后 我 用 第二个 鸡蛋 再 去 试 111213141516... 一直 到 19 对 不 对 所以 B 这个 鸡蛋 它 扔 的 楼层 就是 x1x2x3...一直到 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 层 不碎 加 969层 然后 加 877层 加 784 层 然后 加 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 可以 是 123 或者 一直 到 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 账号 李永乐 老师 里 订阅 我 点击 小 铃铛 可以 第一时间 获得 更新 信息