題目：http://poj.org/problem?id=1013
經典問題，有12個銀幣，已知其中一個是假的(重量可能比較重或輕)
現在利用天秤來判斷哪一個是假幣
給出Sally Jones已經秤三次的結果，「保證有且有一組解」
問哪一個是假幣，比真幣輕或重
程式碼：http://codepad.org/ChO4Bo9A
要想設計一個策略總是能測出假幣，難。
但是給了一段保證有解的結果，問假幣是哪個？簡單。
(這就好比隨便給一些整數，想找出一種非空子集令總和是0 是 NP完全問題
但是想驗證一段整數和是不是0就是相當簡單的P問題了)
既然題目已經出成判定答案的形式，不利用就太可惜了
很自然地枚舉假幣、枚舉是輕或重，並設定重量(例如真幣設1，輕幣設0、重則2)
然後一一判斷是否合乎這三條天平結果
因為有且僅有一組解
只要有一種可能讓三個敘述都成立，就是答案！
沒有留言:
張貼留言