一道很有意思的面试题目

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

分析:

首先理解题意,将这个杯子从某一层楼扔下,如果没碎,我还可以再利用它测试。如果碎了的话,就不能再继续用了。如果我从x楼扔下,没碎,在x+1楼扔下,碎掉了,即证明找到了x+1是刚好碎掉的楼层。问题的关键是,怎么快速找到这个楼层呢?这是一个查找问题。我们需要一个策略方法来快速地找到它,就看谁的方法比较优秀拉。而优秀的方法其评价标准显而易见:各种情况下都能快速地找到目标楼层。

思考路径:

如果只有一个杯子的话,应该怎么做呢?

稍微想一下也可以知道,必定只能一层一层地扔,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次多)这是我知道的最好的方法。

有意思。

FORM 时宇电 ZHIHU.COM