谷歌公司有道面试题：有一个100层高的大厦，从这个大厦的某一层扔下棋子恰好就会碎（称这一层为临界层）。请你用手中的两个玻璃围棋子，找出一个最优的策略来得知那个临界层。 解法：假设在最坏情况下投掷的最少次数为x,即无论临界层为几，投掷次数都小于等于x。那么我第一次投掷的楼层为x，此时有两种情况： （1）围棋子碎了：用第二个围棋子从1到x-1投掷，最多一共投掷x次可以确定临界层。 （2）围棋子没有碎：此时投掷次数剩下x-1次，那么我就在x+(x-1)层楼处投掷玻璃球。 最坏情况下是围棋子一直没有碎，剩下的投掷次数为0，为了能够确定临界层，必须满足： x+(x-1)+(x-2)+…+2+1>=100； 该式子表示我投掷次数用完了，我检查的楼层数必须要在100以上，不然我不知道临界层，因此解得x>=14。 拓展： 对于m层楼高，k个球的扔棋子问题，又该怎么做？ 答案是用动态规划的思想：如果是三个棋子，100层楼，我扔了一次棋子碎了以后，就变成2个棋子的问题了，因此可以利用上面的结果： （x*(x-1)/2）+((x-1)*(x-2)/2)+…+3+1>=100. 对于m层楼，k个棋子，问题相当于： 已知m,k，求解不等式： 编写程序很快就可以把n的最小值(最小投掷次数)算出来。 算法证明：对m层楼，k个棋子的问题，存在复杂度为O(m^(1/k))的算法。 证明方法可用数学归纳法，详见：m层楼k个鸡蛋问题的算法复杂度证明。
参考链接（打开网页后第一个）
