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