稱球問題的通用解法

最近看了個算法題 據說還是google面試題之一，大意是：八個球已知其中有一個是偏重的，問最少幾次稱出來？

之前我在網上還有個更難的，大意是：13個球已知其中有一個重量異常（重或者輕），給一個天平3次稱出那個異常球。

仔細想想 其實這兩個題目是有緊密聯繫的。13球問題的解答需要用到8球問題的解法。

先看看 8球與13球問題的解法：

8球：

先將球8個球分成3堆：3，3，2的形式（3，3是代表在天平兩端的球數）。

1、稱一次找出重的一邊（平衡就只要再稱剩下兩個中重的一個即可，2次搞定）；

2、重的一邊三個球，取出兩個稱：如果平衡則是另一個，不平衡就是重的那個（2次搞定）。

所以，8個球出重的一個球需要兩次。

13球：

把球分成三堆：4，4，5的形式。（5，5，3的分法需要4次）。

1、平衡將5個球分成兩堆（2，3）；

1.1、將分好的三個球替換天平上任意一端得三個球；

1.2、查看天平狀態，如果發生偏移則說明異常球就在這三個中，而且可以知道是輕還是重；如果沒有發生偏移則說明在另外兩個球中；

1.2.1、如果在三個球中間，且知道輕重，則任意取兩個球再稱一次就能找出異常球；

1.2.2、如果在兩個球中不知道輕重，則取正常球一個，再在兩個球中任意取一個稱；如果平衡則是兩個球中的另一個；如果不平衡則是除去正常球以外的另一個；

平衡的情況只要稱三次。

2、不平衡則在5個正常球中取三個與天平上重的一側（輕的一側也行）的4個球中的3個交換

；然後將重的一側4個球中沒有交換的一個球與輕的一側的4個球中任意一個互換；再稱；

這個時候可能出現3種狀態：（注意重的一側的球全部發生了交換！）

2.1、天平保持不變：則說明異常球在天平輕的一側的沒有被交換的3個球之中；這樣就再稱1次便可找出異常球；

2.2、天平平衡：則說明異常球在換下天平的三個球中；而且是重球，這樣再稱1次就能解決；

2.3、天平發生傾覆：則說明異常球在左右互換的兩個球中，而且不知道異常球的輕重；這個時候可以取兩個球中的一個與一個正常球稱；如果平衡則是兩個球中的另一個球；如果不平衡則是正常球以外的另一個。

所以可以看出兩種情況都最多隻要3次就能搞定。

那麼有什麼聯繫嗎？

1、稱13箇中異常的時候在第一次稱不平衡的條件下，互換的過稱實際上是將球的輕重做了區分（因為天平兩邊的交換其實只鐵定只要再稱一次便可）；將異常球的輕重得出來而且鎖定了範圍。這時，問題就退化為“8球問題”了；

2、如果天平平衡，則異常球肯定在天平下的剩餘的球。這個時候將剩下的球分半，一半與天平上的正常球交換，一半不動。其實是一種變形的“13球”問題。因為，分半以後跟交換以後的正常球正好變異成一個球數為(N/2上取整+1)個球的新“13”球問題的稱完一次時的情況。（將分開的球看做天平兩邊不平衡的兩端，交換下來的球看著做天平下的正常球！）

而且肯定稱的次數會比(N/2上取整+1)少1次，所以這樣一來這種情況的稱數是：1+(Recusive F(N/2上取整+1)個球的次數-1)次=F（N/2上取整+1）-F（N）為計算13球問題的函數。根據常識，F（N）>=F（N/2上取整+1）。所以其實這種情況是可以不考慮的！

綜合1，2可以看出，13球問題其實是分組處理以後的8球問題。

這一來可以得出解N個球中稱出一個異常球的通用解法：

將N個球分成3堆，保證形成M,M,M或者M+1,M+1,M或者M,M,M+1的分法（肯定是可以的，因為任何數除3餘數只能是0，1，2，對應上面三種情況。因為這樣能保證重的那邊或者輕的那邊的球都被交換掉！）。

令解“8球”問題的函數為F（X）；則解N球1個異常球的方法是G（x）=2+F（M）。F（X）是一個遞歸函數，每一步都是貪心的。（加2表示做F（）之前其實已經稱了2次了）

這樣一來G（x）=2+F（M）很簡單的形式，解決了複雜的問題。