作者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