鸡蛋的暴走
问题:
你有两个一模一样的鸡蛋，现在站在一个100层建筑物面前，如果需要得到一个鸡蛋从最高多少层落下完好无损，请问最少试验多少次才能成功？
解答:
最简单的办法就是从一楼开始丢鸡蛋，如果鸡蛋没有坏，就上一层楼继续向下扔鸡蛋，如果鸡蛋摔坏了，那么就得到鸡蛋不会被摔碎的最高楼层是0。
如果我们继续这个流程，我们很容易用一个鸡蛋得出鸡蛋不会被摔破的最高楼层，这样如果鸡蛋不会被摔破的最高楼层是100，我们需要尝试100次。
100次？ 我们应该可以优化下。
让我们从第2层楼开始，如果鸡蛋破损，我们可以回到1楼使用第二枚鸡蛋(别忘记共有2个鸡蛋)继续尝试，如果没有损坏，我们继续上楼在4楼尝试(2个倍数)，如果鸡蛋破损了，我们假设是 x 层，这样鸡蛋不会被摔碎的最高楼层是x-2层，我们后面只要回到x-1层用第二枚鸡蛋试验即可。
那么我们最多需要尝试多少次？ 如果鸡蛋不会被摔破的最高楼层是98或99层，我们需要尝试50次到达100层，然后回到99层用第2个鸡蛋继续试验，那么总计51次。已经比上面的结果消减一半了。
51层？ 我们可以继续优化下。
如果我们每次间隔3楼呢，按照上面的逻辑，我们需要35次才能得到最终结果（33次达到99楼，余下2次是在97层和98层）。
以此类推直到间隔16层，仍需要21次，其中间隔8层的时候需要最少，仍高达19次。
总觉得有点不对，我们能否尝试每次间隔不一样吗？ 比如等差数列。
如我们第一次试验在14楼，如如果破碎了就往上逐层（1，2,3，……，13）试验，共需14次。如果没有破碎，往上走13层，在27楼第二次丢下第一颗鸡蛋；如果碎了，换第二颗鸡蛋在（15,16,17，……，26）逐层实验，共需要14次，若仍没碎，往上走12层试验第一颗鸡蛋；以此类推，我们可以囊括105层 (14 + 13 + 12 + … + 1) 。因为我们只需要覆盖100层，14次足够找出鸡蛋不会被摔破的最高楼层。
最后, 14 是能得到最终结果尝试的最少次数。
<blockquote> 如果你真的看懂了，请点赞。 </blockquote>
推荐阅读
网友评论