免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 發帖

[重要物] c++練習題1之7 偽幣問題(32枚秤5次)

輸入 : 32枚外觀看起來都相同的硬幣,其中一枚是偽幣而且其重量與其他31枚不同(輕與重都有可能)
輸出 : 找出這枚偽幣並且決定它是比真幣輕或重

Note 1 : 唯一能使用的工具是一支天秤
Note 2 : 只能使用5次天秤就必需找出偽幣並且決定它是比真幣或重
Note 3 : 若你沒有程式設計基礎,你只要寫出解決的方法,若你有程式設計基礎,請寫出程式。

-----------

這題我訪問過許多人,最後討論出最適合的解法是「曹永維」大大所想出的解法。
因為沒有程式設計基礎,所以會用純敘述方式表達。
  1. 首先,將32枚硬幣分為A堆「10枚」、B堆「10枚」、C堆「10枚」、D堆「2枚」。
  2. 這題的關鍵性問題是判別偽幣比真幣輕還是重,用接下來的兩次秤可以得出。

  3. 步驟一(秤兩次):
  4. 先用A堆和B堆秤,再用A堆和C堆秤,有以下四種情況。

  5. 1:若ABC三堆皆同重,則可知ABC三堆內皆為真幣,且D堆裡有偽幣。
  6. 接下來用真幣和D堆內兩幣秤,即可知道偽幣是哪個,且知道偽幣和真幣的重量關係。
  7. 此路線總共最多只需要秤四次。
  8. 2:若AB同重,且C比A重(or輕),則偽幣在C內,且偽幣比真幣重(or輕)。
  9. 3:若A比B重(or輕),且A比C重(輕),則偽幣在A內,且偽幣比真幣重(or輕)。
  10. 4:若A比B重(or輕),且AC同重,則偽幣在B內,且偽幣比真幣輕(or重)

  11. 步驟二(秤三次):
  12. 如果步驟一是2、3、4情況,則繼續到步驟二。
  13. 找出含有偽幣的堆後,先分成「5」、「5」兩堆互秤(第三次),可得出偽幣在哪邊(因為已經知道偽幣和真幣的重量關係)。

  14. 剩下5枚硬幣,分成「2」、「2」、「1」三堆,2枚的兩堆互秤(第四次)。
  15. 若同重,則偽幣是剩下的那枚。
  16. 若不同重,可得出偽幣在哪堆。

  17. 剩下2枚硬幣,互秤(第五次)可知誰是偽幣。

  18. 此問題得出解答如上所述。

  19. 題外話,一開始有想到一個方法,是一開始分成「8」、「8」、「8」、「8」四堆。
  20. 其中兩堆互秤,同重則偽幣在另外兩堆,不同重則偽幣在選重的兩堆裡。

  21. 以此類推,第二次秤,將「4」、「4」、「4」、「4」選兩堆秤,找出偽幣在哪兩堆中。
  22. 第三次秤,「2」、「2」、「2」、「2」中選出4枚。
  23. 第四次秤,「1」、「1」、「1」、「1」中選出2枚。
  24. 第五次秤,拿真幣和其中一枚秤,如同重則偽幣是沒選上那枚,不同重則選上的那枚是偽幣。
  25. 唯一的問題是,此方法不見得能找出偽幣和真幣的重量關係。
  26. 若第四次和第五次的結果(或是每次)都是同重,則偽幣與真幣的重量關係無法得出。

  27. 因此,這個方法被捨棄。
複製代碼
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

小貓貓2024了喔!
(點一下露米亞傳送到小貓貓2024大事記)

返回列表