基礎(chǔ)算法(枚舉、貪心、分治策略).ppt

《基礎(chǔ)算法(枚舉、貪心、分治策略).ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在PPT專區(qū)-天天文庫。

1、基礎(chǔ)算法策略長沙市第一中學(xué)曹利國第一部分枚舉策略枚舉策略的基本思想枚舉法，又稱窮舉法，指在一個有窮的可能的解的集合中，一一枚舉出集合中的每一個元素，用題目給定的檢驗條件來判斷該元素是否符合條件，若滿足條件，則該元素即為問題的一個解；否則，該元素就不是該問題的解。枚舉策略的基本思想枚舉方法也是一種搜索算法，即對問題的所有可能解的狀態(tài)集合進(jìn)行一次掃描或遍歷。在具體的程序?qū)崿F(xiàn)過程中，可以通過循環(huán)和條件判斷語句來完成。枚舉法常用于解決“是否存在”或“有多少種可能”等類型的問題。例如，求解不定方程的問題就可以采用列舉法。雖然枚舉法本質(zhì)上屬于搜索策略，但是它

2、與回溯法有所不同。因為適用枚舉法求解的問題必須滿足兩個條件：??????⑴可預(yù)先確定每個狀態(tài)的元素個數(shù)n；⑵狀態(tài)元素a1，a2，…，an的可能值為一個連續(xù)的值域。設(shè)ai1—狀態(tài)元素ai的最小值；aik—狀態(tài)元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofoa2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif狀態(tài)(a1，…，ai，…，an)滿足檢驗條件then輸出

3、問題的解；枚舉策略的基本思想枚舉法的特點(diǎn)是算法比較簡單，在用枚舉法設(shè)計算法時，重點(diǎn)注意優(yōu)化，減少運(yùn)算工作量。將與問題有關(guān)的知識條理化、完備化、系統(tǒng)化，從中找出規(guī)律，減少枚舉量。枚舉方法的優(yōu)化枚舉算法的時間復(fù)雜度：狀態(tài)總數(shù)*單個狀態(tài)的耗時主要優(yōu)化方法：⑴減少狀態(tài)總數(shù)⑵降低單個狀態(tài)的考察代價優(yōu)化過程從以下幾個方面考慮：⑴枚舉對象的選取⑵枚舉方法的確定⑶采用局部枚舉或引進(jìn)其他算法枚舉算法的應(yīng)用例題1：二進(jìn)制數(shù)的分類若將一個正整數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)后，0的個數(shù)多于1的個數(shù)的這類數(shù)稱為A類數(shù)，否則稱為B類數(shù)。例如：（13）10=（1101）2，13為B類數(shù)；（

4、10）10=（1010）210為B類數(shù)；（24）10=（11000）224為A類數(shù)；程序要求：求出1～1000之中（包括1與1000），全部A、B兩類數(shù)的個數(shù)?！痉治觥看祟}是一道統(tǒng)計類題目。解決統(tǒng)計問題的一個常用方法是枚舉法：逐一枚舉所有情況，同時進(jìn)行統(tǒng)計，枚舉結(jié)束時，統(tǒng)計也完成，得到結(jié)果。具體對本題而言，采用枚舉法的正確性與可行性是顯然的，而本題的數(shù)據(jù)規(guī)模又僅為1～1000，所以采用逐一枚舉方法進(jìn)行統(tǒng)計的時間復(fù)雜度是完全可以接受的。枚舉算法的應(yīng)用例題2：01統(tǒng)計例題3：圍巾裁剪（NOI試題）將一個邊長為n(n<=100)的大的正三角形均勻的分成

5、n*n的小三角形，某些小三角形已經(jīng)損壞。求出2個面積最大的（即包含小三角形個數(shù)最多的）2個子正三角形，要求這兩個子正三角形中沒有損壞的小三角形。枚舉算法的應(yīng)用【分析】三角形的分割必定將沿著其分割線分割。由于n〈=100，將每個分割線枚舉一次，最多只有100*3條，所以可以考慮用枚舉求解。枚舉出分割線以后，我們當(dāng)前最重要的任務(wù)就是如何求出上下2個三角形的最大子三角形。我們又可以使用枚舉，以每一個點(diǎn)最為一次頂點(diǎn)，向下擴(kuò)展，求出其可以擴(kuò)展的最大面積。為了減少枚舉次數(shù)，我們可以考慮將其值先計算并保存下來。枚舉算法的應(yīng)用定義變量：lup[I，j]表示以第I

6、行j列的正放著的小三角形為上頂點(diǎn)的最大可擴(kuò)展的面積。ldown[I，j]表示以第I行j列的倒放著的小三角形為下頂點(diǎn)的最大可擴(kuò)展的面積。Up[I，j]表示第I行j列的正放著的小三角形是否損壞。down[I，j]表示以第I行j列的倒放著的小三角形是否損壞。枚舉算法的應(yīng)用容易得出lup，ldown[I，j]的遞推式：min{lup[I+1,j],lup[I+1,j+1]}+1[down[I+1,j]=true]lup[I,j]:=1[down[I+1,j]=false]0[up[I,j]=false]邊界：lup[n，I]：=1min{ldown[I-

7、1,j],ldown[I-1,j-1]}+1[up[I-1,j]=true]ldown[I,j]:=1[up[I-1,j]=false]0[down[I,j]=false]求出了lup，ldown后，算法的設(shè)計就不難了。枚舉算法的應(yīng)用另外，還需要注意的一點(diǎn)是關(guān)于三角形60度的旋轉(zhuǎn)。對于正放著的三角形：xx：=n-y+1yy：=x-（n-xx）對于倒放著的三角形：xx：=n-y+1yy：=x-1-（n-xx）枚舉算法的應(yīng)用例題4：圓桌騎士（IOI試題）在一個8*8的棋盤上，有一個國王和若干個武士。其中，國王走一字步，騎士走馬步。若國王與騎士相會在同

8、一點(diǎn)上，國王可以選擇讓騎士背他走。求一個點(diǎn)，使所有的騎士和國王相距在這個點(diǎn)上的所走的步數(shù)最少。枚舉算法的應(yīng)用【分析】此題可從3個方面考慮