Re: [問題] 擲杯問題

[teves (teves)]

※ 引述《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
推 weian:漂亮，不過我直覺想的是平均值最小的方法，還沒解決
→ teves:平均最小的解感覺不會有太大的差異
推 stimim:這不是ACM的題目嗎？
推 luciferii:我比較好奇你們的作法，如果第一次就丟破怎麼辦?
→ luciferii:嗯，想錯，你這方式是最小14次沒錯
推 stimim:可以反著推回來，如果你有k顆水球，可以試T次，你最多可以
→ stimim:確定多少層樓高的房子
推 BGirlAlu:厲害
推 MaMaMoMo:真厲害 ! 想請問 14 這個數字怎麼得出的 ? 有算法嗎 ?
推 MaMaMoMo:想到好像是梯形面積的公式@@~ ((X+1)*X)2 > 100
→ teves:你只要想第一個杯子多丟一次,第二個杯子試最多就要少一次
→ teves:下面那一篇則提供了有條理的解法XD
→ teves:我則是很直覺地打開記事本試一試而已XD