The latest articles on DEV Community by liuxiao-guan (@liuxiaoguan). https://dev.to/liuxiaoguan https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F3655445%2Fccf3383d-bdce-4fce-985e-7413fb94ae2b.png https://dev.to/liuxiaoguan en liuxiao-guan Thu, 18 Dec 2025 04:35:20 +0000 https://dev.to/liuxiaoguan/zhi-li-ti-gao-kong-pao-ji-dan-kk1 https://dev.to/liuxiaoguan/zhi-li-ti-gao-kong-pao-ji-dan-kk1 <p><strong>来源</strong>：高通面试题<br> <strong>题目</strong>：有一栋100层的楼，和2个坚硬的鸡蛋，从楼上扔下鸡蛋，鸡蛋会在大于某一层刚好开始碎，在最坏情况下，最少要扔多少次，才能一定找出这个临界楼层？</p> <p><strong>错误思路</strong>：二分法，100-50-25-12-6-3-1 但是这样不同的临界楼层，扔的次数都是不一样，最多高达50次（但是实际上有更少的次数）<br> 如临界楼层为49，第一个鸡蛋在50层碎了，之后第二颗鸡蛋为了找到临界楼层只能一层层地从一层向上找，直到49层。</p> <p><strong>正确思路：</strong>：<br> 首先要理解题目，<br> 其一：无论临界楼层在100层的哪一层，我保证最多扔多少次？<br> 其二：两个鸡蛋的作用，第一个鸡蛋用来分段，第二个鸡蛋用于逐层扫描，以找到临界楼层<br> 那么在最坏的情况下，第一个鸡蛋向下分的段越大，会导致最后的结果也就越大（如二分法的50次）</p> <p>因此我们不妨有一个聪明的做法就是<strong>第一个鸡蛋给予可扫描的段+已经扔的次数</strong>是固定的 这样无论临界层在哪，<strong>第一个鸡蛋给予可扫描的段+已经扔的次数=总扔的次数</strong> 都是差不多的。具体做法：每多试一次第一个鸡蛋，第二个鸡蛋需要扫描的范围就减少一层。<br> 如第一个鸡蛋先扔第14层：<br> 假设碎了，那么第二个鸡蛋逐层扫描，最坏是14层<br> 假设没碎，那么第一个鸡蛋就放在27层（14+13层），即使在14-27扫描，最坏也是14次，之后这样依次递减 这样无论临界楼层在哪一层 最坏都是14次</p> <p>那第一个鸡蛋的14层是怎么确定的呢？我们可以知道之后段的范围是不断递减的，所以我们希望之后递减到1的时候能超过100层了，因此要计算 1+2+3+4+...+n &gt;= 100,得到n最小为14 </p> webdev ai learning