※ 引述《bb511 (我沒空打牌)》之銘言： : 這問題搞不好大家都知道 也看過了 : 不過我查一下 好像沒po過?? : --------------------------------------------- : 有十二袋裝滿金幣的袋子 : 每袋中的金幣一樣多 : 其中一袋裝滿假金幣 : 真金幣每枚10公克，假金幣每枚9公克。 : 最少要秤幾次才能秤出假金幣？ 這題相信很多人知道答案了，不過為了向經典題目致敬，還是正式回答一下。 首先，這個題目重點在於，我們必須知道假幣與真幣間的重量差為多少。很多人會把它跟 「用天平找假幣」的題目弄混，認為只要知道「較輕」、「較重」的資訊即可，事實上這 樣是無解的（若要求一次秤出的話）。必須還要知道它「或輕、或重幾克」才行。 此外，本題通常不考慮每袋金幣是否有數量上的限制，也不考慮磅秤是否夠大，能讓我們 不管拿多少金幣都秤得了（我相信日後一定會有腦筋急轉彎的題目鑽此漏洞）。 言歸正傳 原始的問題很簡單，首先在十二袋金幣上分別編上一到十二的編號，再分別從裡頭拿出相 同數量的金幣。把這十二堆的金幣一起拿去秤，然後看它比標準重量差多少即可判斷假幣 在哪一袋裡。 如果假幣在第一袋裡，那秤出來的重量一定比標準重差１公克；若假幣在第二袋裡，由於 我們從裡頭拿出兩枚，所以秤出的重量一定比標準重少２公克，其餘依此類推。 這個問題的變形是，如果假幣可能不只一袋，能否在只秤一次的情況找出呢？ 答案是肯定的。 首先一樣先編號，接著只要從每袋之中取出「２的（編號減一）次方」數量的金幣，一起 拿去秤即可。實際的數量如下： １、２、４、８、１６、３２、６４、１２８、２５６、５１２、１０２４、２０４８ （２的０次方、２的１次方……２的１０次方、２的１１次方） 這些一共是４０９５（用〔２的Ｎ＋１次方〕－１算較快） 也就是標準重是４０９５０公克。 接著只要看秤出來的重量差幾克，然後再算它是由哪些數字組成即可。表面上這邊的計算 有點麻煩，但只要用「２進位」的觀念下去算就行了。 例如秤出來的重量是３９５８７克，那麼── 40950-39587=1363 把1363轉成２進位得： 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 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.194.17.138 ※ 編輯: puzzlez 來自: 123.194.17.138 (11/23 07:28) ※ 編輯: puzzlez 來自: 123.194.17.138 (11/23 07:28) ※ 編輯: puzzlez 來自: 123.194.17.138 (11/23 07:30)