Java实现第九届蓝桥杯耐摔指数

题目描述

x星球的居民脾气不太好&＃xff0c;但好在他们生气的时候唯一的异常举动是&＃xff1a;摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试&＃xff0c;并且评定出一个耐摔指数来&＃xff0c;之后才允许上市流通。

x星球有很多高耸入云的高塔&＃xff0c;刚好可以用来做耐摔测试。塔的每一层高度都是一样的&＃xff0c;与地球上稍有不同的是&＃xff0c;他们的第一层不是地面&＃xff0c;而是相当于我们的2楼。

如果手机从第7层扔下去没摔坏&＃xff0c;但第8层摔坏了&＃xff0c;则手机耐摔指数&＃61;7。
特别地&＃xff0c;如果手机从第1层扔下去就坏了&＃xff0c;则耐摔指数&＃61;0。
如果到了塔的最高层第n层扔没摔坏&＃xff0c;则耐摔指数&＃61;n

为了减少测试次数&＃xff0c;从每个厂家抽样3部手机参加测试。

如果已知了测试塔的高度&＃xff0c;并且采用最佳策略&＃xff0c;在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢&＃xff1f;

输入数据&＃xff0c;一个整数n&＃xff08;3 输出一个整数&＃xff0c;表示最多测试多少次。

例如&＃xff1a;
输入&＃xff1a;
3

程序应该输出&＃xff1a;
2

解释&＃xff1a;
手机a从2楼扔下去&＃xff0c;坏了&＃xff0c;就把b手机从1楼扔&＃xff1b;否则a手机继续3层扔下

再例如&＃xff1a;
输入&＃xff1a;
7

程序应该输出&＃xff1a;
3

解释&＃xff1a;
a手机从4层扔&＃xff0c;坏了&＃xff0c;则下面有3层&＃xff0c;b,c 两部手机2次足可以测出指数&＃xff1b;
若是没坏&＃xff0c;手机充足&＃xff0c;上面5,6,7 三层2次也容易测出。

资源约定&＃xff1a;
峰值内存消耗&＃xff08;含虚拟机&＃xff09; <256M
CPU消耗 <1000ms

请严格按要求输出&＃xff0c;不要画蛇添足地打印类似&＃xff1a;“请您输入…” 的多余内容。

所有代码放在同一个源文件中&＃xff0c;调试通过后&＃xff0c;拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是&＃xff1a;Main&＃xff0c;否则按无效代码处理。

笨笨有话说&＃xff1a;
我觉得3个手机太难了&＃xff0c;要是2个手机还可以考虑一下。

歪歪有话说&＃xff1a;
想什么呢&＃xff0c;你&＃xff01;要是1部手机还用你编程啊&＃xff1f;那样的话只好从下往上一层一层测。

PS&＃xff1a;
1、动态规划&＃xff0c;化繁为简。
2、先假设只有两个手机那么最佳策略便是1&＃43;2&＃43;3&＃43;4&＃43;5&＃43;…&＃43;i>&＃61;n。即扔i次可以测出结果。
3、因为有三个手机所以用数组保存两个手机的结果&＃xff1b;x[0]&＃43;x[1]&＃43;x[2]&＃43;…x[i],>&＃61;n.即扔k次可以测出结果。

//java代码public static void main(String[] args){Scanner sc&＃61;new Scanner(System.in);int n&＃61;sc.nextInt();int [] x&＃61;new int [1000];int sum&＃61;1;for(int i&＃61;0;sum

不懂得话可以看一下这个