我最近看到一個面試題目，問如何花費做少次數進行測試，這文章主要是講該如何思考來解決這樣的問題
最近在ptt的soft_job看到一個面試問題：
你有兩顆蛋，其堅固程度不詳，可能可以承受從100層樓丟下去的衝擊力而不破
也可能一層樓高的衝擊力就破
這兩顆蛋的堅固程度相同
今天要你用一棟100層樓高的建築進行測試，來知道蛋最高可以從多少層樓摔下去而不破
那你需要摔多少次才能判斷出來
這是個有趣的問題
一開始我想到的是二分法，但這是我沒看清楚題目而想到的做法
題目說兩顆蛋表示只能摔破2次，不可以說50層樓摔一次 然後25or75再摔一次
大概作法應該採取過濾與精練的作法
第一顆蛋用負擔比較小的方式來過濾掉不會是答案的結果
第二顆蛋用負擔比較大的方式來進行確認
一開始想到的做法是以x為單位，每次增加層樓測試，破了就再摔最多x次
最多次數約(x/10)(無條件進位)-1+x
x多少需要一個個數字算算看，x大概10(100的平方根)左右比較小，也就是最多數字約19次
後來有人的方式跟我類似，但他的x是從14開始，x逐漸減少
(第一次14、第二次27、第三次39...以此類推)
這樣最多次數為14，比我的作法好(雖然都沒人說14哪來的)
我沒有想到每次過濾的數量可以調整而非固定
但14要怎麼來呢?
這首先要能先想到解法是這樣的梯形
一開始先往上x層，然後x遞減
再用梯形公式試(1+x)*x/2的結果:
(1+13)*13/2=91<100
(1+14)*14/2=105>100...所以x從14開始
要較快速的得到14並非一個數字一個數字的試
而是該取100*2的平方根附近整數來算(200的平方根為14多)
為什麼要取乘以2的平方根呢?其實這是把梯形公式的除以2移到另一邊
左邊就變成(1+x)*x了，右邊再取平方根，就能得到接近相等的數字了
我覺得過濾與精煉是比較容易想到的方式，我過去經驗告訴我這樣的方法很可能適用
但梯形這部分就會變得比較困難了
我想這部分需要做過類似題目或能作跳躍性思考才能解開吧
跳躍性思考...需要靈光一現...我相信都能在面試時靈光一現的人不會多的
我覺得這種題目只有兩種人能答對:
1.同時能夠在面試中進行跳躍性思考與謹慎的邏輯思考的人
2.做過類似題目的人
這種題目剛有人出時，答對的比較有可能是前者，但久了…我相信答對的很可能會是後者。