時間 (2014-04-16 16:46:13)

推文13則 (6推 0噓 7→)
※ 引述《brucetu (sec)》之銘言：
: 既然知道兩個蛋相同
: 就再找98個相同的蛋從1~100樓同時落下
: 再算算看有幾顆蛋
: 平行處理
: ※ 引述《howdiun (Howdiun)》之銘言：
: : 把蛋交給別人，
: : 叫他從一樓開始丟，
: : 破掉再跟我回報樓層，
: : 我會付他薪水，
: : 為了怕她騙我，
: : 我可以一次請兩個人（反正有2個蛋），
: : 我要摔幾次？
: : 0次

這個應該和camera af差不多的algorithm
第一顆蛋做coarse search,第二顆做fine search
所以假設第一顆一次跳x層樓，最差跳100／x次
第二顆要找x-1次
所以找100/x + x／2-1的最小值
x大約是10
也就是說第一顆蛋每10樓丟一次
最差情況是在99樓，丟10次
第二顆可2層丟一次，要丟4次
共14次
不知這答案可不可行

--
Sent from my Android--
※ 發信站: 批踢踢實業坊(pttweb.tw), 來自: 42.74.136.62
※ 文章網址: https://pttweb.tw/Soft_Job/M.1397637976.A.C51

#1推 :這的確是最佳解～但是解釋的方式比較淺顯04/16 17:40

#2推 :強...@@04/16 18:56

#3推 :如果第二顆蛋破在第92層，怎麼知道該在91還92？04/16 19:05

#4推 :92破怎麼還會再9204/16 19:26

#5推 :他意思是破在92, 你怎麼知道安全的極限是90還91?04/16 19:38

#6推 :e.g 1號蛋在90樓丟沒破, 此時x=5, 90+x=95樓再丟一次1號04/16 21:07

#7 蛋破掉後, 直接從91樓開始一樓一樓丟2號蛋, 當你在92樓04/16 21:08

#8 丟2號蛋第一次破, 那麼91樓就是答案.04/16 21:08

#9 x可以隨著coarse search次數逐漸增多而遞減04/16 21:09

#10 http://datagenetics.com/blog/july22012/index.html04/16 21:11

#11→ :樓上跟這篇講的不一樣吧以樓上作法99層是丟12次04/16 22:22

#12→ :@GoalBased，我是說破在 92，如何知道 91 會不會破？04/17 00:14