Skip to content

Instantly share code, notes, and snippets.

@sing1ee
Last active March 27, 2024 06:37
Show Gist options
  • Save sing1ee/5971946 to your computer and use it in GitHub Desktop.
Save sing1ee/5971946 to your computer and use it in GitHub Desktop.
Google面试题:扔鸡蛋问题

Google面试题:扔鸡蛋问题

原题描述

两个软硬程度一样但未知的鸡蛋,它们有可能都在一楼就摔碎,也可能从一百层楼摔下来没事。有座100层的建筑,要你用这两个鸡蛋通过最少的次数确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋

方法分析

看到这个题目,最保险的方法就是一层一层试验,但这样只需要一个鸡蛋就可以了。我们现在有两个鸡蛋,完全可以用有更快的方法。

进一步呢?可能试验的方法是二分查找,例如,第一个鸡蛋再50层扔下,如果碎了,第二个鸡蛋从1-49逐层试验;如果没碎,第一个鸡蛋在75层扔下,如果碎了,第二个鸡蛋从51-74逐层试验…但是,这个方法,很容易悲剧,例如,当正好49层是可以安全落下的,需要尝试50次。比只有一个鸡蛋的情况,效果还要差。

上面的分析都是从鸡蛋的角度出发的,想要得到最少的尝试次数,似乎比较难。那如果我们换个角度,从每个高度的楼层来看呢?如果,某个楼层是可以安全落下的,那么最少需要多少次尝试呢?看下面的分析

在我们编程解决问题的过程中,如果遇到最优问题的时候,往往可以先尝试一下动态规划的方法。而动态规划的方法,首要的我们要找到构成这个最优问题的最优子问题。所以,下面的分析,我们首先尝试动态规划的方法,如何解决这个问题,这也是典型的程序员的思路;其次,在众多的问题当中,有不少可以直接归结为数学方程式,如果我们能够写出数学方程式,那么,答案将是更加的简洁、美妙。所以,第二个方法,将尝试如果总结出数学方程式。

基于动态规划的方法

前面提到,若要采用动态规划的方法,最重要的是要找到子问题。做如下的分析,假设f{n}表示从第n层楼扔下鸡蛋,没有摔碎的最少尝试次数。第一个鸡蛋,可能的落下位置(1,n),第一个鸡蛋从第i层扔下,有两个情况:

  • 碎了,第二个鸡蛋,需要从第一层开始试验,有i-1次机会
  • 没碎,两个鸡蛋,还有n-i层。这个就是子问题了f{n-i} 所以,当第一个鸡蛋,由第i个位置落下的时候,要尝试的次数为1 + max(i - 1, f{n - i}),那么对于每一个i,尝试次数最少的,就是f{n}的值。状态转移方程如下: f{n} = min(1 + max(i - 1, f{n - 1}) ) 其中: i的范围为(1, n), f{1} = 1 完毕。
推广

动态规划的方法,可以推广为n层楼,m个鸡蛋。如下分析: 假设f{n,m}表示n层楼、m个鸡蛋时找到最高楼层的最少尝试次数。当第一个鸡蛋从第i层扔下,如果碎了,还剩m-1个鸡蛋,为确定下面楼层中的安全楼层,还需要f{i-1,m-1}次,找到子问题;不碎的话,上面还有n-i层,还需要f[n-i,m]次,又一个子问题。 状态转移方程如下: f{n, m} = min(1 + max(f{n - 1, m - 1}, f{n - i, m}) ) 其中: i为(1, n), f{i, 1} = 1

基于数学方程的方法

假设最少尝试次数为x,那么,第一个鸡蛋必须要从第x层扔下,因为:如果碎了,前面还有x - 1层楼可以尝试,如果没碎,后面还有x-1次机会。如果没碎,第一个鸡蛋,第二次就可以从x +(x - 1)层进行尝试,为什么是加上x - 1,因为,当此时,第一个鸡蛋碎了,第二个鸡蛋还有可以从x+1 到 x + (x - 1) - 1层进行尝试,有x - 2次。如果还没碎,那第一个鸡蛋,第三次从 x + (x - 1) + (x - 2)层尝试。碎或者没碎,都有x - 3次尝试机会,依次类推。那么,x次的最少尝试,可以确定的最高的楼层是多少呢? x + (x - 1) + (x - 2) + … + 1 = x(x+1) / 2 那反过来问,当最高楼层是100层,最少需要多少次呢?x(x+1)/2 >= 100, 得到x>=14,最少要尝试14次。

【全文完】

@zhipcui
Copy link

zhipcui commented Apr 24, 2015

在动态规划的推广处,状态转移方程应该如下: f{n, m} = min(1 + max (f{i - 1, m - 1}, f{n - i, m}) ) 其中: i的范围为(1, n), f{i, 1} = 1。

@jeankueo
Copy link

jeankueo commented Oct 22, 2016

good gist. 不过想说两句,实际上这个策略最坏情况是12次吧, 14是105层。如果第一个鸡蛋每次尝试的成功后跳跃的层数是固定的,基本上最坏情况 - 也就是99层是碎掉的最底层 - 是稳定在19次。如果想最优化最坏情况,也就是那个楼层是99,那么要最小化最后一个step尝试的机会,那么是用你这个这个算法,不过牺牲了其他非最坏情况的次数。 http://datagenetics.com/blog/july22012/index.html 这里有非常详细的讲解。

@EcoJ
Copy link

EcoJ commented Oct 29, 2016

@jeankueo The worst case is not when the egg breaks at the 100th floor but at the ( ∑i (15-i) ) -1 where i in [1, 14] and i ∈N, specifically, at the 13th, 26th, 38th, 49th, 59th, 68th, 76th, 83rd, 89th, 94th and 98th floor. In these cases, we will test 14 times.

@zjplab
Copy link

zjplab commented Dec 28, 2016

为什么动态规比二分更好?50,75,87.5这样这样折半才是标准的二分查找吧,而且这里面1到100是“有序"的,假如50层没坏,必然是51到100层坏掉

@xiewenya
Copy link

@zjplab 如果在50层第一个鸡蛋没有坏,那么最差情况下需要24次尝试就能找到对应楼层。但是如果在50层没有碎,那么在最坏情况下你就需要49次尝试才能找到对应的楼层。所以,你需要平衡第一个鸡蛋在碎了的情况下和没碎情况下的尝试次数。很显然第一次尝试的楼层应该小于50

@thinki
Copy link

thinki commented Apr 13, 2017

@xiewenya 是不是笔误了,“但是如果在50层没有碎” 应该改成“但是如果在50层鸡蛋碎了”吧?

@meizzhou
Copy link

meizzhou commented Jul 6, 2017

@zjplab 你太二了,如果鸡蛋在第四层碎,你第一次50层碎一个,第二次25层碎一个,于是你就没有鸡蛋了。。。。

@dahaihu
Copy link

dahaihu commented Oct 11, 2018

我有一个应该比较笨的问题,为什么第i次的尝试次数为1 + max(i-1, f{n-i}),这个公式里面为什么取得是i-1和f{n-i}的较大值呢?在不知道第i次碎或者没碎的情况下,就为什么取得是最大值呢?

@ninjachen
Copy link

good gist. 不过想说两句,实际上这个策略最坏情况是12次吧, 14是105层。如果第一个鸡蛋每次尝试的成功后跳跃的层数是固定的,基本上最坏情况 - 也就是99层是碎掉的最底层 - 是稳定在19次。如果想最优化最坏情况,也就是那个楼层是99,那么要最小化最后一个step尝试的机会,那么是用你这个这个算法,不过牺牲了其他非最坏情况的次数。 http://datagenetics.com/blog/july22012/index.html 这里有非常详细的讲解。

感谢分享,这个说的比较直观

@ShaneTian
Copy link

good gist. 不过想说两句,实际上这个策略最坏情况是12次吧, 14是105层。如果第一个鸡蛋每次尝试的成功后跳跃的层数是固定的,基本上最坏情况 - 也就是99层是碎掉的最底层 - 是稳定在19次。如果想最优化最坏情况,也就是那个楼层是99,那么要最小化最后一个step尝试的机会,那么是用你这个这个算法,不过牺牲了其他非最坏情况的次数。 http://datagenetics.com/blog/july22012/index.html 这里有非常详细的讲解。

最坏是 14 次啊,那个 12 说的是要是鸡蛋没碎,才能不断增加楼层,那要是第一个鸡蛋就在 14 层碎了呢?不就 1+13=14 了么?
求的是最坏情况

@by415304229
Copy link

good gist. 不过想说两句,实际上这个策略最坏情况是12次吧, 14是105层。如果第一个鸡蛋每次尝试的成功后跳跃的层数是固定的,基本上最坏情况 - 也就是99层是碎掉的最底层 - 是稳定在19次。如果想最优化最坏情况,也就是那个楼层是99,那么要最小化最后一个step尝试的机会,那么是用你这个这个算法,不过牺牲了其他非最坏情况的次数。 http://datagenetics.com/blog/july22012/index.html 这里有非常详细的讲解。

感谢分享,这个说的比较直观

原文说的挺好的,但是楼上的出12的的结论是错的。。。。
最坏情况仍然是14。最坏情是12况是建立在14层没摔碎的条件下的。即86层,2个蛋的问题的答案。。。

@ninjachen
Copy link

原文说的挺好的,但是楼上的出12的的结论是错的。。。。

我又看了一遍,发现你和楼主说的对!哈哈哈哈不知道上次怎么想的

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment