UC知道Google面试题？
来源：百度知道 编辑：UC知道 时间：2024/05/26 18:30:06
有一幢100层高的大厦，给你两个完全相同的玻璃围棋子。假设从某一层开始，丢下玻璃棋子就会摔碎。那么怎么利用手中的两颗棋子，用一种什么样的最优策略，知道这个临界的层高呢？
答案是先从14楼开始抛第一次；如果没碎，再从27楼抛第二次；如果还没碎，再从39楼抛第三次；如果还没碎，再从50楼抛第四次；如此，每次间隔的楼层少一层。这样，任何一次抛棋子碎时，都能确保最多抛14次可以找出临界楼层。
证明如下：
1、第一次抛棋子的楼层：最优的选择必然是间隔最大的楼层。比如，第一次如果在m层抛下棋子，以后再抛棋子时两次楼层的间隔必然不大于m层（大家可以自己用反证法简单证明）
2、从第二次抛棋子的间隔楼层最优的选择必然比第一次间隔少一层，第三次的楼层间隔比第二次间隔少一层，如此，以后每次抛棋子楼层间隔比上一次间隔少一层。（大家不妨自己证明一下）
3、所以，设n是第一次抛棋子的最佳楼层，则n即为满足下列不等式的最小自然数：
不等式如下： 1+2+3+...+(n-1)+n >= 100
由上式可得出n=14
即最优的策略是先从第14层抛下，最多抛14次肯定能找出临界楼层。