关键词:抛小球,抛鸡蛋,楼层
恩,是有关键词,为了让搜索引擎找到这个文章。
题目的原型是这样的:
有100层楼,给你两个玻璃球,在某一层楼R将球扔下,球会碎,而R-1楼就不会碎,设计一个方案,确保找到这个R,这个方案最少要尝试多少次。
这是个相当相当经典的公司面试笔试题目,目前网上流传各种版本。其他版本还包括300层楼,3个球等等。总之实际上这个问题对于要找工作的同学来说,是有好好琢磨一下的必要的。
首先,我们先考虑一个更为一般,但更为直接的问题:如果给你n个球,允许你尝试不超过k次,那么最多你能检查多少层楼?(看出这个问题和上面那个问题的关系了吧)
在解决[……]