hg0088备用网址楼2个鸡蛋,如何得知鸡蛋能承受几层的撞击 – 霓裳依旧

hg0088备用网址楼2个鸡蛋,如何得知鸡蛋能承受几层的撞击 – 霓裳依旧

有一栋楼共hg0088备用网址,独一鸡蛋从楼上落下来就会分裂。, 议员席以下的议员席将不会坍塌。。我给你2个鸡蛋。,使杰出N的发明物,并确保在最坏的局面下, 放量缩减滑下量。 

让we的所有格形式先让最坏的局面。,落下的蛋数是X,换句话说,we的所有格形式在寻觅N。,用鸡蛋做X实验。。 这么,we的所有格形式最初的得在哪层楼把鸡蛋扔下去呢?先让we的所有格形式让最初的是在第y层楼扔的鸡蛋, 万一第独一鸡蛋最初的破损,它就会被破晓。,we的所有格形式只剩独一鸡蛋了。,we的所有格形式需求用它来正确地找出N。, 只从第苗圃开端。,管辖的范围最重要的水平。,直到它产生。,答案就暴露了。。 第独一鸡蛋在Y一楼破了。, 因而最坏的局面是次货个鸡蛋得率先受校样到Y-1 FL。,最不克不及够的,接收了总算。, 噢,鸡蛋在Y-1的苗圃分裂了,或许在Y-1上分裂了。,答案是层Y。。) 受校样次数为1 (Y-1)=X。,换句话说,第独一受校样是在X级。。OK, 那么,万一最初的鸡蛋缺少破损,,n霉臭大于x。,持续往上看。,我需求扔几层楼? we的所有格形式可以模拟先前的柄状物。,万一第独一鸡蛋在次货次实验中分裂,, 那么受校样的次货只鸡蛋的等同只X-2倍(第独一鸡蛋有B)。。 这样一来,次货层产蛋和最初的抛鸡蛋的舱口。 让we的所有格形式再回想一下。,一楼扔鸡蛋是在X级。,X层定居第苗圃和X层当中。; 第1次扔鸡蛋的议员席到第2次扔鸡蛋的议员席间公共用地x-1层(包括第2次扔鸡蛋的那苗圃), 同一的局面还在持续。,we的所有格形式可以画画,在次货层当中扔鸡蛋和第三个FLO当中有X-2层。, ……最不克不及够的,添加不包括的区间数。,它得大于或平稳的总议员席数100。,即

x + (x-1) + (x-2) + ... + 1 >= 100
(x+1)*x/2 >= 100

答案是14。。

换句话说,我先用第独一鸡蛋不时地受校样等同。,直到它产生。。 那么用次货个蛋从下独一不分裂的易碎的东西开端。,向上受校样, 您可以确保在最坏的局面下只需求受校样14次。,你可以用2个鸡蛋来找出哪苗圃开端。, 把鸡蛋扔下去,鸡蛋会破的。。

14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100

譬如,我破晓了第七十七层的第独一蛋。,那么我的次货只蛋开端在第七十层。,向上受校样, 次货只鸡蛋至多霉臭受校样7次(70)。,71,72,73,74,75,76),补充第独一鸡蛋受校样。 7次(14,27,39,50,60,69,77),最坏的局面不得不经过受校样14次来答复。。

这样地成绩也有非具体的的版本。,D层建造物,煽动,那么使杰出N的发明物, 在最坏的局面下放量缩减受校样次数。。这是要用的静态使突出(DP)来解。 

F [D] [E]代表D层。,煽动时,最坏局面受校样次数,则:

f[d] [e]=min {max(f[di-] [e]+1),F[I-1 ] [E-1] 1),i=1,2,…,d;

f[k][1]=k,0<=k<=d,f[0][0...e]=0;

创造密码列举如下:

int min_testnumber(int d, int e)  
{  
        int **f=new int *[d+1];  
        int i,j,k;  
        (I=0;I)<=d;i++)  
            f[i]=new int[e+1];  
        for(i=0;i<=d;i++)  
            f[i][1]=i;  
        for(i=0;i<=e;i++)  
            f[0][e]=0;  
        for(i=1;i<=e;i++)  
        {  
            for(j=1;j<=d;j++)  
            {  
                int tmp;  
                int min_test=0x7FFFFFFF;  
                for(k=1;k<=j;k++)  
                {  
                    tmp=f[j-k][i]+1>f[k-1][i-1]+1?f[j-k][i]+1:f[k-1][i-1]+1;  
                    if(tmp>min_test)  
                        min_test=tmp;  
                }  
                f[j][i]=min_test;  
            }  
       }  
       return f[d][e];  
}

两个鸡蛋又软又硬,但不变卖。,他们能够都在一楼分手。,它也能够从一百层落下来。。

有座hg0088备用网址的建造物,据我看来让你用这两个鸡蛋来决定哪个层是最重要的的PLA。。你可以破晓两个鸡蛋。。

无论如何需求数个受校样。,为了弄舱口碎鸡蛋?这样地展现到何种地步?

================================================= 

回答这样地成绩,从程序设计者的角度看,最简略的思惟办法是用静态P的思惟处理争端。,不外本文不将其从程序角度辨析,但从算学的角度来议论这样地成绩。。

 ================================================

对这样地成绩,原始成绩——hg0088备用网址楼,无论如何需求数个受校样。,为了弄舱口碎鸡蛋。,整齐的思索是不容易思索的。,不管怎样,万一we的所有格形式想对这样地成绩做独一相当折算。,这样地成绩简单明了答复。。亲自的以为,这种换衣服是处理这一成绩的胸部。,这样地替换是:

          替换成绩[两个鸡蛋。,举行K考试,高达几层。

万一we的所有格形式能把原始成绩瀑布替换成绩,就亲自的关于,成绩曾经处理了部份地。,替换后,这样地成绩顿时开悟了。,充实创意。

现时we的所有格形式将替换成绩对待模板。,有两个鸡蛋。,万一第独一鸡蛋破了,次货只鸡蛋霉臭举行一一的的考试。,并且,we的所有格形式命令K考试就将摔碎鸡蛋的议员席霉臭找到.

=====================================================

思索最初的受校样。。这是最初的。,第独一蛋不克不及放得太高。,不同的,万一第独一鸡蛋破了,次货个蛋能够茫然的那边。K考试后接收总算。但不克不及放得太短。,由于万一臀部很短,第独一鸡蛋坏了。,万一缺少破损,we的所有格形式糜费了一次受校样的机遇。,不克不及被说成一种彻底的糜费。,但无论如何它责怪功效最大值化。。因而,这是最初的。霉臭让第独一鸡蛋积蓄的中等身高。

中等身高是多高?高到万一第独一鸡蛋破了后次货个鸡蛋精确地能使筋疲力尽K考试接收总算这样地目的。由此可知,最初的实验的打倒高价地为k,万一最初的实验,第独一鸡蛋就坏了。,剩的就剩了。K-1层建造物,一级受校样,K次将管辖的范围目的。。

万一最初的受校样,第独一鸡蛋缺少碎。,现时we的所有格形式只K-1受校样机遇。,直到最不克不及够的。K楼和向楼下都是肯定的的。。we的所有格形式耗费了独一受校样机遇。,但我受校样过一次。K层楼。

那么只K-1机遇。,次货次校样,we的所有格形式可以在由于更多的加法的K层K-1层,坚持到底,此刻,由于we的所有格形式只K-1机遇,因而we的所有格形式不得不加法这样地时期。K-1层,为了确保第独一鸡蛋在受校样时被残害,官方使命依然可以是C。。

随即,反复前述的指引航线,直到最不克不及够的一次机遇。,we的所有格形式受校样过的议员席总额是:

      

那么,回到原始成绩。,hg0088备用网址楼,万一需求K考试才干受校样使筋疲力尽,则霉臭有

你可以接收它。,k≥14

这执意需求。14个受校样总算。,这样地指引航线也将提名受校样展现。,那是最初的。14建造物实验,万一第独一鸡蛋破了,则其他人员13机遇,13层未知议员席,恰恰,次货次14+13=27建造物实验,非常的。

万一责怪hg0088备用网址,但是N层,所需受校样的等同为k,则有

      

========================================================= 

那么,这样地成绩可以在这样地时候扩展。,万一we的所有格形式有三个鸡蛋,有K机遇,we的所有格形式可以受校样少量层?

和先前平均。,最初的受校样,不要太高或太短。,必然是对的。,换句话说,万一第独一鸡蛋坏了。,其他人员K-1机遇能将其他人员议员席给受校样完。

从由于尾声,K-1机遇至多可以受校样K(K-1)/2层,因而最初的K(K-1)/2+1层,最初的,万一第独一鸡蛋缺少破损。,次货次此按照加法(K-1)(K-2)/2+1层建造物,随即,三个鸡蛋K机遇总共受校样议员席数为

k=9.

至若四的鸡蛋,与某人击掌问候鸡蛋,以至若鸡蛋,什么的。,办法与前述的办法相似的。。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注