记得有一道常见的面试题是问:有两个完全一样的玻璃球,从某一高度摔下会碎,问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;
}
分享到:
相关推荐
投掷玻璃球问题的C语言程序 投掷玻璃球问题的C语言程序
这是一个关于PHOTOSHOP中透明玻璃球制作过程的图片教程
自己整理的.华丽的photoshop 玻璃球 教程
外国的OpenGL 折射 实例,一个玻璃球,包含了折射、色散
同济大学嵌入式课程的作品 基于WinCE,用C#完成, 包含所有项目文档和源代码
蓝色玻璃球,科技感,3D立体网格背景ppt模板。
Photoshop画玻璃球
玻璃球PPT模板适用于清新动感主题设计应用。
玻璃球消洗机电路图pdf,玻璃球消洗机电路图
绿草地上透明玻璃球,淡雅绿背景,夏日清凉幻灯片模板。
圣诞玻璃球flash动画是一款圣诞节礼物玻璃球动画素材下载。
制造玻璃管棒纤维及玻璃球的设备.pptx
绘制质感透明玻璃球PPT教程。为了让主体有磨砂的质感,填充的时候选取斜纹图案,再选择相近的两种深蓝色为前景后景,前景稍浅,后景较深。边缘发光的效果用内阴影来代替,主要注意阴影颜色,透明度,还有模糊的设置 ...
蓝色玻璃球网状立体背景PPT模板.pptx
Photoshop打造逼真的透明玻璃球体
玻璃球淡雅绿炎热夏日清凉PPT模板.pptx
用Photoshop打造玻璃球中的漂亮MM
以硅胶、平均粒径为5μm的玻璃粉和碳酸氢钠为原料,通过调整硅胶、玻璃粉和碳酸氢钠的质量比制成直径为2 cm左右的小球,焙烧后得到了有一定强度并能浮在水面上的多孔玻璃球。在一定浓度的TiO2溶胶中将此多孔玻璃球...
行业文档-设计装置-半潜式玻璃球洒水喷头.zip
吊着的玻璃球摆动flash动画是一款卡通吊球随机摇摆动画下载。