秤出最輕的兩個金幣

2011-12-16 10:34 pm
我有一個天平, 和64個重量完全不相同的金幣, (如最輕的100.1g, 最重的106.4g), 那麼最少秤多少次, 才能秤出最輕的兩個?如何秤出?
更新1:

多謝"自由自在" 的答案, 很精彩, 我想再問, 如果不是64個, 而是99個, 那麼如何解決?

回答 (1)

2011-12-17 5:09 am
✔ 最佳答案
將64個金幣分別標籤,把它們分為32組,以天平找出每組較輕的一個,並記錄每次比較過程 把32個較輕的再分為16組,重複比較重量,及記錄過程.如此重複直到找出最輕的一個,共經過6輪比較(32,16,8,4,2,1)找出最輕的一個後,複查之前6輪比較記錄,曾經和最輕一個比較過重量的,都有可能是第二最輕的.(給其它金幣淘汰的,必重於淘汰它的那一個金幣,而淘汰它的又不是最輕的一個,所以不可能是第二輕的.) 這6個各自比較重量,需要5次比較找出第二輕的.所以找出最輕兩個最小需要比較32 + 16 + 8 + 4 + 2 + 1 + 5 = 68次

2011-12-17 15:35:20 補充:
第1輪,49組,一個輪空,比較後餘下50個
第2輪,25組,沒輪空, 比較後餘下25個
第3輪,12組,一個輪空, 比較後餘下13個
第4輪,6組,一個輪空, 比較後餘下7個
第5輪,3組,一個輪空, 比較後餘下4個
第6輪,2組,沒輪空, 比較後餘下2個
第7輪,1組,沒輪空, 比較後得最輕者
7輪共98次比較,找出被最輕淘汰的,可能有3-7個(有機會最輕者曾最多輪空4次),所以找第二輕者,需要2-6輪比較.幸運的最小只需98+2=100次,最多不用多於98+6=104次


收錄日期: 2021-04-23 23:26:03
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20111216000051KK00299

檢視 Wayback Machine 備份