時間 (2014-04-12 11:16:12)

推文21則 (8推 0噓 13→)
假設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層樓高的大樓。
: 而蛋的特性有的可能很堅固，堅固到從一百層樓跌下都沒事，
: 有的可能很脆弱，一樓就可以摔破。
: 現在你只知道這這兩顆蛋是完全相同的，
: 你想要知道蛋最高從哪一層樓摔下來不會摔破。
: 問題是：你要摔幾次才能計算出來？
: （如果你低於高度摔下蛋，蛋就沒事，如果高於那個樓層，蛋就完蛋）
: 在這過程你可以摔破蛋。
--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 72.229.214.138
※ 文章網址: https://pttweb.tw/Soft_Job/M.1397272575.A.198
※ 編輯: 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

#1推 :學過數學的就是不一樣04/12 11:28

※ 編輯: hweric (72.229.214.138), 04/12/2014 11:33:42

#2推 :f(x) 就是連加要過樓層, 基本梯型公式 (x <= ...那段)04/12 12:09

#3→ :樓上說的沒錯，不過不證明並不能保證它是梯型公式，畢竟04/12 12:20

#4 原先的f(x)是min{max}}，我只是推論它的結果是梯型公式04/12 12:20

#5推 :這個版常有人說數學跟演算法沒屁用。04/12 14:45

#6推 :cool04/12 15:28

#7推 :沒屁用+1, google的缺太少了..很多缺的就有屁用04/12 15:30

#8→ :台灣軟體工程師覺得沒屁用，難怪軟體產業發展不起來。04/12 15:57

#9推 :推04/12 16:29

#10→ :很意外嗎，看這個版的風氣就知道啦，軟體 = 程式語言04/13 00:47

#11 軟體業 = 程式語言。這種狹隘的思考。04/13 00:48