3.4.1　求解“雞兔同籠”問題

有了條件分支和循環遍歷這兩類基本的流程控制，我們就能通過Java編程來解決復雜一點的問題了。現在通過一個階段性的實戰練習幫助大家加深對流程控制語句的理解。

在南北朝時期成書的數學著作《孫子算經》中，有一道趣味的“雞兔同籠”問題，題干是“今有雉兔同籠，上有三十五頭，下有九十四足，問雉兔各幾何？”這段文言文翻譯成白話文，意思是：籠子里關著一群雞和兔子，上面有35個頭，下面有94條腿，請問雞和兔子各有幾只？顯然這是一個二元一次方程組，列出代數方程式求解即可。按照中學課本里的常規解法，假設雞的數量為x，兔子的數量為y，則有等式x+y=35（35個頭）。又因為雞有兩條腿，兔子有4條腿，所以存在等式2x + 4y=94（94條腿）。結合x+y=35與2x+4y=94兩個等式構成的方程組，很容易采取代數手段求得x=23且y=12，即籠子里有23只雞加12只兔子。

不過代數方程式是西方的舶來品，中國的古人并不認識，我們的祖先使用另一種巧妙的辦法，同樣成功解開了雞兔同籠問題。我國數學家命令籠子里的雞和兔子都抬起一半的腿，于是兩條腿的雞抬起一條腿，4條腿的兔子抬起兩條腿，瞬間籠子里站著的腿只剩下94的一半，也就是47條腿。這時每只兔子比每只雞還多一條站立的腿，同時兔子跟雞都只有一個頭，那么籠子里腿的數量減去頭的數量，必然等于兔子的數量。據此求得，兔子的個數=還站著的腿數量-頭的數量=47-35=12，雞的個數=頭的數量-兔子個數=35-12=23。

無論是西方的方程式解法，還是東方的命令式解法，都依賴于解題者的算術素養，通過某種精巧的思路求得題解。然而程序代碼非常笨，只會基本的加減乘除，即使引入牛頓迭代法，也只能求解一元N次方程的方根，你讓它去計算二元一次方程組，沒見過世面的程序還真要束手無策了。但計算機程序有一個優點，它的運算速度非常快，一秒鐘能開展億次運算，俗話說“笨鳥先飛”，計算機程序正是如此。雖然程序沒有人那么聰明，可是笨辦法總是會的，比如使用簡單的窮舉法把二元方程式可能的解一個一個試過去，只要方程式存在合理的解，窮舉法就一定能夠試出方程解。

就雞兔同籠問題而言，雞加上兔子的總數為35，意味著雞的數量范圍是0～35，真實的雞個數必定是其中一個數字。那么我們可以設計一個循環語句，讓雞的個數從0開始算起，則兔子的個數=35-雞的個數，于是全部腿的數量=雞的個數×2+兔子的個數×4=94。這里的等式依然包含兩個變量，分別是雞的個數和兔子的個數，看起來仍是二元方程式，但運用了窮舉法之后，在每次循環里面雞的個數都是確定的（從0開始遞增），兔子的個數也是確定的，代碼只需判斷表達式“雞的個數×2+兔子的個數×4”的結果是否等于94。一旦發現腿的數量的計算結果符合條件，就表示本次循環預設的雞的個數與兔子的個數正好是雞兔同籠問題的答案。

根據以上的窮舉法思路，編寫對應的循環處理代碼示例如下（完整代碼見本章源碼的src\com\control\Jitutonglong.java）：

    // 今有雉兔同籠，上有三十五頭，下有九十四足，問雉兔各幾何？
    int chick, rabbit;  // chick表示雞的數量，rabbit表示兔子的數量
    int sum=35;  // 雞和兔子加起來一共35只
    for (chick=0, rabbit=0; chick <= sum; chick++){  //利用窮舉法逐個嘗試可能的雞兔組合
        rabbit=sum - chick;  // 計算兔子的數量
        if (chick * 2 + rabbit * 4 == 94) {  // 若滿足雞兔同籠的問題條件，則結束循環
            break;
        }
    }
    System.out.println("雞的數量為" + chick + "，兔子的數量為" + rabbit);

別看窮舉法很傻，上面的幾行代碼分別運用了條件判斷與循環操作兩種控制語句，足以逐個篩查所有可能的雞兔組合，并找到正確的問題答案。運行以上的窮舉法代碼，可以觀察到以下的輸出日志：

雞的數量為23，兔子的數量為12

從日志可見，利用窮舉法成功求得了雞兔各自的數量，而且上述代碼的解法適用于任何二元一次方程組，如果將代碼里的35與94換成其他數字，那么這段代碼仍然能夠求出正確的方程解（只要存在的話）。