扔玻璃球的问题

记得有一道常见的面试题是问：有两个完全一样的玻璃球，从某一高度摔下会碎，问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;
}

 

评论

2 楼 java_林 2011-04-21  

chenjiankun18 写道

不用二分法吗

总共两个玻璃球，碎完就没了，二分法怎么用

1 楼 chenjiankun18 2011-04-21  

不用二分法吗