2021年11月2日 星期二

數學_從第幾層樓丟下,玻璃球會剛好碎掉(未知解法)?


最近看到一個面試題目(註1),如下:
給你兩個一模一樣的玻璃球。這兩個球如果從一定高度掉到地上就會摔碎,
當然,如果在這個高度以下往下扔,怎麼都不會碎,超過這個高度肯定就一次摔碎了。
現在已知這個恰巧摔碎的高度範圍在1層樓到100層樓之間。
如何用最少的試驗次數,用這兩個玻璃球測試出玻璃球恰好摔碎的樓高。

為了便於你理解這道題,我不妨講兩個具體的策略。
第一個策略是從第一層樓開始,一層一層往上試驗。
你拿著球跑到第一層,一摔,沒有碎,接下來你又跑到第二層去試,也沒有摔碎。
你一層層試下去,比如說到了第59層摔碎了,那麼你就知道它摔碎的高度是59層。
這個策略能保證你獲得成功,但顯然不是很有效。

第二個策略是預測一下,試一試, 你跑到30層樓一試,沒有碎,再跑到80層樓一試,碎了。
雖然你把摔碎高度的範圍從1-100減小到30-80,但接下來你就犯難了,因為你就剩一個球了,
再這樣憑感覺做試驗,可能兩個球都摔碎了,也測不出想知道的高度。

它的答案是:
第一顆球,由下往上,每次增加10層樓丟,
比如:到10樓丟,沒碎,就去20樓丟...一直到碎時,
   如果100樓沒碎,答案就是100。
第二顆球,在第一顆球碎時,退10層,由下往上,每次增加1層樓丟。
比如:第一顆在80樓碎掉,則退到70(80-10),照71、72、73...順序丟。
一定會在20次內找到。


假如有三顆球,答案是:
跟上題的模式一樣,
第一顆球,由下往上,每次增加22層樓;
第二顆球,找到第一顆球碎的樓層,退22層、每次增加4或5層樓丟;
第三顆球、找到第二顆球....   ,退4或5層,每次增加1層樓丟;


*****
我雖然知道這兩題答案,
但沒有找到為什麼第一題是10和1、第二題是22、4(或5)、1。
(我覺得網路上應該有人解答)因此,我從答案去猜解法。

從作兩輪,作三輪,我想到程式的For loop。
1.作兩輪:
for(int i = 0; i <n; i++)
 for(int j = 0; j <n; j++)
    ....
複雜度為:O(n^2)

2.作三輪:
for(int i = 0; i <n; i++)
 for(int j = 0; j <n; j++)
        for(int k = 0; k <n; k++)
        ....
複雜度為:O(n^3)


假如我要作兩輪(兩層的for loop),把100層都跑到。n^2=100。
就是拿100開2次方更號=10,n為10。
第一個for loop要做10次,每次就要增加100/10=10(層樓)。
第二個for loop要做n^2次,也就是100次,那每次就要增加100/100=1(層樓)。

假如我要作三輪(三層的for loop),把100層都跑到。n^3=100。
就是拿100開3次方更號,n約為4.64(4的立方是64、5的立方是125)。
第一層for loop要做4.64次,每次就要增加100/4.64,約為22(層樓)。
第二層for loop要做4.64的平方次,每次要增加100/21.54,約為4或5(層樓)。
第三層for loop要做4.64的立方次,那就是100的意思,
每次要增加100/100=1(層樓)。

這是我能想到的、最有可能的解法。



-------------------------------------------------------------------------------------------------------------------
註1:圖片來源

-------------------------------------------------------------------------------------------------------------------
參考資料:硅谷來信SE2,Letter025、026

沒有留言:

張貼留言