作者pig030 (猫博3号)
看板logic
标题Re: [请益] 金币问题
时间Tue Sep 9 23:59:25 2008
※ 引述《hseuler (蓝色狸猫)》之铭言：
: 1.
: 100个金币，长得一模一样，其中一个比较重，给一个天秤，最多花多少次，能找出那
: 比较重的金币？如果给1000个呢? 10000个呢？
最多次，这个问题比较难。 最少次的话这个问题比较简单
先把金币分成四堆 A(33)个 B(33)个 C(33)个 D(1)个
如果A>B则最重的金币在A堆里面 (其他比法以此类推)
因此我们剩下33个里面找出个最重的金币。
一样再将33个分成3堆 E(11)个 F(11)个 G(11)个
如果E>F则最重的金币在里面，因此我们可以再将金币分成3堆
即H(5) I(5) J(1) 如果H>I则 最重的金币在H里面
因此我们可以再分成3堆 即K(2) L(2) M(1)
如果K>L我们可以知道金币最重的在K 因此再坪最後一次即可知。
因此我们可知道运气好的话 最少坪2次。
运气最差的话最多5次...
这个方法我想应该可以改进，不知道大家可以指出来吗？
--------------------------------------------------------------
我也想过利用切一半找法。 先分成50 50
再分成 25 25
再分成 12 12 1
最後再分成 6 6
再分成3 3
最後再分成1 1 1
但是这样也要6次...
--
"假如"人类不存在，那麽经济就不需要
"假如"牛马鬼神存在，那麽必有一个平衡点
不然这个世界早就崩溃，不会有你的出生。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 124.29.131.148
1F：推 hseuler:那存不存在一种方法 在四次之内就可以找到？ 09/10 00:05
2F：推 hseuler:其实运气好 一次就可以了 09/10 00:15
3F：推 luciferii:这两题请找版上「找出重量不等的球」或类似题目 09/10 00:44
4F：→ luciferii:了解後可以自己对m球写出公式 09/10 00:45
5F：推 hseuler:我看过那讨论串 不过那讨论串已经给定最小次数 09/10 01:12
6F：→ hseuler:然後再去找方法 但问题现在是 要怎麽找最好的方法? 09/10 01:13
7F：推 hseuler:其实我要问的是第二题呢 09/10 01:20
8F：→ hseuler:第一题的答案应该是log100/log3 非整数的话就无条件进位 09/10 01:20
9F：推 hseuler:但希望版友提共第二题的思路 09/10 01:23
10F：推 theknight:第2题好像会因N而有所差异 毕竟…这种解法要用到前次条 09/10 02:46
11F：推 waiter337: 不建议 33 33 33 1 直接分25 25 25 25 11/12 08:38