http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=33318
這題背後原理是Divide&Conquer演算法，可以推導出只用一行程式的公式
(1)假設N = 8袋, 先分成3、3、2 三大袋(A、B、C)，先拿A、B秤，若A、B平衡，代表C有偽幣；反之A或B裡輕的那一大袋有偽幣
(2)若A是輕的有偽幣，將A袋分成1、1、1三大袋(D、E、F)，先拿D、E秤，假如天秤不穩，代表輕的那一代就是偽幣；反之，F是偽幣
從這過程中，得知不斷將問題兩半切下(Divide)去比對(Conquer)，正是這演算法的精神
至於怎變成公式，跟BigO(演算法複雜度)有關係
這種方法叫做prune & search，典型的演算法就是binary search，每比對一次，就可以去除一半不可能的，留下一半可能的繼續搜尋下去。而這一題，就是希望每秤一次，不管運氣好壞，留下來的越少越好
至於為什麼要取三堆呢?
分兩堆只能砍掉一半；分四堆以上，秤其中兩堆，運氣不好，只能砍掉這兩堆，其他留著繼續秤；分三堆，運氣不管好壞，都只會留下1/3
沒有留言:
張貼留言