基本算法枚舉法PPT學(xué)習(xí)教案

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

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

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

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

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

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

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

8、個數(shù)是連續(xù)的，這樣的數(shù)只能是1 1和和8 8。因此，。因此，b1b1，b3b3，b6b6，b8b8這四個格子中數(shù)的放法可以先確定下來：這四個格子中數(shù)的放法可以先確定下來：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對格子中的數(shù)需要驗證。對格子中的數(shù)需要驗證

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; 檢驗當(dāng)前放法是否符合要求檢驗當(dāng)前放法是否符合要求 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頁枚舉法的優(yōu)點枚舉法的優(yōu)點 由于枚舉算法一般是現(xiàn)實生活中問題的由于枚舉算法一般是現(xiàn)實生活