[轉錄]Re: [問題] 秤重的老問題
※ [本文轉錄自 Inference 看板]
作者: zephyr (斷了線的風箏) 看板: Inference
標題: Re: [問題] 秤重的老問題
時間: Fri Dec 17 01:55:45 2004
※ 引述《u504053 (Rebecca)》之銘言：
: 現在假設有12個球，其中有一顆的重量與其它11顆球不同，
: 只是也不知道比較輕還是比較重。
: 有辦法只用三次天秤就秤出結果來嗎?
: 這是秤重的老問題
: 我手上也有所謂的解答
: 可是我覺得那考慮太少狀況
: 解答好像不太完全
: 大家討論一下吧 ^Q^
._.a
花時間再寫一次用編碼解的過程好了....
秤一次天秤有三種結果，三次就是3*3*3=27種
我們希望把每一種結果都能對應到某一顆球是輕或重上
比如說想把"三次都是左邊重"對應到"A球較重"，那就必須三次都把A球放在天秤左邊
在這種放法下，完全相反的結果"三次都是右邊重"，當然也就會對應到"A球較輕"
用編碼解的出發點就是這樣，希望剛好把所有結果都分完
接下來把27種可能都列出來 (右:表示右重，左:表示左重，平:表示平衡)
右右右 A重 左左左 A輕 右右平 B重 左左平 B輕
右右左 C重 左左右 C輕 右平右 D重 左平左 D輕
右平平 E重 左平平 E輕 右平左 F重 左平右 F輕
右左右 G重 左右左 G輕 右左平 H重 左右平 H輕
右左左 I重 左右右 I輕 平右右 J重 平左左 J輕
平右平 K重 平左平 K輕 平右左 L重 平左右 L輕
平平右 M重 平平左 M輕 平平平
裡面的平平平表示上秤的所有球都一樣重，也就是沒有不同的球
其他26種結果都會對應到某顆球是輕或重
然後依照上面那種方法把這些球放在天秤上
(如前所述般，右右右是A重，所以A要放右邊)
就有
1. : ABCDEFGHI
2. GHI : ABCJKL
3. CFIL : ADGJM
不過這種放法顯然是失敗的，因為天秤要在兩邊個數一樣的時候才能秤
所以要把前面的編碼方法稍微做點修正
(在這邊我把B,C,D,E的輕重顛倒過來)
右右右 A重 左左左 A輕 右右平 B輕 左左平 B重
右右左 C輕 左左右 C重 右平右 D輕 左平左 D重
右平平 E輕 左平平 E重 右平左 F重 左平右 F輕
右左右 G重 左右左 G輕 右左平 H重 左右平 H輕
右左左 I重 左右右 I輕 平右右 J重 平左左 J輕
平右平 K重 平左平 K輕 平右左 L重 平左右 L輕
平平右 M重 平平左 M輕 平平平
就有
1. BCDE : AFGHI
2. BCGHI : AJKL
3. DFIL : ACGJM
在這裡只要多一個正常的球N上去做平衡
就是"秤三次，從13顆球中找出一顆重量不同的球"的秤法
1. BCEDN : AFGHI
2. BCGHI : AJKLN
3. DFILN : ACGJM
反過來，如果把球G去掉
就是"秤三次，從12顆球中找出一顆重量不同的球"的秤法
1. BCDE : AFHI
2. BCHI : AJKL
3. DFIL : ACJM
類似的做法也可以很容易的推廣到
"秤N次，從[(3^N)/2]-1顆球中找出一顆重量不同的球"上
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.190.43
推
144.136.132.152 12/18,
144.136.132.152 12/18
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.31.131