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

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

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

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

4、息求出被除數(shù)和除數(shù)。請(qǐng)根據(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。我們不可能對(duì)我們不可能對(duì)1414個(gè)格子個(gè)格子中的數(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ù)，就可確定整個(gè)算式。枚舉確定整個(gè)算式。枚舉除數(shù)枚舉量較小，我除數(shù)枚舉量較小，我們選

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

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

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

8、個(gè)數(shù)是連續(xù)的，這樣的數(shù)只能是1 1和和8 8。因此，。因此，b1b1，b3b3，b6b6，b8b8這四個(gè)格子中數(shù)的放法可以先確定下來(lái)：這四個(gè)格子中數(shù)的放法可以先確定下來(lái)：2 2，8 8，1 1，7 7或或7 7，1 1，8 8，2 2。接著。接著，我們只需枚舉，我們只需枚舉b2b2、b4b4、b5b5三個(gè)變量，范圍都是三個(gè)變量，范圍都是3 3至至6 6，而，而b7b7可通過(guò)計(jì)算來(lái)可通過(guò)計(jì)算來(lái)得到。得到。 (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對(duì)格子中的數(shù)需要驗(yàn)證。對(duì)格子中的數(shù)需要驗(yàn)證

9、。第15頁(yè)/共20頁(yè)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; 檢驗(yàn)當(dāng)前放法是否符合要求檢驗(yàn)當(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頁(yè)/共20頁(yè)procedure try;var b2,b4,b5,b7:integer; begin for b2:=3 to 6 do 枚舉枚舉b2，b4，b5，計(jì)算，計(jì)算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頁(yè)/共20頁(yè)第18頁(yè)/共20頁(yè)枚舉法的優(yōu)點(diǎn)枚舉法的優(yōu)點(diǎn) 由于枚舉算法一般是現(xiàn)實(shí)生活中問(wèn)題的由于枚舉算法一般是現(xiàn)實(shí)生活