窮舉算法是程序設計中使用得最為普遍、大家必須熟練把握和正確運用的一種算法。它利用計算機運算速度快、精確度高的特點,對要解決問題的所有可能情況,一個不漏地進行檢查,從中找出符合要求的答案。
用窮舉算法解決問題,通常可以從兩個方面進行分析:
一、問題所涉及的情況:問題所涉及的情況有哪些,情況的種數可不可以確定。把它描述出來。
二、答案需要滿足的條件:分析出來的這些情況,需要滿足什麼條件,才成為問題的答案。把這些條件描述出來。
只要把這兩個方面分析好了,問題自然會迎刃而解。
例 1 : 36 塊磚, 36 人搬。男搬 4 ,女搬 3 ,兩個小兒抬一磚。要求一次全搬完。問需男、女、小兒各若干?
分析 :題目要我們找出符合條件的男生、女生和小孩的人數。答案顯然是一組數據。首先分析一下問題所涉及的情況。對於男生來說,至少要有一人;每個男生可以搬 4 塊磚,那麼 36 塊磚最多 9 個男生足夠,共有 9 種不同取值。同樣,女生有 12 種不同取值。兩個小孩抬一塊磚,至少要有兩個小孩,最多 36 個,並且小孩的人數必須是個偶數,所以小孩的人數可以取 18 種不同的值。最壞情況下,男生、女生和小孩的人數可以是 9 × 12 × 18 = 1944 種不同組合。
知道了問題所涉及的情況有 1944 種,是個確定的數。接下來就要把它描述出來。描述的時候用什麼計算機程序設計語言都可以,我這裡就以 QBASIC 語言為例:假設男生人數為 x ,女生人數為 y ,小孩人數為 z 。可以構建這樣一個三重循環
for x=1 to 9
for y=1 to 12
for z=2 to 36 step 2
循環體
next z
next y
next x
理論上這個循環的循環體將執行 1944 次,我們可以用它來對問題所涉及的 1944 種不同情況逐個進行檢查。
分析完問題所涉及的情況後,第二步就要看看答案需要滿足什麼條件。仔細閱讀一下題目,我們就會發現,答案 x 、 y 、 z 的值必須要同時滿足兩個條件:①總的工作量是 36 塊磚,即: 4x+3y+z/2=36 ;②需要的總人數是 36 人,即: x+y+z=36 。把它描述出來就是: 4x+3y+z/2=36 and x+y+z=36 。滿足這個條件的 x 、 y 、 z 的值就是問題的答案。我們可以在循環體裡面對這個條件進行判定,看它是否滿足,若滿足,就把答案輸出來。源程序如下:
for x=1 to 9
for y=1 to 12
for z=2 to 36 step 2
if 4*x+3*y+z/2=36 and x+y+z=36 then print x,y,z
next z
next y
next x
end
例 2 : A 、 B 、 C 、 D 、 E 五人夜間合伙捕魚,凌晨時都倦怠不堪,各安閒河邊的樹叢中找地方睡著了。日上三竿, A 第一個醒來,他將魚分作五份,把多余的一條扔回河中,拿自己的一份回家去了。 B 第二個醒來,也將魚分作五份,扔掉多余的一條,拿走自己的一份,接著 C 、 D 、 E 依次醒來,也都按同樣的辦法分魚,問五人至少合伙捕了多少條魚?試編程序算出。
分析: 假設五人合伙捕了 x 條魚,則“ A 第一個醒來,他將魚分作五份,把多余的一條扔回河中,拿自己的一份回家”以後,河邊應該還剩 4(x-1)/5 條魚。在這裡,題目為我們提供了一個隱含條件: (x-1)/5 必須是個正整數,否則,就不符合實際情況 , 即: (x-1) mod 5 = 0 必須成立。同樣, B 、 C 、 D 、 E 在分魚的時候也都必須要滿足它。我們不妨取 x 的最小值為 6 ,讓 x 逐漸增加,直到找到一個符合問題要求的答案;根據 (x-1) mod 5 = 0 這個條件, x 的每一次取值,都增加 5 個單位。可以構建一個不定次數的循環
do until < 找到答案 >
判定 x 是否為答案
loop
通過這個循環,我們就可以對每一個 x 的可能情況進行檢查。源程序如下:
rem 初始化
cls
x=6
zd=0
i=0
do until zd=1
rem 判定 (x-1) mod 5 = 0 這個條件是否在五次分魚中都滿足,若都滿足,則置找到答案標志 (zd) 為 1 ;否則,取下一個 x 的值,並置統計變量 i 為 0
if i=5 then
zd=1
else
x = x+5
i=0
endif
rem 初始化標志 wtg (用來標識條件是否被測試通過)
wtg=0
k=x
rem 在每一次分魚中對條件進行判定,並置相應的標志
do until wtg=1 or i=5
if (k-1) mod 5=0 then
k=4*(k-1)/5
i=i+1
else
wtg=1
endif
loop
loop
rem 輸出答案
print x
end