Re: [請益] 金幣問題
※ 引述《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
推
09/10 00:05, , 1F
09/10 00:05, 1F
推
09/10 00:15, , 2F
09/10 00:15, 2F
推
09/10 00:44, , 3F
09/10 00:44, 3F
→
09/10 00:45, , 4F
09/10 00:45, 4F
推
09/10 01:12, , 5F
09/10 01:12, 5F
→
09/10 01:13, , 6F
09/10 01:13, 6F
推
09/10 01:20, , 7F
09/10 01:20, 7F
→
09/10 01:20, , 8F
09/10 01:20, 8F
推
09/10 01:23, , 9F
09/10 01:23, 9F
推
09/10 02:46, , 10F
09/10 02:46, 10F
推
11/12 08:38, , 11F
11/12 08:38, 11F
→
07/07 21:09,
6年前
, 12F
07/07 21:09, 12F
討論串 (同標題文章)