Re: [討論] Google面試問題

[hweric ()]

 假設f(x)是有x層樓時最糟情況最少需要丟的次數。
         x
 f(x) = min{max{1 + j - 1, 1 + f(x-j)}}
        j=1

 f(0) = 0
 f(1) = 1
 f(2) = 2
 f(3) = 2
 f(4) = 3
 f(5) = 3
 f(6) = 3
 f(7) = 4
 f(8) = 4
 ....

 f(x) = k, where (k-1)k/2 < x <= k(k+1)/2
 f(100) = 14

 不確定f(x)對不對，k的部份可以用數學歸納法證明。

※ 引述《bleed1979 (十三)》之銘言：
: 問題：
: 假設你有兩顆蛋，然後有一棟100層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 72.229.214.138
※ 文章網址: http://www.ptt.cc/bbs/Soft_Job/M.1397272575.A.198.html
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:17:43
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:18:50
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:19:37
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:22:42
推 bobju:學過數學的就是不一樣
※ 編輯: hweric (72.229.214.138), 04/12/2014 11:33:42
推 lovdkkkk:f(x) 就是連加要過樓層, 基本梯型公式 (x <= ...那段)
→ hweric:樓上說的沒錯，不過不證明並不能保證它是梯型公式，畢竟
→ hweric:原先的f(x)是min{max}}，我只是推論它的結果是梯型公式
推 thanksyou:這個版常有人說數學跟演算法沒屁用。
推 giantwinter:cool
推 Ting1024:沒屁用+1, google的缺太少了..很多缺的就有屁用
→ ACMANIAC:台灣軟體工程師覺得沒屁用，難怪軟體產業發展不起來。
推 cckk3333:推
→ DrTech:很意外嗎，看這個版的風氣就知道啦，軟體 = 程式語言
→ DrTech:軟體業 = 程式語言。這種狹隘的思考。
→ DrTech:連討論內容也是，搞得此板根本該改名程式語言版。
→ andymai:沒屁用?給你含雜訊的信號數據~請在不用數學的情況下~實作
→ andymai:出原來的信號波形...沒用到跟沒屁用~千萬不要混為一談
→ ykjiang:樓上這個例子不夠複雜，可能不必用到正規的數學
→ andymai:@@不好意思~個人不懂何謂"正規"的數學?
推 dnabossking:主流數學分析討論的都是連續的數學問題
→ dnabossking:寫程式的人比較在意的是離散的數學問題
推 changyuheng:覺得演算法沒用？可以參考：http://goo.gl/lSvD9w
→ ykjiang:我想回答正不正規的問題，不過推文說不清楚～
→ ykjiang:有點類似工程師跟物理學者跟數學家這三者用數學的方式吧