Profilo di HuperHuperFotoBlogElenchiAltro Strumenti Guida

Blog


20 agosto

一道面试题

今天有几个人来我们公司面试,走了以后我就和同事们聊起来面试,这时候Charlie跟我们说要给我们出一个当年他见到的笔试(or面试)题:

有三个材质一样的玻璃球,一个300层高的楼。问最少试验几次可以保证一定能够知道玻璃球的承受能力(假设玻璃球从300层扔下一定会碎,就是说承受能力肯定小于300层)。注:只有三个球,碎了就不能用了。每扔一个球算实验一次。有可能承受能力是0层(就是在一层扔也有可能会碎)

然后我和Bart还有小栗就一起研究,还算不错,大概10分钟左右就想出来了答案,觉得还蛮有意思的,所以决定记录下来。

-----------------------分割线,下面是答案----------------------------







首先,我们设一个函数F(x,y),表示x个球试y次最多可以在多少层楼的范围内保证测试出来。

然后我们先从两个球入手,做这么一道题:把三个球改成两个,然后考虑如果两个球,可以试n次,最多可以试多少层楼呢?

这个题的思路自然是分段试验,先用一个球从低往高进行分段试验,找到范围,然后再用剩下的一个球在那个范围内从低到高逐层试验。

不妨我们都用一号球先来试,一旦一号球碎了,再用二号球一层一层的试。实验开始:

(1)假设第一次把一号球放在n0层,碎了。
这时候我们就要考虑n0是多少。因为可以试n次,我们用一号球试了一次,还剩下n0-1次,二号球用n0-1次只能在n0-1层的范围内逐一试验,最坏的情况要试到n0-1层才得出答案,因此n0应该等于n。
(2)假设第一次把一号球放在n0层(也就是n层),没碎。
那么我们要在n0层上面的某层再试一号球。这时候一号球试验了两次,第二个球最多只能再试验n-2次,因此二号球能够逐一扫过n-2层楼的范围,加上一号球的第二次试验,就等于这个阶段一共扫过了n-1层的范围。

以此类推,一号球每多试验一次,二号球就要少试验一次,也就是少扫过一层的范围。因为一号球最多可以试n次,所以一共可以扫过的层数就是:
n+(n-1)+(n-2)+...+1=n(n+1)/2层

所以:F(2,n)=n(n+1)/2。

比如说两个球试10次,就可以让第一个球分别在10, 19, 27, 34, 40, 45, 49, 52, 54, 55层进行试验,只要碎掉,就用第二个球在得出的区间内从低到高逐层试验。可以保证在F(2,10)=55层之内都可以得到结果。

---------------------------------------------

至此,两个球的问题已经解决了。然后我们来解决三个球的问题,那就是三个球试n次最多可以测多少层楼呢。

由于我们已经有了两个球的思路,三个球的思路就比较明了了。

(1)假设第一个球我们放在n0层,碎了
此时我们仍然要算一下n0是多少。既然可以试n次,第一个球占去了一次,还剩下n-1次。由两个球的结论,两个球n-1次试验可以测出n(n-1)/2层的范围,所以n0=n(n-1)/2+1。

(2)假设第一个球我们放在n0层,没碎
由两个球的思路,第一个球每多一次试验,后两个球就少了一次试验。第一个球可以试验1到n次,把相应的剩下的两个球可以测出的楼层数相加,再加上第一个球自己所测的n层即可。

所以:

    n
F(3,n)=sigma (F(2,n-i)+1)
    i=1

把F(2,n)的公式带入
    n            n-1
F(3,n)=sigma ((n-i)(n-i+1)/2+1)=sigma (i(i+1)/2+1)
    i=1           i=0
展开以后得:
F(3,n)=(n^3+5n)/6

回到原题,只要F(3,n)>=300即可,取n的最小整数值。我们可以得到F(3,12)=298, F(3,13)=377。

所以最少只需要13次就能保证在300层以内一定可以找到。

---------------------------------------------

然后我们可以把这个题扩展到求x个球试y次。我们可以得到如下的递归公式:
    y          y-1
F(x,y)=sigma(F(x-1,y-i)+1)=sigma(F(x-1,i)+1)
    i=1         i=0

这样,我们就可以用程序来解决这个问题了,写一个递归的程序看起来会非常的简单。

函数如下(Java):

    private static int run (int number, int times) {

        int s = 0;
        //终止条件:试验次数为0的时候结果为0,球的数量为1的时候结果就是试验次数。
        if (times == 0)
            s = 0;
        else if (number == 1)
            s = times;
        else {
            for (int i = 0; i < times; i++)
                s += run (number - 1, i) + 1;
        }
        return s;
    }

其中number表示球的数量,times表示试的次数。





Commenti (7)

Attendere...
Il commento immesso è troppo lungo. Immetti un commento più breve.
Immissione non effettuata. Riprova.
Impossibile aggiungere il commento al momento. Riprova più tardi.
Per aggiungere un commento è necessaria l'autorizzazione di un genitore. Chiedi autorizzazione
I tuoi genitori hanno disattivato i commenti.
Impossibile eliminare il commento al momento. Riprova più tardi.
Hai raggiunto il numero massimo di commenti pubblicabili giornalmente. Riprova tra 24 ore.
Impossibile lasciare commenti. La funzionalità è stata disattivata perché i sistemi hanno rilevato una possibile attività di spamming dal tuo account. Se ritieni che il tuo account è stato disattivato per errore, contatta il supporto tecnico di Windows Live.
Esegui il seguente controllo di protezione per completare la pubblicazione del commento.
I caratteri digitati nel controllo di protezione devono corrispondere ai caratteri dell'immagine o della riproduzione audio.

Per aggiungere un commento, accedi con il tuo Windows Live ID (se utilizzi Hotmail, Messenger o Xbox LIVE possiedi già un Windows Live ID). Accedi


Non hai ancora un Windows Live ID? Registrati

Haohui Maiha scritto:
f(x,y)跟随您的定义.

式子应该是这样f(x,y) = 1 + min { f(x, y-1) , f(x-1, y-1)},两个分别对应碎了和没碎的情况

老年痴呆越来越严重了,手抖打错字。。
23 Ago.
Huper Huangha scritto:
To Zig: orz...
To 麦爷: 您的min里面是啥。。。谁和谁比……
22 Ago.
Haohui Maiha scritto:
f(x,y) = 1 + min { f(x, y-1) + f(x-1, y-1)}
f(0,n) = f(n,0) = 0, f(1,n) = n

dp一下就出来了。解析解不知道怎么算。应该就是zig说的nlogn算法了吧
21 Ago.
Yaming Huangha scritto:
大牛!
20 Ago.
Wei Yuha scritto:
我记得这个有nlogn的算法,因为当时我们做的时候n^2的过不了.
20 Ago.
Huper Huangha scritto:
这是以前一个对冲基金公司的笔试题……
20 Ago.
Slan Yangha scritto:
请问考官:什么职位要面这么变态的题目?
20 Ago.

Riferimenti

L'URL di riferimento per questo intervento è:
http://huper9.spaces.live.com/blog/cns!68F52D74B3DF7A1D!2524.trak
Blog che fanno riferimento a questo intervento
  • Nessuno