扔玻璃球的问题
记得有一道常见的面试题是问：有两个完全一样的玻璃球，从某一高度摔下会碎，问100层高的楼最多扔几次可以测出来在那一层扔时玻璃球恰好碎。
为了能测出来在那一层碎，如果第一个球碎了的话第二个球就要从已测未碎的最高的一层开始，一层一层的向上仍，所以问题就是第一次应该扔在第几层，如果没有碎，那么下一次要和上一次隔多少层。隔一样多层肯定不对，因为如果第一个碎了，那么第二个最差情况就要仍和在上一步碎一样多的次数，而他已经比上一次最差情况多仍一次了。所以应该是每一次间隔减一，来弥补第一个球多仍的次数。最后求出来就是最多扔14次即可。
这个问题看上去还是比较简单的，往后一想，如果是三个球或者是k个球呢。
其实这是一道动态规划的问题，换一个问法就是，有n个球扔k次，最多可以测出在多少层内碎的情况，比如一个球仍十次，最多可以测出十层以内的情况，两个球扔10次最多可以测出104层以内的情况，100个球扔两次最多可以测出3层以内的情况，通项就是: f(n,k) = 1 + f(n-1,k-1) + f(n,k-1);
贴出段代码，打印出你n<=10,k<=30，时的全部情况
//扔球问题
#include <iostream>using namespace std;int data[10][30];int main(){for(int i = 0; i<30 ;i++)data[0][i] = i+1 ;for(int i = 1; i<10;i++)data[i][0] = 1;for(int i = 1; i<10 ;i++)for(int j = 1;j<30;j++){data[i][j] = 1 + data[i][j-1] + data[i-1][j-1] ;}for(int i = 0; i<10 ;i++){for(int j = 0;j<30;j++){cout<<data[i][j]<<'\t';}cout<<endl;}return 0;}? 1 楼 chenjiankun18 2011-04-21 不用二分法吗 2 楼 java_林 2011-04-21 chenjiankun18 写道不用二分法吗