问题描述 有十二个鸡蛋，其中有一个是坏的（重量与其余鸡蛋不同，不知道是重了还是轻了），用天平称三次，称出坏的那个鸡蛋 问题解决 首先将十二个鸡蛋进行编号，分为为 1，2，3 . . . 12，将其分为三组...（假设轻了，不影响答案）并且出现问题的鸡蛋在9，10，11中，在9，10，11中任取两个（9，10）进行比较 相等则坏鸡蛋为11号 不相等但是由前面得出了坏鸡蛋轻了，则坏鸡蛋为轻的那个 第一组与第二组不等...1，2，3号中，同时也可以推断出来坏鸡蛋是轻了还是重了，所以从1，2，3中任取两个进行比较，如果相等则为没取的那个，如果不等则为重的那个（因为前面假设条件为第一组重于第二组） 不相等则出现问题可能在Z1...也可能在Z2 Z1 > Z2：说明出现问题的为4号或者8号，从这两个中任取一个与第三组任意一个比较如果相等则为没取那个，如果不等则坏鸡蛋为取的那个 Z1 < Z2：说明出现问题的为5，6，7...号，并且推断出坏鸡蛋为重了还是轻了（根据前面的假设这里应该为坏鸡蛋变轻了），从中任取两个进行比较，如果相等则为没取那个，如果不等则为轻的那个 可能会在Z1与Z2比较大小哪里感觉到迷糊，你可以使用假设方法
知乎上有很多解答：https://www.zhihu.com/question/55484566
问题描述 给定一定楼层数的建筑物和一定数量的鸡蛋，求出可以找出门槛楼层的最少鸡蛋掉落实验的次数，约束条件是：幸存的鸡蛋可以重复使用，破碎的鸡蛋不能再次使用，如果鸡蛋从此层掉落会碎，那么从更高的楼层掉落也会碎...解决问题 我们先来看只有一个鸡蛋的情况，如图1所示，由于鸡蛋会破碎不可再次使用，所以我们只能从最低的楼层开始扔鸡蛋，如果在第一层楼扔鸡蛋没有碎，那么继续往上也就是第二层扔鸡蛋，如果鸡蛋在某一层扔碎了，那么说明门槛楼层就是这一层...这样要找出门槛楼层的最少扔鸡蛋的次数就是楼层的层数。 图1 只有一个鸡蛋的情况 那如果我们有足够多的鸡蛋，即鸡蛋数大于等于楼层数，如图2所示，我们可以先随便在一个楼层扔一个鸡蛋看看会发生什么。...图2 有足够多的鸡蛋 比如说我们选择在3楼扔出一个鸡蛋，如图3所示。...图3 在3楼扔出一个鸡蛋 那么事实是扔出的鸡蛋会有两种结果，一种情况是鸡蛋在3楼扔下破碎了，那么说明我们要找的门槛楼层在3楼以下的楼层，如图4所示，同时我们可以用的鸡蛋减少了一个，即问题的规模减少。
现在确定这栋楼存在楼层0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于F的楼层都会碎，低于F的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层F呢？...比方说现在先不管鸡蛋个数的限制，有 7 层楼，你怎么去找鸡蛋恰好摔碎的那层楼？...你直接去第 4 层扔一下，如果鸡蛋没碎还好，但如果碎了你就没有鸡蛋继续测试了，无法确定鸡蛋恰好摔不碎的楼层F了。这种情况下只能用线性扫描的方法，算法返回结果应该是 7。...我们在第i层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。...注意，这时候状态转移就来了： 如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼； 如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1.
————— 第二天 ————— 题目：扔鸡蛋问题 有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。...比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。 问：如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？ 举个栗子，最笨的测试方法是什么样呢？...方法一：二分法 采用类似于二分查找的方法，把鸡蛋从一半楼层（50层）往下扔。 如果第一枚鸡蛋在50层碎了，第二枚鸡蛋就从第1层开始扔，一层一层增长，一直扔到第49层。...方法二：平方根法 如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数尽可能均衡呢？ 很简单，做一个平方根运算，100的平方根是10。...假设第一次扔在第x-1层： 如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第1层开始一层一层扔，一直扔到第x-2层。
预计阅读时间：7 分钟 今天要聊一个很经典的算法问题，若干层楼，若干个鸡蛋，让你算出最少的尝试次数，找到鸡蛋恰好摔不碎的那层楼。...比方说现在先不管鸡蛋个数的限制，有 7 层楼，你怎么去找鸡蛋恰好摔碎的那层楼？...你直接去第 4 层扔一下，如果鸡蛋没碎还好，但如果碎了你就没有鸡蛋继续测试了，无法确定鸡蛋恰好摔不碎的楼层F了。这种情况下只能用线性扫描的方法，算法返回结果应该是 7。...我们在第i层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。...注意，这时候状态转移就来了： 如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼； 如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1.
这道题是说，100 层楼，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法，因为只想记录一下思路和讨论过程，写得很简略。...动态规划法求解 现在，我有两枚鸡蛋，第一枚鸡蛋从哪一层楼开始扔就显得至关重要了。如果第一枚鸡蛋碎了，那就回到刚说的只有一枚鸡蛋的问题了。...” 到 “m 个鸡蛋” 现在把问题扩展一下，由两个鸡蛋扩展到 m 个鸡蛋，times 数组第一维表示最多可以扔几次，第二维表示扔第几次： public static int dropEgg(int N...现在把思路从 “给定 N 层楼，问最少需要扔多少次” 变化到 “给定 x 次最多扔鸡蛋的次数，最多可以在几层的楼上确定鸡蛋破碎的临界层”。...现在把问题稍稍转变一下，把鸡蛋数量的限制去掉，再把求爬楼梯的限制加上，不妨再来求解： 如果鸡蛋数量无限，但是假如说扔一次鸡蛋需要耗费力气 a，每爬一层楼（无论向上还是向下）需要耗费力气 b，现在用怎样的扔鸡蛋策略
解决思路 2.1 鸡蛋个数无限制 2.2 鸡蛋个数有限制 2个鸡蛋 3个或者更多个鸡蛋 ---- 1....题目介绍 扔鸡蛋是一道经典的面试题，具体问题是给出 N (N>=2)个鸡蛋，以及M层楼房(M>=N)，要求计算最少需要多少次/平均需要多少次能得出鸡蛋在第几层正好摔碎。...2.1 鸡蛋个数无限制 我们先讨论鸡蛋个数无限制的情况。当可以无数次丢掷鸡蛋来寻找正确层数时，这个问题就可以简化为一个查找问题。...2.2 鸡蛋个数有限制 当然，更多的情况还是鸡蛋个数有限制，最常见的有2个鸡蛋和3个鸡蛋。在这种情况下，鸡蛋一旦摔碎意味着少了一次测试机会，因此需要解决的问题比无限制的情况更多。...原始问题是求M层楼x个鸡蛋，最坏需要投掷多少次才能检测出鸡蛋正好摔碎的楼层。当丢出一个鸡蛋之后，问题就减小为M-n层楼，用x/x-1个鸡蛋最坏需要多少次，这里的n是我们的划分区域大小。
有道经典的算法题，两个一模一样的鸡蛋，某层之上扔鸡蛋就会碎。假如运气最差的话，问要测试多少次才能找出这层楼来。 如果只有一个鸡蛋，我就只能一层一层试验。...两个的话关键就是找着第一个鸡蛋试验的位置，第二个鸡蛋还是只能一层一层试验。 这道问题其实可以扩展到任意个鸡蛋，但现在还是只看 2 个鸡蛋的情况。...2 个鸡蛋只有 n 层的最优解求出来假使为 k，那么，n+1 层的时候，把第一个鸡蛋在第 k 层释放，只有两种情况（n+1 只是分解成两个<=n 的子问题，这两个都是已经有解了的）： （1）破碎，于是只有之后就只能遍历从地面到第
鸡蛋掉落） https://leetcode-cn.com/problems/super-egg-drop/ 题目描述 你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑...你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。...每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。 你的目标是确切地知道 F 的值是多少。...示例 1： 输入：K = 1, N = 2 输出：2 解释：鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。...self.superEggDrop(K, N - i) + 1 指的是鸡蛋没有破碎的情况，我们仍然有 K 个鸡蛋， 并且剩下 N - i 个楼层需要 check。
在上一篇漫画中，小灰介绍了一道有趣的智力题： 漫画：有趣的扔鸡蛋问题 那么，如何利用动态规划来求出扔鸡蛋问题的通解？ 换句话说，有M层楼 / N个鸡蛋，要找到鸡蛋摔不碎的临界点，需要尝试几次？...在上一篇漫画中，两个鸡蛋100层楼的条件下，我们找到了一个规律： 假设存在最优解，在最坏情况下尝试次数是 X，那么第一个鸡蛋首次扔出的楼层也是 X 。 这个规律在三个以上鸡蛋的条件上还能否适用呢？...让我们来举个栗子： 假设有三个鸡蛋，100层楼，第一个鸡蛋扔在第10层并摔碎了。这时候我们还剩下两个鸡蛋，因此第二个鸡蛋不必从底向上一层一层扔，而是可以选择在第5层扔。...假设我们第一个鸡蛋扔出的位置在第X层（1<=X<=M），会出现两种情况： 1.第一个鸡蛋没碎 那么剩余的M-X层楼，剩余N个鸡蛋，可以转变为下面的函数： F（M-X，N）+ 1，1<=X<=M 2.第一个鸡蛋碎了...-1，N-1） + 1）），1<=X<=M 比如我们想要求解3个鸡蛋3层楼的最优尝试次数，并不需要知道1个鸡蛋这一层的值，只需要关心2个鸡蛋和3个鸡蛋在各个楼层的值即可。
https://www.bilibili.com/video/av96214853/
引言 鸡蛋掉落问题算是一道经典的算法题目了，leetcode上面也有收录，是被我收藏了的少数几道题目之一，确实是挺有意思的一道题目，李永乐老师也做过视频讲过这个问题。...问题简介 首先，我们来看一下经典算法问题的描述： 你手上有K个鸡蛋，然后有一幢N层高的楼，他有一个临界楼层F，当鸡蛋从F层或更低的楼层中掉落的话，他都不会碎裂；反之，当鸡蛋从高于F层的楼上掉落时，鸡蛋就会碎裂...显然，如果只有一个鸡蛋，那么有几层楼就必须做几次实验才能够确保找出临界层F；而如果只有一层楼，那么无论手上有多少鸡蛋，所需要进行的实验次数都是一次。...dp[k][n-i]) for i in range(1, n+1)) 即是说，考察每一次操作从第i层掉落的情况，如果没有碎，那么只需要考察楼上的第n-i层即可；反之，如果碎了，那么只要考察在k-1个鸡蛋的情况下对
问题 假设有一栋大楼有100层，其中有1层比如F层，你从这一层或者比它低的层往下扔鸡蛋，鸡蛋不会碎，但是从比F层高的楼层开始扔，鸡蛋一定会碎。...可以看到第1个鸡蛋从14层开始实验，后面的楼层每次增加都少1，这样一来鸡蛋1每多实验一次，就让鸡蛋2少实验一次，也就是说让鸡蛋1实验次数和鸡蛋2的实验次数之和保持在一个平均值，这样无论哪种情况都维持这个值...当从一个楼层i往下扔鸡蛋的时候，只有2种结果，要么鸡蛋碎了，要么没碎。...状态转移 和递归的思路一样，当从第j层扔鸡蛋时，要么鸡蛋碎了，楼层变为j-1，鸡蛋数变为k-1；要么鸡蛋没碎，楼层变为N-j，鸡蛋数不变还是k。...状态初始化 当K=0或者m=0时，即没有鸡蛋或者不扔鸡蛋，都是无法从任何楼层中测出结果的，所以填充0； m=1，只扔1次鸡蛋，无论你有多少个鸡蛋，都只能在一层楼中测出答案，所以全是1； K=1，只有1个鸡蛋
题目背景 Czyzoiers 都想知道小 x 为什么对鸡蛋饼情有独钟。经过一番逼问，小 x 道出 了实情：因为他喜欢圆。
PART 扔鸡蛋实验 有一栋100层的楼，和2个坚硬的鸡蛋，从楼上扔下鸡蛋，鸡蛋会在大于某一层刚好开始碎，那最少几次能测出鸡蛋能承受的最大楼层呢？...如果从第50层扔下鸡蛋没碎，第51层扔下碎了，那鸡蛋能承受的最大楼层就是50。 注意：你手上只有2个鸡蛋，如果扔下碎了，就没法再使用了。 ?...2.如果有2个蛋，考虑最小的情况，1，2，3层楼 1层楼，只需1次，而且能看出鸡蛋数超过楼层数没意义。 ? 2层楼，分别先从1、2层扔，枚举所有的情况。最好的方案是总共要2次。 ?...且扔下一个鸡蛋后，问题会转化成2层或1层的子问题，这个在上一步已经求出结果了。 从这3种情况中选择最好的方案，就是先从2层扔，总共要2次。 ?...03 PART 推广：N层楼，M个蛋 为描述方便，设表示层楼，个鸡蛋最小要测试的次数。 从第层扔下 碎， 不碎， 则 ? 04 PART 代码实现 ?
在上一篇漫画中，小灰介绍了一道有趣的智力题： 漫画：有趣的扔鸡蛋问题 那么，如何利用动态规划来求出扔鸡蛋问题的通解？ 换句话说，有M层楼 / N个鸡蛋，要找到鸡蛋摔不碎的临界点，需要尝试几次？...在上一篇漫画中，两个鸡蛋100层楼的条件下，我们找到了一个规律： 假设存在最优解，在最坏情况下尝试次数是 X，那么第一个鸡蛋首次扔出的楼层也是 X 。 ? 这个规律在三个以上鸡蛋的条件上还能否适用呢？...让我们来举个栗子： 假设有三个鸡蛋，100层楼，第一个鸡蛋扔在第10层并摔碎了。这时候我们还剩下两个鸡蛋，因此第二个鸡蛋不必从底向上一层一层扔，而是可以选择在第5层扔。...假设我们第一个鸡蛋扔出的位置在第X层（1<=X<=M），会出现两种情况： 1.第一个鸡蛋没碎 那么剩余的M-X层楼，剩余N个鸡蛋，可以转变为下面的函数： F（M-X，N）+ 1，1<=X<=M 2.第一个鸡蛋碎了...比如我们想要求解3个鸡蛋3层楼的最优尝试次数，并不需要知道1个鸡蛋这一层的值，只需要关心2个鸡蛋和3个鸡蛋在各个楼层的值即可。
文章目录 题目描述 题目分析（我的想法） 题目再分析 题目描述 我有一箩筐的鸡蛋，我可以给你两个。 我有一栋一百层的楼，我想让你站在第一百层，以最少的次数帮我测出来鸡蛋最多扔到哪一层不会碎。...我说说我的想法，首先，第二个鸡蛋肯定一层一层扔啊（不是两层两层扔）。 那第一个鸡蛋呢？ 我是这么想的啊，土是土了点，但我觉得很有效。...对第一个鸡蛋而言 扔的层数/砸碎概率 一次 两次 三次 四次 五次 六次 七次 八次 九次 十次 十一次 十二次 八层 0.08 0.08 0.08 0.08 0.08 0.08 0.08 0.08 0.08...---- 题目再分析 后来，我看到了这么一种解法： 说是一直以同样的层数匹配下去，会对高层鸡蛋不公平。 但是呢，考虑到上面的情况，给出了一种优化，即每次扔的层数递减。 为什么不是迪迦呢？...对高层的鸡蛋更不公平了。 所以，要扔到一百层，第一次扔多少呢？
举例：2个鸡蛋，4层楼，如果从2楼扔下鸡蛋，鸡蛋碎了，那么鸡蛋接下来要在1楼扔下试试的，所以这个时候，就演变成了1个鸡蛋1层楼的问题； 鸡蛋没碎：那么鸡蛋个数k不变，f的值范围是[n-x, n]， 这个时候我们就把本问题缩小成了一个小问题...举例：2个鸡蛋，4层楼，如果从2楼扔下鸡蛋，鸡蛋没碎，那么鸡蛋接下来要在3楼甚至4楼再扔下试试的，所以这个时候，就演变成了2个鸡蛋2层楼的问题； 通过以上分析，不管从x楼扔下的鸡蛋碎没碎，我们的尝试扔的次数一定得能得出确切的...k=1，只有1个鸡蛋的时候，不管n是几，一定都得从1楼开始，然后一层一层的尝试扔鸡蛋，直到鸡蛋碎了或者到了楼顶为止。...如果你一下子跑到8楼扔鸡蛋，结果鸡蛋碎了，那你就再没有鸡蛋去扔了，你永远也得不到n了。因此，dp(1, n) = n。...（哈哈，不要抬杠说再去多买几个鸡蛋~） n=1，只有1层楼，不管你有几个鸡蛋，只扔1个鸡蛋看碎不碎，就知道结果了。因此，dp(k, 1) = 1。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
