Contents
  1. 1. 扔瓶子测楼层
  2. 2. A. 只用一个瓶子从第一层扔到第n层
  3. 3. B. 用贪心的思维
  4. 4. C. 用二分法
  5. 5. D. 数学推算
  6. 6. E. DP的解法
  7. 7. F. 推广到一般化的问题
  8. 8. Reference

扔瓶子测楼层

一栋楼有n层,需要测试某种材质的玻璃瓶从哪一层掉下来恰好会碎。现在仅有两个这样的瓶子。请问怎样仍才能最快的测出楼层的临界值?

A. 只用一个瓶子从第一层扔到第n层

找到临界值的扔瓶子次数的期望为每一层的期望次数之和

1
E(x) = 1/n * 1 + 1/n * 2 + 1/n * 3 + ... + 1/n * n = (1+n)/2

所以时间复杂度是O(n)

B. 用贪心的思维

第一个瓶子从第1层开始扔,每次层数翻倍,依次为,1,2,4,8,16,直至在第 2^k 层碎掉。
第二个瓶子从第 2^(k-1) 层开始扔,直至第 2^k 层为止,中间肯定能找到临界值。
所以时间复杂度是O(lgn)

C. 用二分法

第一个瓶子每次以(i, j)为区间,扔的位置为(i+j)/2, 初始情况, i=0,j=n, 如果瓶子没碎,则i=j,直至碎掉。
第二个瓶子从第 i 层开始扔,直至第 j 层为止,中间肯定能找到临界值。

对于第 i 层,扔的情况为:

  • 第一个瓶子:n/2, $/2+n/4 i, n/2+n/4+n/8
  • 第二个瓶子:n/2+n/4, (n/2+n/k+1), …, i

显而易见,时间复杂度是O(n)

D. 数学推算

这个题目是需要最快的找出临界值,可以转换为,即使在最坏的情况下,也能最快地找出临界值。

我们先假设最坏情况下,瓶子下落次数为x,即我们为了找出N,一共用瓶子做了x次的实验。

那么,我们第一次应该在哪层楼往下扔瓶子呢?

先让我们假设第一次是在第y层楼扔的瓶子,如果第一个瓶子在第一次扔就碎了,我们就只剩下一个瓶子,要用它准确地找出N,只能从第一层向上,一层一层的往上测试,直到它摔坏为止,答案就出来了。

由于第一个瓶子在第y层就摔破了,所以最坏的情况是第二个瓶子要把第1到第y-1层的楼都测试一遍,最后得出结果,噢,原来瓶子在第y-1层才能摔破(或是在第y-1层仍没摔破,答案就是第y层。) 这样一来测试次数是1+(y-1)=x,即第一次测试要在第x层。

OK,那如果第一次测试鸡蛋没摔破呢,那N肯定要比x大,要继续往上找,需要在哪一层扔呢?我们可以模仿前面的操作,如果第一个瓶子在第二次测试中摔破了,那么第二个瓶子的测试次数就只剩下x-2次了(第一个瓶子已经用了2次)。这样一来,第二次扔瓶子的楼层和第一次扔瓶子的楼层之间就隔着x-2层。

我们再回过头来看一看,第一次扔瓶子的楼层在第x层,第1层到第x层间共x层;第1次扔鸡蛋的楼层到第2次扔瓶子的楼层间共有x-1层(包含第2次扔瓶子的那一层),同理继续往下,我们可以得出,第2次扔瓶子的楼层到第3次扔瓶子的楼层间共有x-2层,最后把这些互不包含的区间数加起来,应该大于等于总共的楼层数量100,即

1
2
3
x + (x-1) + (x-2) + ... + 1 >= 100
(x+1)*x/2 >= 100
得出答案是14

即我先用第1个瓶子在以下序列表示的楼层数不断地向上测试,直到它摔破。 再用第2个瓶子从上一个没摔破的序列数的下一层开始,向上测试,即可保证在最坏情况下也只需要测试14次,就能用2个瓶子找出从哪一层开始,往下扔鸡蛋,瓶子就会摔破。

1
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

E. DP的解法

假设f(n)表示从第n层楼扔下鸡蛋,没有摔碎的最少尝试次数。第一个鸡蛋,可能的落下位置[1,n],第一个鸡蛋从第i层扔下,有两种情况:

  • 碎了,第二个鸡蛋,需要从第一层开始试验,有i-1次机会
  • 没碎,两个鸡蛋,还有n-i层。这个就是子问题了f(n-i)

所以,当第一个鸡蛋,由第i个位置落下的时候,要尝试的次数为 1 + max{i - 1, f(n - i)},那么对于每一个i,尝试次数最少的,就是f(n)的值。
状态转移方程如下:

1
f(n) = min{1 + max{i - 1, f(n - 1)}}

其中: i的范围为[1, n], f(1) = 1.

F. 推广到一般化的问题

为n层楼,m个鸡蛋。
如下分析: 假设f(n,m)表示n层楼、m个鸡蛋时找到最高楼层的最少尝试次数。当第一个鸡蛋从第i层扔下,有两种情况:

  • 碎了,还剩m-1个鸡蛋,为确定下面楼层中的安全楼层,还需要f(i-1,m-1)次,找到子问题
  • 不碎,上面还有n-i层,还需要f(n-i,m)次,又一个子问题。

状态转移方程如下:

1
f(n, m) = min{1 + max{f(n - 1, m - 1), f(n - i, m)}}

其中: i为[1, n], f(i, 1) = 1

Reference

http://www.cricode.com/3558.html
https://gist.github.com/sing1ee/5971946

Contents
  1. 1. 扔瓶子测楼层
  2. 2. A. 只用一个瓶子从第一层扔到第n层
  3. 3. B. 用贪心的思维
  4. 4. C. 用二分法
  5. 5. D. 数学推算
  6. 6. E. DP的解法
  7. 7. F. 推广到一般化的问题
  8. 8. Reference