最少秤幾次? - 拼圖
![Adele avatar](/img/cat5.jpg)
By Adele
at 2007-11-23T07:25
at 2007-11-23T07:25
Table of Contents
※ 引述《bb511 (我沒空打牌)》之銘言:
: 這問題搞不好大家都知道 也看過了
: 不過我查一下 好像沒po過??
: ---------------------------------------------
: 有十二袋裝滿金幣的袋子
: 每袋中的金幣一樣多
: 其中一袋裝滿假金幣
: 真金幣每枚10公克,假金幣每枚9公克。
: 最少要秤幾次才能秤出假金幣?
這題相信很多人知道答案了,不過為了向經典題目致敬,還是正式回答一下。
首先,這個題目重點在於,我們必須知道假幣與真幣間的重量差為多少。很多人會把它跟
「用天平找假幣」的題目弄混,認為只要知道「較輕」、「較重」的資訊即可,事實上這
樣是無解的(若要求一次秤出的話)。必須還要知道它「或輕、或重幾克」才行。
此外,本題通常不考慮每袋金幣是否有數量上的限制,也不考慮磅秤是否夠大,能讓我們
不管拿多少金幣都秤得了(我相信日後一定會有腦筋急轉彎的題目鑽此漏洞)。
言歸正傳
原始的問題很簡單,首先在十二袋金幣上分別編上一到十二的編號,再分別從裡頭拿出相
同數量的金幣。把這十二堆的金幣一起拿去秤,然後看它比標準重量差多少即可判斷假幣
在哪一袋裡。
如果假幣在第一袋裡,那秤出來的重量一定比標準重差1公克;若假幣在第二袋裡,由於
我們從裡頭拿出兩枚,所以秤出的重量一定比標準重少2公克,其餘依此類推。
這個問題的變形是,如果假幣可能不只一袋,能否在只秤一次的情況找出呢?
答案是肯定的。
首先一樣先編號,接著只要從每袋之中取出「2的(編號減一)次方」數量的金幣,一起
拿去秤即可。實際的數量如下:
1、2、4、8、16、32、64、128、256、512、1024、2048
(2的0次方、2的1次方……2的10次方、2的11次方)
這些一共是4095(用〔2的N+1次方〕-1算較快)
也就是標準重是40950公克。
接著只要看秤出來的重量差幾克,然後再算它是由哪些數字組成即可。表面上這邊的計算
有點麻煩,但只要用「2進位」的觀念下去算就行了。
例如秤出來的重量是39587克,那麼──
40950-39587=1363
把1363轉成2進位得:
2|1363 ....餘 1
────
2|681 ....餘 1
────
2|340 ....餘 0
────
2|170 ....餘 0
────
2|85 ....餘 1
───
2|42 ....餘 0
───
2|21 ....餘 1
───
2|10 ....餘 0
───
2|5 ....餘 1
───
2|2 ....餘 0
───
1
所以1363(10進位)=010101010011(2進位。最前面補0,是為了湊齊12位數)
由於1在第1、第2、第5、第7、第9、第11位上,所以相應編號的金幣是假的。
1363=1+2+16+64+256+1024
用第二種方法當然也可以用來解決起初的問題,但它的缺點就是必須要拿出許多金幣來測
量(例如本題需取出4095枚)不像第一個方法那樣「輕便」,可以說是各有利弊。
這些東西相信大家都知道,不過問題太經典,所以還是打來當做記錄。
puzzlez
2007/11/22
--
: 這問題搞不好大家都知道 也看過了
: 不過我查一下 好像沒po過??
: ---------------------------------------------
: 有十二袋裝滿金幣的袋子
: 每袋中的金幣一樣多
: 其中一袋裝滿假金幣
: 真金幣每枚10公克,假金幣每枚9公克。
: 最少要秤幾次才能秤出假金幣?
這題相信很多人知道答案了,不過為了向經典題目致敬,還是正式回答一下。
首先,這個題目重點在於,我們必須知道假幣與真幣間的重量差為多少。很多人會把它跟
「用天平找假幣」的題目弄混,認為只要知道「較輕」、「較重」的資訊即可,事實上這
樣是無解的(若要求一次秤出的話)。必須還要知道它「或輕、或重幾克」才行。
此外,本題通常不考慮每袋金幣是否有數量上的限制,也不考慮磅秤是否夠大,能讓我們
不管拿多少金幣都秤得了(我相信日後一定會有腦筋急轉彎的題目鑽此漏洞)。
言歸正傳
原始的問題很簡單,首先在十二袋金幣上分別編上一到十二的編號,再分別從裡頭拿出相
同數量的金幣。把這十二堆的金幣一起拿去秤,然後看它比標準重量差多少即可判斷假幣
在哪一袋裡。
如果假幣在第一袋裡,那秤出來的重量一定比標準重差1公克;若假幣在第二袋裡,由於
我們從裡頭拿出兩枚,所以秤出的重量一定比標準重少2公克,其餘依此類推。
這個問題的變形是,如果假幣可能不只一袋,能否在只秤一次的情況找出呢?
答案是肯定的。
首先一樣先編號,接著只要從每袋之中取出「2的(編號減一)次方」數量的金幣,一起
拿去秤即可。實際的數量如下:
1、2、4、8、16、32、64、128、256、512、1024、2048
(2的0次方、2的1次方……2的10次方、2的11次方)
這些一共是4095(用〔2的N+1次方〕-1算較快)
也就是標準重是40950公克。
接著只要看秤出來的重量差幾克,然後再算它是由哪些數字組成即可。表面上這邊的計算
有點麻煩,但只要用「2進位」的觀念下去算就行了。
例如秤出來的重量是39587克,那麼──
40950-39587=1363
把1363轉成2進位得:
2|1363 ....餘 1
────
2|681 ....餘 1
────
2|340 ....餘 0
────
2|170 ....餘 0
────
2|85 ....餘 1
───
2|42 ....餘 0
───
2|21 ....餘 1
───
2|10 ....餘 0
───
2|5 ....餘 1
───
2|2 ....餘 0
───
1
所以1363(10進位)=010101010011(2進位。最前面補0,是為了湊齊12位數)
由於1在第1、第2、第5、第7、第9、第11位上,所以相應編號的金幣是假的。
1363=1+2+16+64+256+1024
用第二種方法當然也可以用來解決起初的問題,但它的缺點就是必須要拿出許多金幣來測
量(例如本題需取出4095枚)不像第一個方法那樣「輕便」,可以說是各有利弊。
這些東西相信大家都知道,不過問題太經典,所以還是打來當做記錄。
puzzlez
2007/11/22
--
Tags:
拼圖
All Comments
Related Posts
聯想題 016
![Tracy avatar](/img/woman-ring.jpg)
By Tracy
at 2007-11-23T00:24
at 2007-11-23T00:24
聯想題 014
![Zenobia avatar](/img/cat3.jpg)
By Zenobia
at 2007-11-22T20:21
at 2007-11-22T20:21
加字組合 008
![Liam avatar](/img/girl3.jpg)
By Liam
at 2007-11-22T19:14
at 2007-11-22T19:14
最少秤幾次?
![Vanessa avatar](/img/woman-biz.jpg)
By Vanessa
at 2007-11-22T17:15
at 2007-11-22T17:15
撿碁石 011
![Tristan Cohan avatar](/img/cat5.jpg)
By Tristan Cohan
at 2007-11-22T16:57
at 2007-11-22T16:57