NOIP基礎(chǔ)算法綜合PPT學習課件

NOIP基礎(chǔ)算法綜合,巴蜀中學黃新軍,1,第一節(jié)枚舉算法,2,一、枚舉法的基本思想,枚舉法的基本思想：根據(jù)實際問題設(shè)計多重循環(huán)，一一枚舉所有可能的狀態(tài)，并用問題給定的約束條件檢驗?zāi)男顟B(tài)是需要的，哪些狀態(tài)是不需要的。能使命題成立的狀態(tài)，即為其解。雖然枚舉法本質(zhì)上屬于搜索策略，但是它與后面講的回溯法或?qū)挾葍?yōu)先搜索有所不同。,3,二、枚舉法的條件:,可預(yù)先確定每個狀態(tài)的元素個數(shù)n。如百錢買百雞問題，3文錢一只雞的狀態(tài)元素個數(shù)可預(yù)先確定；可預(yù)先確定每個狀態(tài)元素a1,a2,an的值域。,4,三、枚舉法的框架結(jié)構(gòu),設(shè)a11為狀態(tài)元素ai的最小值；aik為狀態(tài)元素ai的最大值(1=i=n),即狀態(tài)元素a1,a2,an的值域分別為a11=a1=a1k,a21=a2=a2k,ai1=ai=aik,an1=an=ank。for(a1=a11;a1=a1k;a1+)for(a2=a21;a2=a2k;a2+).for(ai=ai1;ai=aik;ai+).for(an=an1;an=ank;an+)if(狀態(tài)(a1,.,ai.,an)滿足檢驗條件)輸出問題的解;,5,四、枚舉法的優(yōu)缺點,枚舉法的優(yōu)點：由于枚舉算法一般是現(xiàn)實問題的“直譯”，且是建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)之上的，因此比較直觀，易于理解，其算法的正確性也比較容易證明。枚舉法的缺點：枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個狀態(tài)枚舉的代價，因此效率比較低。,6,例題1：砝碼稱重,【問題描述】設(shè)有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重=1000），求用這些砝碼能稱出不同的重量個數(shù)?！疚募斎搿枯斎?g、2g、3g、5g、10g、20g的砝碼個數(shù)。【文件輸出】輸出能稱出不同重量的個數(shù)。【樣例輸入】110000【樣例輸出】3,7,例題1：砝碼稱重,【思路點撥】根據(jù)輸入的砝碼信息，每種砝碼可用的最大個數(shù)是確定的，而且每種砝碼的個數(shù)是連續(xù)的，能取0到最大個數(shù)，所以符合枚舉法的兩個條件，可以使用枚舉法。枚舉時，重量可以由1g,2g,20g砝碼中的任何一個或者多個構(gòu)成，枚舉對象可以確定為6種重量的砝碼，范圍為每種砝碼的個數(shù)。判定時，只需判斷這次得到的重量是新得到的，還是前一次已經(jīng)得到的，即判重。由于重量=1000g，所以，可以開一個a1001的數(shù)組來判重,8,例題1：砝碼稱重,偽代碼如下：memset(a,0,sizeof(a);for(c1=0;c1=a;c1+)/1g砝碼的個數(shù)for(c2=0;c2=b;c2+)/2g砝碼的個數(shù)for(c3=0;c3=c;c3+)/3g砝碼的個數(shù)for(c4=0;c4=d;c4+)/5g砝碼的個數(shù)for(c5=0;c5=e;c5+)/10g砝碼的個數(shù)for(c6=0;c6=f;c6+)/20g砝碼的個數(shù)sum=0;for(i=1;i=6;i+)sum=sum+ci*wi;asum=1;/標記for(i=1;i=1000;i+)if(ai)num+;/統(tǒng)計不同重量的個數(shù)coutnum=0）3.n(nn;for(i=1;iai;for(i=1;ixy;sum=0;for(j=x;j=y;j+)sum+=aj;coutsumn;for(i=1;iai;si=si-1+ai;for(i=1;ixy;coutsy-sx-1best)best=sum；/調(diào)整最優(yōu)解由于利用了計算出的結(jié)果，整個算法的時間復(fù)雜度降為O(n4),【例題4】最大子矩陣問題,18,3、提取恰當?shù)男畔⑷菀子^察到，最大子矩陣問題是最大連續(xù)子序列和問題的提升，即將一條線換成一個面，將一維問題提升到二維問題。所以我們計算最大子矩陣的方法就是將一行行的數(shù)進行累加以求得最大值。但是還有一個問題，那就是應(yīng)該如何高效地存儲矩陣？我們可以想到：在一個一維的數(shù)列中，設(shè)數(shù)組bi表示從第1個元素到第i個元素的和，則如果想要求第i個元素到第j個元素的和，只需要計算bj-bi-1的值就行了。由此推廣到二維矩陣，設(shè)bij表示矩陣第j列前i個元素的和，aij表示元素數(shù)據(jù)，則壓縮存儲：for(i=1;iaij;bij=bi-1j+aij;因此，我們可以使用三重循環(huán)求出所有的矩形值，即枚舉起始行i和終止行j，壓縮子矩形成為一行，變成一維求最大字段和問題。即tk=max(tk-1,0)+bjk-bi-1k;時間復(fù)雜度為O(n3),【例題4】最大子矩陣問題,19,核心代碼sum=-0 x7fffffff;for(i=1;isum)sum=tk;coutsumn0時,可以用等號(或大于號、小于號)將Hn與其前面的某些項Hi(0in)聯(lián)系起來，這樣的式子就叫做遞推關(guān)系。,25,解決遞推問題的一般步驟,建立遞推關(guān)系式確定邊界條件遞推求解,26,遞推的形式,順推法和倒推法,27,遞推的應(yīng)用分類,一般遞推問題組合計數(shù)類問題一類博弈問題的求解動態(tài)規(guī)劃問題的遞推關(guān)系,28,例題1：faibonacci數(shù)列,【問題描述】已知faibonacci數(shù)列的前幾個數(shù)分別為0，1，1，2，3，5，編程求出此數(shù)列的第n項。（n=60）,遞推的應(yīng)用（一般遞推問題）,29,遞推的應(yīng)用（一般遞推問題）,【例題2】輸出楊輝三角的前N行【問題描述】輸出楊輝三角的前N行(N10)?！疚募斎搿枯斎胫挥幸恍校?個整數(shù)N(N=2)個盤子時，總是先借助c柱把上面的n-1個盤子移動到b柱上，然后把a柱最下面的盤子移動到c柱上；再借助a柱把b柱上的n-1個盤子移動到c柱上；總共移動hn-1+1+hn-1個盤次。hn=2hn-1+1邊界條件：h1=1,33,思考：Hanoi雙塔問題,34,遞推的應(yīng)用（一般遞推問題）,【例題4】數(shù)的計數(shù)【問題描述】我們要求找出具有下列性質(zhì)數(shù)的個數(shù)(包含輸入的自然數(shù)n)，先輸入一個自然數(shù)n(n1000)，然后對此自然數(shù)按照如下方法進行處理：l.不作任何處理；2.在它的左邊加上一個自然數(shù)，但該自然數(shù)不能超過原數(shù)的一半；3.加上數(shù)后，繼續(xù)按此規(guī)則進行處理，直到不能再而自然數(shù)為止；,35,方法1：用遞推。用hn表示自然數(shù)n所能擴展的數(shù)據(jù)個數(shù)，則：h1=1,h2=2,h3=2,h4=4,h5=4,h6=6,h7=6,h8=10,h9=10。分析上數(shù)據(jù)，可得遞推公式：hi=1+h1+h2+hi/2。時間復(fù)雜度O(n2)。,36,方法2：是對方法1的改進。我們定義數(shù)組s.s(x)=h(1)+h(2)+h(x),h(x)=s(x)-s(x-1)此算法的時間復(fù)雜度可降到O(n)。,37,方法3：還是用遞推。只要做仔細分析，其實我們還可以得到以下的遞推公式：(1)當i為奇數(shù)時,h(i)=h(i-1);(2)當i為偶數(shù)時,h(i)=h(i-1)+h(i/2);,38,【思考】1.若n1和1-3-2-1，共兩種。,42,分析,設(shè)fik表示從小蠻開始，經(jīng)過k次傳到編號為i的人手中的方案數(shù)，傳到i號同學的球只能來自于i的左邊一個同學和右邊一個同學，這兩個同學的編號分別是i-1和i+1，所以可以得到以下的遞推公式：fik=fi-1k-1+fi+1k-1f1k=fnk-1+f2k-1,當i=1時fnk=fn-1k-1+f1k-1,當i=n時邊界條件：f10=1；結(jié)果在f1m中。,43,參考代碼,cinnm;memset(f,0,sizeof(f);f10=1;for(k=1;k=m;k+)f1k=f2k-1+fnk-1;for(i=2;i=n-1;i+)fik=fi-1k-1+fi+1k-1;fnk=fn-1k-1+f1k-1;coutf1mendl;,44,樣例輸入33樣例輸出2具體過程見右圖數(shù)組的填充過程按列,45,遞推的應(yīng)用（組合計數(shù)）,Catalan數(shù)定義：Cn=n+2條邊的多邊形，能被分割成三角形的方案數(shù)，例如5邊型的分割方案有：,46,如圖，有一個正n+2邊形。任取一邊，從這邊的端點開始，依次給頂點編號為：0,1,2,3,.,n,n+1(所取的邊端點編號為:0,n+1)。這樣，除線段所在頂點外，還有n個頂點：1,2,3,n。我們以該線段為三角形的一條邊，另一個頂點為i(1=i=n)。,47,我們設(shè)題意要求的三角形剖分方案數(shù)為H(n)，即除線段頂點(編號0與n+1)外，還有n個頂點時的三角形剖分方案為H(n)。則以頂點0,i為指定線段(上面還有1,2,i-1，共i-1個頂點)的剖分數(shù)位H(i-1)；以頂點n+1，i為指定線段的剖分數(shù)為H(n-i)。根據(jù)乘法原理，以0,i,n+1為一剖分三角形的剖分數(shù)應(yīng)為：H(i-1)*H(n-i)，i=1,2,n，所得的剖分各不相同，根據(jù)加法原理則有：這與Catalan數(shù)C(n)的表達式是一致的。故本題答案為H(n)=C(n)。,48,具體實現(xiàn)時，若直接用上述公式計算，對數(shù)字的精度要求較高?？蓪⑵浠癁檫f推式,再進行遞推計算，并且注意類型的定義要用longlong長整型。,49,Catalan數(shù)的應(yīng)用（部分和序列）,問題：n個1和n個0組成一2n位的二進制，要求從左到右掃描，1的累計數(shù)不小于0的累計數(shù)，試求滿足這條件的數(shù)有多少？【類似1】將n個1和n個-1排成一行，要求第1個數(shù)至第k個數(shù)的累加和均非負，問有幾種排列方法？【類似2】有2n個人排成一行進入劇場。入場費5元。其中只有n個人有一張5元鈔票，另外n人只有10元鈔票，劇院無其它鈔票，問有多少種方法使得只要有10元的人買票，售票處就有5元的鈔票找零？,50,Catalan數(shù)的應(yīng)用（棧NOIp2003）,問題：一個棧(無窮大)的進棧序列為1,2,3,.n，有多少個不同的出棧序列？,51,Catalan數(shù)的應(yīng)用（加括號）,P=A1A2A3An，依據(jù)乘法結(jié)合律，不改變其順序，只用括號表示成對的乘積，試問有幾種括號化的方案？,【分析】P(4)：即4個數(shù)相乘的情況如下：(a1a2)a3)a4);(a1(a2a3)a4);(a1a2)(a3a4);(a1(a2a3)a4);(a1(a2(a3a4)。不失一般性，可以假設(shè)最后一次乘法運算如下：(a1ar)(ar+1an),(1=r=n)。令P(n)表示n個數(shù)乘積的n-1對括號插入的不同方案數(shù)，則：P(n)=p1pn-1+p2pn-2+.+pn-1p1,p1=p2=1有：P(n+1)=p1pn+p2pn-1+.+pnp1(1)令C(k)=P(k+1),k=1,2,n，代入(1)式，有：C(n)=C(0)*C(n-1)+C(1)*C(n-2)+C(n-1)*C(0)=因此，本題的答案為C(n-1)。,52,遞推的應(yīng)用（組合計數(shù)）,錯排問題（經(jīng)典問題）n個數(shù)，分別為1n，排成一個長度為n的排列。若每一個數(shù)的位置都與數(shù)的本身不相等，則稱這個排列是一個錯排。例如，n=3，則錯排有231、312。編寫程序，求n的錯排個數(shù),53,分析,我們設(shè)k個元素的錯位全排列的個數(shù)記做：f(k)。四個元素的錯位排列f(4)我們用窮舉法可以找到如下9個：(4,3,2,1);(3,4,1,2);(2,1,4,3)(4,3,1,2);(2,4,1,3);(2,3,4,1)(4,1,2,3);(3,4,2,1);(3,1,4,2)它們有什么規(guī)律呢？,54,通過反復(fù)的試驗，我們發(fā)現(xiàn)事實上有兩種方式產(chǎn)生錯位排列：,A.將k與(1，2，k-1)的某一個數(shù)互換，其他k-2個數(shù)進行錯排，這樣可以得到(k-1)f(k-2)個錯位排列。,B.另一部分是將前k-1個元素的每一個錯位排列（有f(k-1)個）中的每一個數(shù)與k互換，這樣可以得到剩下的(k-1)f(k-1)個錯位排列。,根據(jù)加法原理，我們得到求錯位排列的遞推公式W(k):,f(k)=(k-1)*(f(k1)+f(k2),分析,55,遞推的應(yīng)用（組合計數(shù)）,【例題】編碼問題【問題描述】編碼工作常被運用于密文或壓縮傳輸。這里我們用一種最簡單的編碼方式進行編碼：把一些有規(guī)律的單詞編成數(shù)字。字母表中共有26個小寫字母a,b,c.,z。這些特殊的單詞長度不超過6且字母按照升序排列。把所有這樣的單詞放在一起，按字典順序排列，一個單詞的編碼就對應(yīng)著它在字典中的位置，例如：a-1;b-2;z-26;ab-27;ac-28;你的任務(wù)就是對于所給的單詞，求出它的編碼。,56,遞推的應(yīng)用（博弈問題）,例題：走直線棋問題。有如下所示的一個編號為到的方格：現(xiàn)由計算機和人進行人機對奕，從到，每次可以走個方格，其中為集=a1,a2,a3,.am中的元素(m=4)，規(guī)定誰最先走到第n格為勝，試設(shè)計一個人機對奕方案，摸擬整個游戲過程的情況并力求計算機盡量不敗。,57,分析,題設(shè)條件：若誰先走到第N格誰將獲勝，例如，假設(shè)S=1,2，從第N格往前倒推，則走到第N-1格或第N-2格的一方必敗，而走到第N-3格者必定獲勝，因此在N，S確定后，棋格中每個方格的勝、負或和態(tài)（雙方都不能到達第N格）都是可以事先確定的。將目標格置為必勝態(tài)，由后往前倒推每一格的勝負狀態(tài)，規(guī)定在自己所處的當前格后，若對方無論走到哪兒都必定失敗，則當前格為勝態(tài)，若走后有任一格為勝格，則當前格為輸態(tài)，否則為和態(tài)。,58,分析,設(shè)1表示必勝態(tài)，-1表示必敗態(tài)，0表示和態(tài)或表示無法到達的棋格。例如，設(shè)N10，S1,2，則可確定其每個棋格的狀態(tài)如下所示：而N10，S2,3時，其每格的狀態(tài)將會如下所示：有了棋格的狀態(tài)圖后，程序應(yīng)能判斷讓誰先走，計算機選擇必勝策略或雙方和（雙方均不能到達目標格）的策略下棋，這樣就能保證計算機盡可能不敗。,59,遞推的應(yīng)用（動態(tài)規(guī)劃中的遞推）,例題：最小傷害把兒站在一個NxN的方陣中最左上角的格子里。他可以從一個格子走到它右邊和下邊的格子里。每一個格子都有一個傷害值。他想在受傷害最小的情況下走到方陣的最右下角。,60,分析,Fij：設(shè)走到(i,j)這格的最小傷害值,aij表示(i,j)這格的傷害值。Fij=min(fi-1j,fij-1)+aij邊界條件：f11=a11fi1=fi-11+ai1(2=i=n)f1i=f1i-1+a1i(2=i=n),61,在一個nm的方格中，m為奇數(shù)，放置有nm個數(shù)，如圖,方格中間的下方有一人，此人可按照五個方向前進但不能越出方格,見右下圖。人每走過一個方格必須取此方格中的數(shù)。要求找到一條從底到頂?shù)穆窂?，使其?shù)相加之和為最大。輸出和的最大值。,遞推的應(yīng)用（動態(tài)規(guī)劃中的遞推),例題：方格取數(shù),62,分析,我們用坐標(x,y)唯一確定一個點，其中(m,n)表示圖的右上角，而人的出發(fā)點是，受人前進方向的限制，能直接到達點(x,y)的點只有(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)。到點(x,y)的路徑中和最大的路徑必然要從(m/2,0)到(x+2,y-1)，(x+1,y-1)，(x,y-1)，(x-1,y-1)，(x-2,y-1)的幾條路徑中產(chǎn)生，既然要求最優(yōu)方案，當然要挑一條和最大的路徑，關(guān)系式如下：Fx,y=MaxFx+2,y-1,Fx+1,y-1,Fx,y-1,Fx-1,y-1,Fx-2,y-1+Numx,y，其中Numx,y表示(x,y)點上的數(shù)字。邊界條件為：,63,動態(tài)規(guī)劃與遞推的關(guān)系,上題實質(zhì)上是采用動態(tài)規(guī)劃來求解,那么與遞推動態(tài)規(guī)劃之間到底是什么關(guān)系呢？我們不妨畫個圖(如下圖)。而通常人們理解的遞推關(guān)系就是一般遞推關(guān)系，故認為動態(tài)規(guī)劃與遞推關(guān)系是兩個各自獨立的個體。,64,動態(tài)規(guī)劃與遞推的關(guān)系,1、一般遞推邊界條件很明顯,動態(tài)規(guī)劃邊界條件比較隱蔽,容易被忽視2、一般遞推數(shù)學性較強,動態(tài)規(guī)劃數(shù)學性相對較弱3、一般遞推一般不劃分階段,動態(tài)規(guī)劃一般有較為明顯的階段,65,遞推進階,【例題1】位數(shù)問題,【問題描述】在所有的N位數(shù)中，有多少個數(shù)中有偶數(shù)個數(shù)字3？由于結(jié)果可能很大，你只需要輸出這個答案mod12345的值。【文件輸入】讀入一個數(shù)N(1=N=1000)【文件輸出】輸出有多少個數(shù)中有偶數(shù)個數(shù)字3。【樣例輸入】2【樣例輸出】73,66,遞推進階,【例題2】鋪磁磚問題,【問題描述】用1x1和2x2的磁磚不重疊地鋪滿Nx3的地板，問共有多少種不同的方案？【文件輸入】輸入一個整數(shù)n（1=N=1000）。【文件輸出】輸出方案數(shù)，由于結(jié)果可能很大，你只需要輸出這個答案mod12345的值?！緲永斎搿?【樣例輸出】3,67,遞推進階,【例題3】路程問題,【問題描述】從原點出發(fā)，一步只能向右走、向上走或向左走。恰好走N步且不經(jīng)過已走的點共有多少種走法？【文件輸入】輸入一個整數(shù)n（1=n=1000）。【文件輸出】輸出走法數(shù)。由于結(jié)果可能很大，你只需要輸出這個答案mod12345的值。【樣例輸入】2【樣例輸出】7,68,遞推進階,【例題4】圓周上的弦,【問題描述】圓周上有N個點。連接任意多條（可能是0條）不相交的弦（共用端點也算相交）共有多少種方案？【文件輸入】輸入一個整數(shù)n（1=N=1000）。【文件輸出】輸出方案數(shù)。由于結(jié)果可能很大，你只需要輸出這個答案mod12345的值。【樣例輸入】4【樣例輸出】9,69,遞推進階,【例題5】矩形中的樹,【問題描述】在網(wǎng)格中取一個Nx1的矩形，并把它當作一個無向圖。這個圖有2(N+1)個頂點，有3(N-1)+4條邊。這個圖有多少個生成樹？【文件輸入】輸入一個整數(shù)n（1c;if(c!=!)rever();coutc;intmain()rever();return0;【樣例輸入】gnauh！【樣例輸出】,77,遞歸的實現(xiàn),采用遞歸方法編寫的問題解決程序具有結(jié)構(gòu)清晰，可讀性強等優(yōu)點，且遞歸算法的設(shè)計比非遞歸算法的設(shè)計往往要容易一些，所以當問題本身是遞歸定義的，或者問題所涉及到的數(shù)據(jù)結(jié)構(gòu)是遞歸定義的，或者是問題的解決方法是遞歸形式的時候，往往采用遞歸算法來解決。,78,遞歸的應(yīng)用,處理遞歸定義或解決方法為遞歸方式的問題解決搜索問題實現(xiàn)分治思想用于輸出動態(tài)規(guī)劃的中間過程,79,1、遞歸定義問題,樹結(jié)構(gòu)是由遞歸定義的。因此，在解決與樹有關(guān)的問題時，常?？梢圆捎眠f歸的方法。,80,2、解決搜索問題,因為搜索產(chǎn)生的節(jié)點成樹狀結(jié)構(gòu)，所以可以用遞歸方法解決。這類例子很多，如“N皇后”問題，全排列，哈密頓回路，圖的可著色性等搜索問題。,81,例題：全排列,【問題描述】編程列舉出1、2、n的全排列，要求產(chǎn)生的任一個數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字【文件輸入】輸入n(1=n=9)【文件輸出】有1到n組成的所有不重復(fù)數(shù)字的序列，每行一個序列,82,分析,我們假設(shè)n=3時，如下圖：位置1可以放置數(shù)字1、2、3；位置2可以放置數(shù)字1、2、3；位置3可以放置數(shù)字1、2、3，但是當位置1放了數(shù)字1后位置2和位置3都不能在放1，因此畫樹的約束條件是：各位置的數(shù)字不能相同。,83,分析,我們畫“解答樹”時，根結(jié)點一般是一個空結(jié)點，根結(jié)點下面的第1、2、3三層分別對應(yīng)位置1、位置2、位置3，用“”標示的分支表示該結(jié)點不滿足約束條件，不能被擴展出來：,84,voidf(intk)/搜索第k層結(jié)點（向第k個位置放數(shù)）inti;if(k=n+1)for(i=1;i=n;i+)coutai;coutendl;/如果搜索到一條路徑，則輸出一種解elsefor(i=1;i=n;i+)/每一個結(jié)點可以分解出n個子結(jié)點；if(bi=0)/如果能生成第k層的第i個結(jié)點；ak=i;/第k個位置為數(shù)字i；bi=1;/標記數(shù)字i已用f(k+1);/擴展第k層的第i個結(jié)點(向第k+1個位置放數(shù))bi=0;/向上回溯，并恢復(fù)數(shù)據(jù),我們用遞歸過程來描述“解答樹”的深度優(yōu)先搜索,85,3、實現(xiàn)分治思想,不難發(fā)現(xiàn)，在各種時間復(fù)雜度為nlogn排序方法中，大都采用了遞歸的形式。因為無論是分治合并排序，還是堆排序、快速排序，都存在有分治的思想。只要分開處理，就可以采用遞歸。其實進行分治，也是一個建樹的過程。,86,例題：表達式求值,由鍵盤輸入一