????????蠻力法（brute force methord，也稱窮舉法或者枚舉法）是一種簡單直接地解決問題的方法，常常直接基于問題的描述。所以，蠻力法也是最容易應用的方法。

? ? ? ? 蠻力法所依賴的基本技術(shù)是遍歷（traversal,也稱掃描），即采用一定的策略依次處理待求解問題的所有元素，從而找出問題的解。依次處理所有元素是蠻力法的關(guān)鍵，為了避免陷入重復試探，應保證處理過的元素不再被處理。用蠻力法設計的算法，一般來說，都可以對算法的第一個版本進行一定程度的改進，提高其時間性能，但只能減少系數(shù)，而數(shù)量級不會改變。
????????由于蠻力法需要依次窮舉待處理的元素，因此，用蠻力法設計的算法其時間性能往往也是最低的，典型的指數(shù)時間算法一般都是采用蠻力窮舉。但是，基于以下原因，蠻力法也是一種重要的算法設計技術(shù)：

（1)理論上，蠻力法可以解決可計算領域的各種問題。對于一些非常基本的問題，例如，求一個序列中的最大元素，計算n個數(shù)的和等，蠻力法是一種常用的算法設計技術(shù)。
（2)蠻力法經(jīng)常用來解決一些較小規(guī)模的問題。如果要解決問題的輸入規(guī)模不大，用蠻力法設計的算法其時間是可以接受的，此時，設計一個更高效算法的代價是不值得的。
（3)對于一些重要的問題（例如排序、查找、串匹配），蠻力法可以設計一些合理的算法，這些算法具有實用價值，而且不受輸入規(guī)模的限制。
（4)蠻力法可以作為某類問題時間性能的下界，來衡量同樣問題的其他算法是否具有更高的效率。

應用實例——百元買百雞問題

【問題】已知總金額為100元，公雞5元一只，母雞3元一只，小雞1元三只，一共需要買100只雞，求解公雞、母雞、小雞各多少只？

【想法】設公雞、母雞和小雞的個數(shù)分別為x、y和z，則有以下方程組成立：

?

則百元買百雞問題轉(zhuǎn)換為求方程組的解。應用蠻力法求方程組的解只能依賴試探變量x、y和z的值，驗證x、y和z的某個特定值是否能夠使方程組成立。

【算法】設公雞、母雞和小雞的個數(shù)分別為x、y和z，注意到方程組可能有多個解，需要輸出所有滿足條件的解，設變量count表示解的個數(shù)，算法用偽代碼描述如下：

輸入:無

?輸出：公雞、母雞和小雞的個數(shù)

1. 初始化解的個數(shù)count=0；

2. 循環(huán)變量x從0～20重復執(zhí)行下述操作：

? ? ? ? 2.1 循環(huán)變量y從0～33重復執(zhí)行下述操作：

? ? ? ? ? ? ? ? 2.1.1 z=100-x-y;

? ? ? ? ? ? ? ? 2.1.2 如果5x+3y+z/3=100,則count++;輸出x、y和z的值；

? ? ? ? ? ? ? ? 2.1.3 y++；

? ? ? ? 2.2 x++；

3. 如果count=0,則輸出無解信息；

【算法分析】算法由兩層循環(huán)嵌套組成，基本語句為5x+3y+z/3=100，所以操作執(zhí)行次數(shù)為21X34=714.

【算法實現(xiàn)】

C語言代碼如下：

#include<stdio.h>int main() {int x, y, z; //x、y和z表示 公雞、母雞和小雞的個數(shù) int count = 0; //解的個數(shù)初始化為0for (x = 0; x < 20; x++) //公雞個數(shù)的范圍是0到20{for (y = 1; y <= 33; y++) //母雞個數(shù)的范圍是0到33{z = 100 - x - y; //滿足條件x+y+z=100if ((z % 3 == 0) && (5 * x + 3 * y + z / 3 == 100)) //滿足條件總價為100元，且小雞的個數(shù)應該是3的倍數(shù){count++; //問題解的個數(shù)加一printf("公雞有%d只，母雞有%d只，小雞有%d只\n",x , y, z); //輸出所有解}}}if (count == 0) //無解的情況printf("問題無解");}

?輸出結(jié)果：

//公雞有0只，母雞有25只，小雞有75只 //公雞有4只，母雞有18只，小雞有78只 //公雞有8只，母雞有11只，小雞有81只 //公雞有12只，母雞有4只，小雞有84只

?參考書籍：《算法設計與分析》（第2版）

總結(jié)

以上是生活随笔為你收集整理的蛮力法求解百元买百鸡问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。