智力測驗 - 金幣問題 (二) | 小殘的程式光廊

問題

有金幣六袋，不知道有幾袋真幾袋假，真的金幣重 10 克，假的重 9 克。給你一個電子秤，只能秤重一次，就知道哪幾袋是假的？

提示

不是天秤，這可以秤出重量。

解法

這題可以透過二進位表示法來解，將每袋編號並取出 2 的編號減 1 冪次方的金幣進行秤重，如下表所示：

袋子編號 (相當於二進位位數)	6	5	4	3	2	1
取出的金幣數 (相當於二進為轉為十進位值)	32	16	8	4	2	1

我們先以全部為假幣維基準點 (63 * 9 = 567 克)，任一袋為真時，則比基準點多出該袋取出金幣數的克重，例如 1 號為真，會有一枚真金幣，也就會多 1 克 (568 克)；當 1 號與 2 號為真，會多 3 克…

實際判斷時，是以秤重得到的重量反推組合，將多出的克重轉為二進位數字即可得知對應的袋子：

如果多 63 克，轉為二進位為 111111，表示全部為真。
如果多 62 克，轉為二進位為 111110，表示只有 1 號是假。
如果多 61 克，轉為二進位為 111101，表示只有 2 號是假。
如果多 60 克，轉為二進位為 111100，表示 1 號和 2 號是假。
…
如果多 0 克，轉為二進位為 000000，表示全部為假。