Abo

腾讯面试题--厉害了我的杯

杯具题:厉害了我的杯 🙄

阅读理解:一个杯子定区间,一个杯子定位置,关键在于区间怎么划分。

wallhaven-gjmwz7

问题

有一种玻璃杯质量确定但未知,需要检测。
有一栋100层的大楼,该种玻璃杯从某一层楼扔下,刚好会碎。
现给你两个杯子,问怎样检测出这个杯子的质量,即找到在哪一层楼刚好会碎?

思考

  • 2 个杯子的脆弱程度是一样的

  • 如果杯子从 N 楼扔下来没有碎,那么它从小于 N 楼扔下来,也不会碎

  • 如果杯子从 N 楼扔下来碎了,那么它从大于 N 楼扔下来,也一定会碎

  • 一个扔出去但没有碎的杯子,可以继续被用于试验

  • 碎了的杯子将无法再继续试验。

    问题的关键是,怎么快速找到这个楼层呢?这是一个查找问题。
    我们需要一个策略方法来快速地找到它,就看谁的方法比较优秀拉。
    而优秀的方法其评价标准显而易见:各种情况下都能快速地找到目标楼层。

再度思考

如果只有一个杯子的话,应该怎么做呢?
稍微想一下也可以知道,必定只能一层一层地扔,1楼没碎扔2楼,2楼没碎扔3楼,直到碎掉。

现在我有两个杯子。

学习过算法和程序的人应该都知道二分法,很容易想到这样去做,因为面对的是一个搜索问题。
所以可能会给出这样的策略:
从50楼扔下,没碎的话,再扔75楼,再没碎我扔88楼,依次下去很快就可以锁定楼层?
很快你会意识到问题所在,万一第一次从50层楼扔下去,碎了咋整,难道又一层一层地扔?
杯子的质量是刚好在49层碎掉的话。最差的情况我需要扔50次,这方法不行。

再一个比较常见的方法是,先分区间的扔,再慢慢地一层一层地扔,隐含着分段查找的策略。
具体操作方式是:
先从第10楼扔,再从第20楼扔,依次下去,如果到某一层碎掉,比如50层碎掉了,我再从41楼开始扔,这样的话应该算是比较快了把?
这个方法是要快一点不过如果我杯子的质量比较好,在99楼才会刚好碎掉。
这样,最差的情况下,需要扔19次才能找到目标楼层,还是不能让面试官满意。

我们需要的方法是无论杯子的质量如何,不论是在1楼碎,49楼碎,99楼碎都要能快速锁定的方法。

继续思考刚才方法的缺陷,当杯子质量比较差的时候,此方法还是比较快速的找到的。比如杯子是在19楼刚好碎,我只需要扔11次,比99楼刚好碎的情况要少很多次。

所以我们的愿望是:
杯子的质量无论分布在哪个查找区间,都可以快速地找到。所以我想到的是可以“匀”一下刚才的方法。即最开始我需要大胆地扔,然后再慢慢小心地扔。

具体方法设计:
每次扔的区间减少一层,这样做可以保证每个区间查找的最差次数是一样的。
假定第一步在15楼扔,没碎的话则下一步在29楼扔,没碎下一步在42楼扔….碎掉之后则在上一次没碎的楼层开始向上扔。那么最开始在哪一层开始扔呢??
这里我们需要拿支笔算一下:
x+(x-1)+(x-2)+…+2 >=100
求解出答案为14。

即最终给出的解决方案是:
最开始从14楼开始扔,没碎的话在27楼扔,再没碎的话在39楼扔…..一旦碎掉,则从上一次没碎的楼层逐层往上扔,即可快速确认杯子在哪一层刚好会碎掉。

这样的方法可以保证在最差的情况下也能在14次内找到楼层,平均需要的次数不到10次。
(列式子算了下期望是9次多)

整理方案

方案一:二分法

从 50 楼扔下,没碎的话,再扔 75 楼,再没碎我扔 88 楼,依次下去貌似很快就可以锁定楼层。

不过,很不巧,第一次从 50 层楼扔下去就碎了,这个时候就只能从 1 层开始慢慢的的一层一层地扔,如果杯子的质量是刚好在 49 层碎掉的话,那么最差的情况是需要扔 50 次。

方案二:分段查找区间法

核心点:先分区间的扔,再慢慢地一层一层地扔。

举个🌰:先从第 10 楼扔,再从第 20 楼扔,依次下去,如果到某一层碎掉,比如 60 层碎掉了,我再从 51 楼开始扔,这样比前面的二分法更快,因为即使又很不巧,杯子的质量比较好,在 99 楼才会刚好碎掉。这样的话,在这种最差的情况下,也只需要扔 19 次就能找到目标楼层。

方案三:基于数学方程的方法

事实上,这算是一道趣味问题,可以从数学的角度进行分析。

假设最少尝试次数为 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 次。

方案四:动态规划

先思考上面的 分段查找区间法 ,如果杯子的质量没那么好,在第 19 层就碎了,那么需要扔 11 次,这样比 99 楼刚好碎的情况要少很多次。

那么问题来了:能否无论杯子的质量如何,不管是很好还是很差,都可以快速地找到。

能!

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

事实上,这就是一个求最优解的问题了。

而我们编程解决问题的过程中,如果遇到最优问题的时候,往往可以先尝试一下动态规划的方法。

动态规划的一个出发点就是去 找到构成这个最优问题的最优子问题

我们可以将这样的问题简记为 W(n,k) ,其中 n 代表可用于测试的杯子数,k 代表被测试的楼层数。对于问题 W(2,10), 我们可以如此考虑

  • 将第 1 个杯子,在第 i 层扔下( i 可以为 1~k 的任意值),如果碎了,则我们需要用第 2 个杯子,解决从第 1 层到第 i-1 层楼的 子问题 W(1,i-1)
  • 如果这个杯子没碎,则我们需要用这两个杯子,解决从 i+1 层到第 100 层的子问题 W(2,100-i)。

解决这两个问题,可以分别得到一个尝试次数 p 与 q,我们取这两个次数中的较大者(假设是 p ),将 p 与第 1 次在 i 层执行测试的这一次相加,则 p+1 就是第一次将杯子扔在 i 层来解决 W(2,100) 所需的最少测试次数,将其表示为ti

对于这 100 层楼的问题,第一次,我们可以把杯子扔在 100 层中的任何一层,所以可以得到 100 中解决方案的测试次数 T{t1,t2,t3,……,t100} ,在这些结果中,我们选取最小的 ti,使得对于集合 T 中任意的值 tj(1 <= j <= 100,j != i),都有ti <= tj,则 ti 就是这个问题的答案。

用公式来描述就是:

1
W(n, k) = 1 + min{max(W(n -1, x -1), W(n, k - x))}, x in {2, 3, ……,k}

其中x是第一次的测试的楼层位置

其中W(1,k) = k(相当于 1 个杯子测试 k 层楼问题),W(0,k) = 0,W(n, 0) = 0

所以在计算 W(2,100) 之前,我们需先计算出所有 W(1,0) ,……, W(1,100) , W(2,0),……,W(2,99)这些的值。

使用递推的方法实现,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
unsigned int DroppingCups(unsigned int cups, unsigned int floors){
unsigned int i, j, k, t, max;
unsigned int temp[cups + 1][floors + 1];
for(i = 0; i < floors + 1; ++i){
temp[0][i] = 0;
temp[1][i] = i;
}
for(i = 2; i < cups + 1; ++i){
temp[i][0] = 0;
temp[i][1] = 1;
}
for(i = 2; i < cups + 1; ++i){
for(j = 2; j < floors + 1; ++j){
for(k = 1, max = UINT_MAX; k < j; ++k){
t = temp[i][j-k]>temp[i - 1][k -1]? temp[i][j - k]:temp[i - 1][k -1];
if(max > t){
max = t;
}
}
temp[i][j] = max + 1;
}
}
return temp[cups][floors];
}