3.2　窮舉算法思想

窮舉算法（Exhaustive Attack method）是最簡單的一種算法，其依賴于計算機的強大計算能力，來窮盡每一種可能的情況，從而達到求解問題的目的。窮舉算法效率并不高，但是適合于一些沒有明顯規(guī)律可循的場合。

3.2.1　窮舉算法基本思想

窮舉算法的基本思想就是從所有可能的情況中搜索正確的答案，其執(zhí)行步驟如下：

（1）對于一種可能的情況，計算其結(jié)果。

（2）判斷結(jié)果是否滿足要求，如果不滿足則執(zhí)行第（1）步來搜索下一個可能的情況；如果滿足要求，則表示尋找到一個正確的答案。

在使用窮舉算法時，需要明確問題的答案的范圍，這樣才可以在指定范圍內(nèi)搜索答案。指定范圍之后，就可以使用循環(huán)語句和條件判斷語句逐步驗證候選答案的正確性，從而得到需要的正確答案。

3.2.2　窮舉算法實例

窮舉算法是最基本的算法思想，下面通過一個簡單的例子來分析窮舉算法的應(yīng)用。雞兔同籠問題最早記載于1500年前的《孫子算經(jīng)》，這是我國古代一個非常有名的問題。雞兔同籠的原文如下：

今有雞兔同籠，上有三十五頭，下有九十四足，問雞兔各幾何？

這個問題的大致意思是：在一個籠子里關(guān)著若干只雞和若干只兔，從上面數(shù)共有35個頭；從下面數(shù)共有94只腳。問籠中雞和兔的數(shù)量各是多少？

1.窮舉算法

上述問題需要計算雞的數(shù)量和兔的數(shù)量，通過分析可以知道雞的數(shù)量應(yīng)該為0～35之間的數(shù)。這樣，可以使用窮舉法來逐個判斷是否符合，從而搜索答案。

采用窮舉算法求解雞兔同籠問題的程序代碼示例如下：

在上述代碼中，輸入?yún)?shù)head為籠中頭的個數(shù)，輸入?yún)?shù)foot為籠中腳的個數(shù)，chicken為保存雞的數(shù)量的變量，rabbit為保存兔的數(shù)量的變量。該方法循環(huán)改變雞的個數(shù)，然后判斷是否滿足腳的個數(shù)條件，當(dāng)搜索到符合條件的答案后，返回1；否則返回0。

2.窮舉算法求解雞兔同籠問題

學(xué)習(xí)了前面的窮舉法求解雞兔同籠問題的算法，下面給出完整的窮舉法求解雞兔同籠問題的程序代碼。代碼示例如下：

【程序3-1】

在該程序中，首先由用戶輸入頭的數(shù)量和腳的數(shù)量，然后調(diào)用窮舉法求解雞兔同籠問題的方法，最后輸出求解的結(jié)果。

執(zhí)行該程序，按照題目的要求輸入數(shù)據(jù)，執(zhí)行結(jié)果如圖3-1所示。可知，籠中有23只雞和12只兔子。