算法系列之第九届蓝桥杯Java B组第四题测试次数
题目:测试次数
x星球的居民脾气不太好,但好在他们生气的时候唯一的异常举动是:摔手机。
各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试,并且评定出一个耐摔指数来,之后才允许上市流通。
x星球有很多高耸入云的高塔,刚好可以用来做耐摔测试。塔的每一层高度都是一样的,与地球上稍有不同的是,他们的第一层不是地面,而是相当于我们的2楼。
如果手机从第7层扔下去没摔坏,但第8层摔坏了,则手机耐摔指数=7。
特别地,如果手机从第1层扔下去就坏了,则耐摔指数=0。
如果到了塔的最高层第n层扔没摔坏,则耐摔指数=n
为了减少测试次数,从每个厂家抽样3部手机参加测试。
某次测试的塔高为1000层,如果我们总是采用最佳策略,在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢?
请填写这个最多测试次数。
注意:需要填写的是一个整数,不要填写任何多余内容。
思路:
说实话,当时小编看到这个题目时候,上来就理解错了,以为是抽取的是三款手机进行测试,
因此立马想到了二分法,1000 500 250 125 62 31 15 7 3 1 答案是10
可是怎么会这么简单,又仔细读了一下题目,“从每个厂家抽样3部手机参加测试”,只有三部手机,只有三部手机!!!进行测试,因此立即转换了思路,经过一阵时间的思考,得到了28的答案。思路如下。
将1000层楼,先用第一个手机在100 200 300 400 500 600 700 800 900 1000依次进行试验,如果在某个层数如果摔碎,则将这中间的100个数分成
10 20 30 40 50 60 70 80 90,就用第二部手机在第一部的上一层+10进行试验(如;在第一部手机在300层处摔坏,那么第二部手机就,210开始测试),如果在这一百个数内摔坏,则将摔坏的层数与摔坏层数-10这中间的10个数,分成1 2 3 4 5 6 7 8 9,再用第三部手机进行测试,这样就可以测试出耐摔指数。题目又说了:在最坏的情况下,那测试指数是988层(3个手机全用)998层(只用两个手机就能测出来)应该就是最坏的情况了100 200 300 400 500 600 700 800 900 1000 共测试10次,在1000层第一个手机碎了,再用第二部手机从910层测 910 920 930 940 950 960 970 980 990,共9次,第二部手机在990层碎,再用第三部手机从991开始测试,981 982 983 984 985 986 987 988 989,共9层,在989层碎了,因此耐摔指数是988,共计测试次数是:10+9+9=28次。
代码如下:
package 第九届蓝桥杯;
public class 第四题测试次数 {
public static void main(String[] args) {
int a=999;//设置最坏情况下的耐摔指数+1
int count=0;//测试次数
int first[]={100,200,300,400,500,600,700,800,900,1000};
int second[]={10,20,30,40,50,60,70,80,90};
int third[]={1,2,3,4,5,6,7,8,9};
for(int i=0;i<first.length;i++){
if(a<first[i]){
count++;
a=a-first[i-1];
break;
}
count++;
}
for(int i=0;i<second.length;i++){
if(a<second[i]){
count++;
a=a-second[i-1];
break;
}
/*if(i==second.length-1&&a>second[second.length-1]){
count++;
a=a-second[second.length-1];
break;
}*/
count++;
}
for(int i=0;i<third.length;i++){
if(a<third[i]){
count++;
break;
}
count++;
}
System.out.println(count);
}
}
当然还有最后某些大佬用动态规划算出来的19,是真心木有理解,但小编会努力理解的~
动态规划思路:先思考如果只有两个手机,100层楼,应该怎么摔。 假设最多摔x次。第一次肯定摔x层,第二次摔x+x-1层,……第n次摔x*n-n+1层,这样能保证最多摔x次。第一次摔x层,如果摔碎了,从第一层开始摔,正好x次。如果第x层没碎,摔x+x-1层,如果碎了,从x+1开始摔,做多也是x次。
一共就是1+2+3+4+……x>=100 x=14
如果三个手机怎么办?
把两层的摔的结果保存下来,a[1]=1,a[2]=3,a[3]=6……
a[1]+a[2]+a[3]+……a[x]>=1000 x=18
第一次摔第a[18]层如果碎了,最多再摔18次,所以结果是19次。
结语:大佬们的脑子就是和别人的不一样~~~
补充:
昨天的复数幂的代码出现了乱码,先纠正如下:
package 第九届蓝桥杯;
/**
* @author 小萝卜头
*
*/
public class 第三题复数幂 {
public static void main(String[] args) {
long a=2,fir=2;
long b=3,sed=3;
long c=0,thi=0;
for(int i=2;i<=7;i++){
thi=-(b*sed);
//System.out.print(thi+" ");
sed=a*sed+b*fir;
//System.out.print(sed+" ");
fir=a*fir+thi;
//System.out.println(fir+" ");
}
if(sed>=0)
System.out.println(fir+"+"+sed+"i");
else{
System.out.println(fir+""+sed+"i");
}
}
}