1、會計學1基本算法枚舉法基本算法枚舉法第1頁/共20頁第2頁/共20頁第3頁/共20頁時間復雜度怎么算？時間復雜度怎么算？第4頁/共20頁按數量級遞增排列，常見的時間復雜度有：常數階O(1) 對數階O(logn) 線性階O(n),線性對數階O(nlogn) 平方階O(n2) 立方階O(n3) . k次方階O(nk), 指數階O(2n) 第5頁/共20頁時間復雜度為時間復雜度為O（N） 第6頁/共20頁5nvar t,n:integer;nbegin 時間復雜度為時間復雜度為O（logN） 第7頁/共20頁 在程序設計中，我們經常需要根據給定的一組條件求滿足條件的解。如果問題的解可以用公式，或者按

2、一定的規則、規律求出，那么就可以很容易地寫出相應的程序。但是對于許多問題，我們都難以找到明確的公式和計算規則，在這種情況下，我們可以利用計算機高速運算的特點，用窮舉法來求解。在程序設計中，我們經常需要根據給定的一組條件求滿足條件的解。如果問題的解可以用公式，或者按一定的規則、規律求出，那么就可以很容易地寫出相應的程序。但是對于許多問題，我們都難以找到明確的公式和計算規則，在這種情況下，我們可以利用計算機高速運算的特點，用窮舉法來求解。 基本思想：基本思想： 窮舉也叫枚舉，它的基本思想是先依據題目的窮舉也叫枚舉，它的基本思想是先依據題目的部分條件部分條件將所有將所有可能解可能解列舉出來，然后用列

3、舉出來，然后用其余的條件其余的條件對所有可能解進行一一對所有可能解進行一一驗證驗證，刪去那些不符合條件的解，剩下符合條件的解就是整個問題的解。，刪去那些不符合條件的解，剩下符合條件的解就是整個問題的解。 適用枚舉法求解的問題必須滿足兩個條件適用枚舉法求解的問題必須滿足兩個條件: : 1 1、可事先確定、可事先確定解元素解元素的個數的個數n n； 2 2、解變量解變量，n n的可能值為一個連續的值域。的可能值為一個連續的值域。第8頁/共20頁怎么樣買法，才能剛好用一百塊錢買一百只雞？舉各種雞的個數。第9頁/共20頁第10頁/共20頁 設有下列的除法算式：設有下列的除法算式： 請根據上述算式中的信

4、息求出被除數和除數。請根據上述算式中的信息求出被除數和除數。 其它信息：其它信息： 設除數為設除數為x x，被除數為，被除數為y y，則，則10=x=9910=x=99，1000=y=99991000=y=9999，且，且8 8* *x=99x=100 x=100。我們不可能對我們不可能對1414個格子個格子中的數都進行枚舉，本題的中的數都進行枚舉，本題的關鍵在于找出適當的元素進關鍵在于找出適當的元素進行枚舉。行枚舉。 本題已給出了商本題已給出了商和余數，只要再知道和余數，只要再知道被除數或除數，就可被除數或除數，就可確定整個算式。枚舉確定整個算式。枚舉除數枚舉量較小，我除數枚舉量較小，我們選

5、擇枚舉除數，而們選擇枚舉除數，而被除數則可按公式被除數則可按公式y=809y=809* *x+1x+1計算得出計算得出。第11頁/共20頁var x,y:integer;begin for x:=10 to 99 do begin y:=（）（）; 計算出被除數計算出被除數 if y9999 then break;優化語句優化語句 if （）then writeln(y, ,x); end;end.運行結果：運行結果：9709 129709 12枚舉所有可能的除枚舉所有可能的除數數 驗證驗證 窮舉法是一種比較笨拙的算法，因為它需要列舉出許多個可能解來一一驗證，窮舉法是一種比較笨拙的算法，因為它

6、需要列舉出許多個可能解來一一驗證，程序往往需要運行很長時間，效率較低。程序往往需要運行很長時間，效率較低。 針對窮舉法效率較低的缺點，在設計窮舉算法時，我們必須注意以下二點：針對窮舉法效率較低的缺點，在設計窮舉算法時，我們必須注意以下二點： 減少枚舉變量：充分挖掘各解元素之間的聯系，將一些非枚舉不可的解元素減少枚舉變量：充分挖掘各解元素之間的聯系，將一些非枚舉不可的解元素列為枚舉變量，然后在此基礎上直接計算出其它解元素的可能值。列為枚舉變量，然后在此基礎上直接計算出其它解元素的可能值。 減少枚舉變量的值域：枚舉前要盡可能多地將不符合條件的情況預先排除。減少枚舉變量的值域：枚舉前要盡可能多地將不

7、符合條件的情況預先排除。 809*x+1(y=1000) and (8*x=100)第12頁/共20頁第13頁/共20頁第14頁/共20頁 如下圖所示的八個格子中填入如下圖所示的八個格子中填入1 1至至8 8八個數字，使得相鄰的和對角線的數字之差不為八個數字，使得相鄰的和對角線的數字之差不為1 1。請編程找出所有放法。請編程找出所有放法。 b1b1 b2b2b3b3b4b4b5b5b6b6b7b7 b8b8 分析：分析： 由題意可知，放入由題意可知，放入b3b3，b6b6這兩個格子中的數，必須和六個數不連續，這兩個格子中的數，必須和六個數不連續，僅可以和一個數是連續的，這樣的數只能是僅可以和一

8、個數是連續的，這樣的數只能是1 1和和8 8。因此，。因此，b1b1，b3b3，b6b6，b8b8這四個格子中數的放法可以先確定下來：這四個格子中數的放法可以先確定下來：2 2，8 8，1 1，7 7或或7 7，1 1，8 8，2 2。接著。接著，我們只需枚舉，我們只需枚舉b2b2、b4b4、b5b5三個變量，范圍都是三個變量，范圍都是3 3至至6 6，而，而b7b7可通過計算來可通過計算來得到。得到。 (1,2),(1,4),(2,5),(4,7),(5,8),(7,8)(1,2),(1,4),(2,5),(4,7),(5,8),(7,8)共共6 6對格子中的數需要驗證。對格子中的數需要驗證

9、。第15頁/共20頁constconst link:array1.6,1.2 of link:array1.6,1.2 of integerinteger=(1,2),(1,4),(2,5),(4,7),(5,8),(7,8);=(1,2),(1,4),(2,5),(4,7),(5,8),(7,8);var var b:array1.8 of integer;b:array1.8 of integer;存放擺放方案存放擺放方案 procedure print; procedure print; 輸出一種滿足條件的放法輸出一種滿足條件的放法 begin begin writeln(b1:4);

10、writeln(b1:4); writeln(b2:2,b3:2,b4:2); writeln(b2:2,b3:2,b4:2); writeln(b5:2,b6:2,b7:2); writeln(b5:2,b6:2,b7:2); writeln(b8:4); writeln(b8:4); writeln; writeln; end; end;function choose:boolean; function choose:boolean; 檢驗當前放法是否符合要求檢驗當前放法是否符合要求 var var i:integer;i:integer; begin begin choose:=fals

11、e; choose:=false; for i:=1 to 6 do for i:=1 to 6 do if abs( blinki,1 - blinki,2 )=1 then exit; if abs( blinki,1 - blinki,2 )=1 then exit; choose:=true; choose:=true; end; end;第16頁/共20頁procedure try;var b2,b4,b5,b7:integer; begin for b2:=3 to 6 do 枚舉枚舉b2，b4，b5，計算，計算b7 for b4:=3 to 6 do if b2b4 then for b5:=3 to 6 do if (b5b2)and(b5b4) then begin b7:=18-b2-b4-b5; b2:=b2;b4:=b4;b5:=b5;b7:=b7; if choose then print; end; end;第17頁/共20頁第18頁/共20頁枚舉法的優點枚舉法的優點 由于枚舉算法一般是現實生活中問題的由于枚舉算法一般是現實生活