google曾有个面试题说给你两个鸡蛋,在一个100层楼上测试鸡蛋掉下摔碎的临界高度,以楼层计算,问你最少的尝试次数。
当时因为只有两个鸡蛋所以答案很简单那就是14次。
思路如下:假设至少需要尝试x次,则第一次在第x层扔下,如果摔碎了,则还有一个鸡蛋则最大需要再逐个尝试1-(x-1)层即可,若未摔碎,则此时还是两个鸡蛋,只需要在x+(x-2)层扔即可,因为这样如果碎了,只需要尝试x-2次,如果没碎则需要再尝试x-2次,一次类推,两个鸡蛋可检测的楼层为x+(x-2)+(x-3)+…+1层时,检测次数最小为x次,另x+(x-2)+(x-3)+…+1>=100即可算出x最小为14,现在扩展一下,假设有n个鸡蛋m层楼,问你至少需要多少次尝试就能测出鸡蛋的临界高度。
请编程实现。
分析这其实是一个动态规划问题,dp[i][j]为i个鸡蛋在j层楼需要最少尝试的次数,状态转移题目中有解释。
代码:
#include <iostream> #include <cstdio> using namespace std; const int M=200; const int N=200; int dp[M+1][M+1]; int main () { int m,n; memset(dp,0,sizeof(dp)); for (int i=1;i<=N;i++) { dp[1][i]=i; } for (int i=2;i<=M;++i) { for (int j=1;j<=N;++j) { dp[i][j]=1+dp[i][j-1]; for (int k=2;k<=j;++k) { //此处dp[i-1][k-1]表示第k层扔鸡蛋碎了则还有i-1个鸡蛋需要最多尝试k-1层(1-i-1) //dp[i][j-1]表示第k层扔鸡蛋没碎,则还有i个鸡蛋只需要尝试k+1到j层即可所以为j-k层 //这两种情况选出最坏情况加上本次操作即可 dp[i][j]=min(dp[i][j],1+max(dp[i-1][k-1],dp[i][j-k])); } } } while (scanf("%d%d",&m,&n)!=EOF) { printf("%d\n",dp[m][n]); } return 0; }
您还没有登录,请您登录后再发表评论
Java面试题必备——Java基础知识部分汇总,面试者必备的哦
2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端...
java面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏...
2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端...
领导干部公选面试题总结——组织活动类.doc
公务员面试题之——谈谈你的看法.pdf
2024年秋招and春招面试真题——中软.txt2024年秋招and春招面试真题——中软.txt2024年秋招and春招面试真题——中软.txt2024年秋招and春招面试真题——中软.txt2024年秋招and春招面试真题——中软.txt2024年秋招and...
领导干部公选面试题总结——领导科学方法类.doc
2024春招面试真题——鑫合易家java初级试卷1-题目.docx2024春招面试真题——鑫合易家java初级试卷1-题目.docx2024春招面试真题——鑫合易家java初级试卷1-题目.docx2024春招面试真题——鑫合易家java初级试卷1-题目....
Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案
c面试题,用于准备面试笔试非常好 1). 标识#define在宏中应用的基本知识。这是很重要的,因为直到嵌入(inline)操作符变为标准C的一部分,宏是方便产生嵌入代码的唯一方法,对于嵌入式系统来说,为了能达到要求的...
中兴通讯唯一可与华为相提并论的企业,与思科、诺基亚齐名。其试题亦体现了国际企业的风范,IT界很多公司都用中兴的面试题。对你的实际作用远远大于期望值!!!
最全面的java面试题——选择题部分
CCNA面试题——网络工程师
一、Java基础知识 1.Java有那些基本数据类型,String是不是基本数据类型,他们有何区别。 答案: 8种基本类型 char byte short int long float double boolean String和他们的区别你从首字母就能看出来了,String的...
这是java程序员面试题的总结,非常经典,来自于河南省863软件孵化器有限公司。对于有一定技术,面试却总是失败的朋友很有帮助。
2022前端面试系列——Vue面试题.pdf
UC面试题,里面包含uc经典面试题,是准备找uc工作的人的首选。
世界500强面试题 25年面试官首次揭秘——世界500强面试题(精彩选载)
HCIE面试题——LAN&WAN 技术.docx
相关推荐
Java面试题必备——Java基础知识部分汇总,面试者必备的哦
2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端最新面试题——Vue篇2023前端...
java面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏骏环昇旺科技.jpgjava面试真题——江苏...
2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端最新面试题——Vue篇.docx2023前端...
领导干部公选面试题总结——组织活动类.doc
公务员面试题之——谈谈你的看法.pdf
2024年秋招and春招面试真题——中软.txt2024年秋招and春招面试真题——中软.txt2024年秋招and春招面试真题——中软.txt2024年秋招and春招面试真题——中软.txt2024年秋招and春招面试真题——中软.txt2024年秋招and...
领导干部公选面试题总结——领导科学方法类.doc
2024春招面试真题——鑫合易家java初级试卷1-题目.docx2024春招面试真题——鑫合易家java初级试卷1-题目.docx2024春招面试真题——鑫合易家java初级试卷1-题目.docx2024春招面试真题——鑫合易家java初级试卷1-题目....
Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案Java面试题和答案
c面试题,用于准备面试笔试非常好 1). 标识#define在宏中应用的基本知识。这是很重要的,因为直到嵌入(inline)操作符变为标准C的一部分,宏是方便产生嵌入代码的唯一方法,对于嵌入式系统来说,为了能达到要求的...
中兴通讯唯一可与华为相提并论的企业,与思科、诺基亚齐名。其试题亦体现了国际企业的风范,IT界很多公司都用中兴的面试题。对你的实际作用远远大于期望值!!!
最全面的java面试题——选择题部分
CCNA面试题——网络工程师
一、Java基础知识 1.Java有那些基本数据类型,String是不是基本数据类型,他们有何区别。 答案: 8种基本类型 char byte short int long float double boolean String和他们的区别你从首字母就能看出来了,String的...
这是java程序员面试题的总结,非常经典,来自于河南省863软件孵化器有限公司。对于有一定技术,面试却总是失败的朋友很有帮助。
2022前端面试系列——Vue面试题.pdf
UC面试题,里面包含uc经典面试题,是准备找uc工作的人的首选。
世界500强面试题 25年面试官首次揭秘——世界500强面试题(精彩选载)
HCIE面试题——LAN&WAN 技术.docx