【益智遊戲】：真假金幣問題_綠翠園_濁水溪畔的國中生部落格

	§網綠翠園站§ 　　濁水溪畔的國中生部落格

主題：【益智遊戲】：真假金幣問題

發表：濁水溪畔的國中生	2012-05-13 16:00:56	閱覽數：39308	(IP: )	T 3493	引　用

回應：濁水溪畔的國中生	2012-05-14 23:17:12	(IP: )	T 3493_R 19	引　用

以下解答，僅供各位前輩先進參考。

首先，是【＃1】暖身問題──已知8個金幣中有1個假金幣，假的較輕。請問用天平最少秤幾次，就可以得知那一個是假金幣？

（1）最【人才】的做法：逐一比對。

1. 將8個金幣編號A1、A2、......A8。
2. 把（A1、A2）分放兩邊秤，若A1＞A2，則A2即為所求；若A1＝A2，則繼續下步驟。
3. 把（A1、A3）分放兩邊秤，若A1＞A3，則A3即為所求；若A1＝A3，則繼續下步驟。
4. 同上述作法，依序逐一相秤（A1、A4）、（A1、A5）……直到碰到比較輕的那個為止。

幸運的話，可能第一次就可以找到假金幣。萬一灰熊衰洨，假金幣正好是最後一個，那麼最糟的情況是──總共要秤7次！

（2）稍微不白爛的做法：兩兩對秤。

1. 每兩個金幣為一組，8個金幣分為（A1、A2）、（B1、B2）、（C1、C2）、（D1、D2）4組。
2. 把（A1、A2）分放兩邊秤，若A1＞A2，則A2即為所求；若A1＝A2，則繼續下步驟。
3. 把（B1、B2）分放兩邊秤，若B1＞B2，則B2即為所求；若B1＝B2，則繼續下步驟。
4. 同上述作法，依序逐一相秤（C1、C2）、（D1、D2）……直到秤到比較輕的那個為止。

幸運的話，可能第一次就找到假金幣。如果衰洨，假金幣正好在最後一組，那麼最糟的情況是──總共要秤4次！

（3）比較聰明的做法：二分法。

1. 將8個金幣平均分成兩組，分別為（A1、A2、A3、A4）及（B1、B2、B3、B4）。
2. 把A組、B組分放兩邊秤，若A組＞B組，則B組包含那個假金幣，繼續下步驟。
3. 同上述作法，再把B組平均分成兩組，分別為（B1、B2）及（B3、B4），並分放兩邊秤。若（B1、B2）＞（B3、B4），則（B3、B4）包含那個假金幣，繼續下步驟。
4. 把（B3、B4）分放兩邊秤，若B3＞B4，則B4即為所求。

持續將金幣【均分對秤】的步驟，只剩兩個金幣時，只要再秤一次即可。不過，若是採用這種做法，就沒有所謂【第一次就找到假金幣】的幸運事了。所以這樣總共要秤3次，也就是㏒2（8）＝3次。（以2為底，8的對數）

（4）更快的做法：

1. 將8個金幣平均分成3組，分別為（A1、A2、A3）、（B1、B2、B3）及（C1、C2）。
2. 把A組、B組分放兩邊秤，若A組＝B組，則C組包含那個假金幣，繼續步驟3；若A組＞B組，則B組包含那個假金幣，繼續步驟4。
3. 把（C1、C2）分放兩邊秤，若C1＞C2，則C2即為所求。
4. 把（B1、B2）分放兩邊秤，若B1＝B2，則B3即為所求；若B1＞B2，則B2即為所求。

每次都儘可能平分成3堆，且至少有兩堆金幣個數相同。先把相同個數的那兩堆拿來秤，如果有一堆比較輕，那一堆一定包含那個假金幣，否則金幣就在沒秤的那一堆；再把包含假金幣的那堆，依上述的相同做法（儘可能平分成三堆……）繼續操作。8個金幣分成3組，此時我們所要處理的數量已從8降到3或2，比上述二分法的策略只降到4有效多了。不過，若是採用這種做法，就沒有所謂【第一次就找到假金幣】的幸運事了。所以這樣總共要秤2次！也就是㏒3（8）＝1.8927892607……，→2次。（以3為底，8的對數）

綜覽全部討論

總　覽版　務政　經健康醫療軍　武理　財文　化藝　文科　技台灣的美旅　遊 PISA 娛　樂鄉　土公　民認　同副　刊哈　啦范氏網

竹縫
視界耳聾
世界泰伯
觀點 Joy
隨筆哈利
天地 Jerry C
鳥世界射水魚
天　空討海人
鏡　頭嘻笑
人間詩情
畫藝老工仔
思　維網網
相連歷史
庫存

* 討論區內之言論，不代表本園之立場，一切法律責任仍由發言者本人負責
* 如果您有任何不當言論，本園有權決定是否保留您所送貼的意見。