窮舉法

窮舉法

窮舉法的基本思想是根據題目的部分條件確定答案的大致範圍,並在此範圍內對所有可能的情況逐一驗證,直到全部情況驗證完畢。若某個情況驗證符合題目的全部條件,則為本問題的一個解;若全部情況驗證後都不符合題目的全部條件,則本題無解。窮舉法也稱為枚舉法。

基本信息

基本信息

用窮舉法解題時,就是按照某種方式列舉問題答案的過程。針對問題的數據類型而言,常用的列舉方法一有如下三種:

(1)順序列舉 是指答案範圍內的各種情況很容易與自然數對應甚至就是自然數,可以按自然數的變化順序去列舉。

(2)排列列舉 有時答案的數據形式是一組數的排列,列舉出所有答案所在範圍內的排列,為排列列舉。

(3)組合列舉 當答案的數據形式為一些元素的組合時,往往需要用組合列舉。組合是無序的。

例子如下:在公元五世紀我國數學家張丘建在其《算經》一書中提出了“百雞問題 ”:

“雞翁一值錢5,雞母一值錢3,雞雛三值錢1。百錢買百雞,問雞翁、母、雛各幾何?”這個數學問題的數學方程可列出如下:

Cock+Hen+Chick=100

Cock*5+Hen*3+Chick/3=100

顯然這是個不定方程,適用於窮舉法求解。依次取Cock值域中的一個值,然後求其他兩個數,滿足條件就是解。

該問題的C語言程式算法如下:

int Cock,Hen,Chick; /*定義公雞,母雞,雞雛三個變數*/

Cock=0;

while (Cock

相關詞條

相關搜尋

熱門詞條

聯絡我們