作者teves (teves)
看板Inference
標題Re: [問題] 擲杯問題
時間Mon Jun 15 12:00:33 2009
※ 引述《brains (不認識)》之銘言：
: 一種杯子,
: 若在第 N 層被摔破, 則在任何比 N 高的樓層均會破;
: 若在第 M 層不破, 則在任何比 M 低的樓層均不破.
: 現在給你兩個這種杯子, 讓你在100層樓高的建築作測試, 要求用最少的測試次數找出
: 恰巧會使杯子摔破的樓層.
: ---------------------------
: 這問題若po過我會自D
以最大試驗次數最小來看
我認為是先丟
14,27,39,50,60,69,77,84,90,95,99這幾層直到破
另一個杯子依序試中間的區段
最多14次
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.109.22.19
1F：推 weian:漂亮，不過我直覺想的是平均值最小的方法，還沒解決 06/15 12:06
2F：→ teves:平均最小的解感覺不會有太大的差異 06/15 12:52
3F：推 stimim:這不是ACM的題目嗎？ 06/15 14:07
4F：推 luciferii:我比較好奇你們的作法，如果第一次就丟破怎麼辦? 06/15 15:50
5F：→ luciferii:嗯，想錯，你這方式是最小14次沒錯 06/15 15:52
6F：推 stimim:可以反著推回來，如果你有k顆水球，可以試T次，你最多可以 06/15 17:12
7F：→ stimim:確定多少層樓高的房子 06/15 17:13
8F：推 BGirlAlu:厲害 06/16 13:38
9F：推 MaMaMoMo:真厲害 ! 想請問 14 這個數字怎麼得出的 ? 有算法嗎 ? 06/16 19:08
10F：推 MaMaMoMo:想到好像是梯形面積的公式@@~ ((X+1)*X)2 > 100 06/16 19:12
11F：→ teves:你只要想第一個杯子多丟一次,第二個杯子試最多就要少一次 06/16 23:08
12F：→ teves:下面那一篇則提供了有條理的解法XD 06/16 23:09
13F：→ teves:我則是很直覺地打開記事本試一試而已XD 06/16 23:11