NOIP基礎(chǔ)算法--枚舉、遞推和遞歸.ppt

《NOIP基礎(chǔ)算法--枚舉、遞推和遞歸.ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、NOIP基礎(chǔ)算法綜合第一部分枚舉策略一、枚舉法的基本思想枚舉法的基本思想是根據(jù)提出的問題枚舉所有可能狀態(tài)，并用問題給定的條件檢驗?zāi)男┦切枰?，哪些是不需要的。能使命題成立，即為其解。枚舉結(jié)構(gòu)：循環(huán)+判斷語句。二、枚舉法的條件:雖然枚舉法本質(zhì)上屬于搜索策略，但是它與后面講的回溯法有所不同。因為適用枚舉法求解的問題必須滿足兩個條件：⑴可預(yù)先確定每個狀態(tài)的元素個數(shù)n；⑵狀態(tài)元素a1，a2，…，an的可能值為一個連續(xù)的值域。三、枚舉法的框架結(jié)構(gòu)設(shè)ai1—狀態(tài)元素ai的最小值；aik—狀態(tài)元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an

2、1≤an≤ankfora1←a11toa1kdofora2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif狀態(tài)(a1，…，ai，…，an)滿足檢驗條件then輸出問題的解；枚舉法的優(yōu)點⑴由于枚舉算法一般是現(xiàn)實生活中問題的“直譯”，因此比較直觀，易于理解；⑵由于枚舉算法建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)上，所以算法的正確性比較容易證明。枚舉法的缺點枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個狀態(tài)枚舉的代價，因此效率比較低。四、枚舉法的優(yōu)缺點“直譯”枚舉：直接根據(jù)題意設(shè)定枚舉對象、范圍和約束條件。注意認(rèn)真審題，

3、不要疏漏任何條件例題1：砝碼稱重(noip1996)【問題描述】設(shè)有1g、2g、3g、5g、10g、20g的砝碼各若干枚（其總重<=1000），求用這些砝碼能稱出不同的重量個數(shù)?！疚募斎搿枯斎?g、2g、3g、5g、10g、20g的砝碼個數(shù)?！疚募敵觥枯敵瞿芊Q出不同重量的個數(shù)。【樣例輸入】110000【樣例輸出】3【分析】根據(jù)輸入的砝碼信息，每種砝碼可用的最大個數(shù)是確定的，而且每種砝碼的個數(shù)是連續(xù)的，能取0到最大個數(shù)，所以符合枚舉法的兩個條件，可以使用枚舉法。枚舉時，重量可以由1g,2g,……,20g砝碼中的任何一個或者多個構(gòu)成，枚舉對象可以確定為6種重量的砝碼，范圍為每種砝碼的個數(shù)

4、。判定時，只需判斷這次得到的重量是新得到的，還是前一次已經(jīng)得到的，即判重。由于重量<=1000g，所以，可以開一個a[1001]的數(shù)組來判重。核心參考代碼：readln(a,b,c,d,e,f)forc[1]:=0toado//1g砝碼的個數(shù)forc[2]:=0tobdo//2g砝碼的個數(shù)forc[3]:=0tocdo//3g砝碼的個數(shù)forc[4]:=0toddo//5g砝碼的個數(shù)forc[5]:=0toedo//10g砝碼的個數(shù)forc[6]:=0tofdo//20g砝碼的個數(shù)beginsum:=0;fori:=1to6dosum:=sum+c[i]*w[i];a[sum]:=1;/

5、/標(biāo)記end;fori:=1to1000doifa[i]=1theninc(num);//統(tǒng)計不同重量的個數(shù)Writeln(num);【問題描述】給你n根火柴棍，你可以拼出多少個形如“A+B=C”的等式？等式中的A、B、C是用火柴棍拼出的整數(shù)（若該數(shù)非零，則最高位不能是0）。用火柴棍拼數(shù)字0-9的拼法如圖所示：注意：1.加號與等號各自需要兩根火柴棍2.如果A≠B，則A+B=C與B+A=C視為不同的等式（A、B、C≥0）3.n根火柴棍必須全部用上【輸入】輸入文件matches.in共一行，又一個整數(shù)n（n≤24）。【輸出】輸出文件matches.out共一行，表示能拼成的不同等式的數(shù)目。例

6、題2：火柴棒等式（NOIP2008）例題2：火柴棒等式（NOIP2008）【問題簡述】給你n(n<=24)根火柴棒,叫你拼出“A+B=C”這樣的等式,求方案數(shù)?！舅悸伏c撥】本題主要考查對枚舉法的掌握，可以枚舉A和B的取值，考查等式是否剛好用了24根火柴棒。1S的時限對枚舉的范圍有所要求，必須要仔細(xì)分析A和B的取值。例題2：火柴棒等式（NOIP2008）本題最多24根火柴，等號和加號共用4根火柴，所以A,B,C這3個數(shù)字需用20根火柴。我們考查A和B的最大的取值可能：0~9這10個數(shù)字所用的火柴數(shù)為6,2,5,5,4,5,6,3,7,6，很明顯數(shù)字1用的火柴棒最少只要2根，不妨讓B為1，那

7、么A和C最多可以使用18根火柴，而C>=A，滿足條件的A的最大取值為1111。所以枚舉A和B的范圍是從0~1111。為了加快速度，可以將0到2222的所有整數(shù)需要的火柴棒數(shù)目提前算好保存在數(shù)組中。五、枚舉算法的優(yōu)化枚舉算法的時間復(fù)雜度：狀態(tài)總數(shù)*單個狀態(tài)的耗時。⑴提取有效信息；⑵減少重復(fù)計算；⑶將原問題化為更小的問題；⑷根據(jù)問題的性質(zhì)進(jìn)行截枝；⑸引進(jìn)其他算法【例題3】給你n(n<=105)個整數(shù)，然后要有m(m<=105)個詢問。每