程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> 窮舉算法解題的一般思路

窮舉算法解題的一般思路

編輯:C語言基礎知識
窮舉算法是程序設計中使用得最為普遍、大家必須熟練把握和正確運用的一種算法。它利用計算機運算速度快、精確度高的特點,對要解決問題的所有可能情況,一個不漏地進行檢查,從中找出符合要求的答案。 用窮舉算法解決問題,通常可以從兩個方面進行分析: 一、問題所涉及的情況:問題所涉及的情況有哪些,情況的種數可不可以確定。把它描述出來。 二、答案需要滿足的條件:分析出來的這些情況,需要滿足什麼條件,才成為問題的答案。把這些條件描述出來。 只要把這兩個方面分析好了,問題自然會迎刃而解。 例 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
 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved