輸入 : 32枚外觀看起來都相同的硬幣,其中一枚是偽幣而且其重量與其他31枚不同(輕與重都有可能)
輸出 : 找出這枚偽幣並且決定它是比真幣輕或重
Note 1 : 唯一能使用的工具是一支天秤
Note 2 : 只能使用5次天秤就必需找出偽幣並且決定它是比真幣或重
Note 3 : 若你沒有程式設計基礎,你只要寫出解決的方法,若你有程式設計基礎,請寫出程式。
-----------
這題我訪問過許多人,最後討論出最適合的解法是「曹永維」大大所想出的解法。
因為沒有程式設計基礎,所以會用純敘述方式表達。- 首先,將32枚硬幣分為A堆「10枚」、B堆「10枚」、C堆「10枚」、D堆「2枚」。
- 這題的關鍵性問題是判別偽幣比真幣輕還是重,用接下來的兩次秤可以得出。
- 步驟一(秤兩次):
- 先用A堆和B堆秤,再用A堆和C堆秤,有以下四種情況。
- 1:若ABC三堆皆同重,則可知ABC三堆內皆為真幣,且D堆裡有偽幣。
- 接下來用真幣和D堆內兩幣秤,即可知道偽幣是哪個,且知道偽幣和真幣的重量關係。
- 此路線總共最多只需要秤四次。
- 2:若AB同重,且C比A重(or輕),則偽幣在C內,且偽幣比真幣重(or輕)。
- 3:若A比B重(or輕),且A比C重(輕),則偽幣在A內,且偽幣比真幣重(or輕)。
- 4:若A比B重(or輕),且AC同重,則偽幣在B內,且偽幣比真幣輕(or重)
- 步驟二(秤三次):
- 如果步驟一是2、3、4情況,則繼續到步驟二。
- 找出含有偽幣的堆後,先分成「5」、「5」兩堆互秤(第三次),可得出偽幣在哪邊(因為已經知道偽幣和真幣的重量關係)。
- 剩下5枚硬幣,分成「2」、「2」、「1」三堆,2枚的兩堆互秤(第四次)。
- 若同重,則偽幣是剩下的那枚。
- 若不同重,可得出偽幣在哪堆。
- 剩下2枚硬幣,互秤(第五次)可知誰是偽幣。
- 此問題得出解答如上所述。
- 題外話,一開始有想到一個方法,是一開始分成「8」、「8」、「8」、「8」四堆。
- 其中兩堆互秤,同重則偽幣在另外兩堆,不同重則偽幣在選重的兩堆裡。
- 以此類推,第二次秤,將「4」、「4」、「4」、「4」選兩堆秤,找出偽幣在哪兩堆中。
- 第三次秤,「2」、「2」、「2」、「2」中選出4枚。
- 第四次秤,「1」、「1」、「1」、「1」中選出2枚。
- 第五次秤,拿真幣和其中一枚秤,如同重則偽幣是沒選上那枚,不同重則選上的那枚是偽幣。
- 唯一的問題是,此方法不見得能找出偽幣和真幣的重量關係。
- 若第四次和第五次的結果(或是每次)都是同重,則偽幣與真幣的重量關係無法得出。
- 因此,這個方法被捨棄。
複製代碼 |