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

《NOIP基礎(chǔ)算法-枚舉、遞推和遞歸》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、NOIP基礎(chǔ)算法綜合重慶巴蜀中學(xué)黃新軍第一部分第一部分第一部分第一部分第一部分第一部分第一部分第一部分枚舉策略枚舉策略枚舉策略枚舉策略枚舉策略枚舉策略枚舉策略枚舉策略一、枚舉法的基本思想一、枚舉法的基本思想一、枚舉法的基本思想一、枚舉法的基本思想?枚舉法的基本思想是根據(jù)提出的問(wèn)題枚舉所有可能狀態(tài)，并用問(wèn)題給定的條件檢驗(yàn)?zāi)男┦切枰模男┦遣恍枰?。能使命題成立，即為其解。?枚舉結(jié)構(gòu)：循環(huán)+判斷語(yǔ)句。二、枚舉法的條件二、枚舉法的條件二、枚舉法的條件二、枚舉法的條件::::?雖然枚舉法本質(zhì)上屬于搜索策略，但是它與后面講的回溯法有所不同。因?yàn)檫m用枚舉法求解的問(wèn)

2、題必須滿足兩個(gè)條件：?⑴可預(yù)先確定每個(gè)狀態(tài)的元素個(gè)數(shù)n；?⑵狀態(tài)元素a1，a2，…，an的可能值為一個(gè)連續(xù)的值域。三、枚舉法的框架結(jié)構(gòu)三、枚舉法的框架結(jié)構(gòu)三、枚舉法的框架結(jié)構(gòu)三、枚舉法的框架結(jié)構(gòu)?設(shè)ai1—狀態(tài)元素ai的最小值；aik—狀態(tài)元素ai的最大值(1≤i≤n)，即a11≤a1≤a1k，a21≤a2≤a2k，ai1≤ai≤aik，……，an1≤an≤ankfora1←a11toa1kdofora2←a21toa2kdo……………………forai←ai1toaikdo……………………foran←an1toankdoif狀態(tài)(a1，…，ai，…，an

3、)滿足檢驗(yàn)條件then輸出問(wèn)題的解；四、枚舉法的優(yōu)缺點(diǎn)四、枚舉法的優(yōu)缺點(diǎn)枚舉法的優(yōu)點(diǎn)?⑴由于枚舉算法一般是現(xiàn)實(shí)生活中問(wèn)題的“直譯”，因此比較直觀，易于理解；?⑵由于枚舉算法建立在考察大量狀態(tài)、甚至是窮舉所有狀態(tài)的基礎(chǔ)上，所以算法的正確性比較容易證明。枚舉法的缺點(diǎn)?枚舉算法的效率取決于枚舉狀態(tài)的數(shù)量以及單個(gè)狀態(tài)枚舉的代價(jià)，因此效率比較低。?“直譯”枚舉：直接根據(jù)題意設(shè)定枚舉對(duì)象、范圍和約束條件。?注意認(rèn)真審題，不要疏漏任何條件例題例題11：砝碼稱重：砝碼稱重(noip1996)(noip1996)【問(wèn)題描述】設(shè)有1g、2g、3g、5g、10g、20g的砝碼

4、各若干枚（其總重<=1000），求用這些砝碼能稱出不同的重量個(gè)數(shù)?！疚募斎搿枯斎?g、2g、3g、5g、10g、20g的砝碼個(gè)數(shù)。【文件輸出】輸出能稱出不同重量的個(gè)數(shù)?！緲永斎搿?10000【樣例輸出】3【分析】根據(jù)輸入的砝碼信息，每種砝碼可用的最大個(gè)數(shù)是確定的，而且每種砝碼的個(gè)數(shù)是連續(xù)的，能取0到最大個(gè)數(shù)，所以符合枚舉法的兩個(gè)條件，可以使用枚舉法。枚舉時(shí)，重量可以由1g,2g,……,20g砝碼中的任何一個(gè)或者多個(gè)構(gòu)成，枚舉對(duì)象可以確定為6種重量的砝碼，范圍為每種砝碼的個(gè)數(shù)。判定時(shí)，只需判斷這次得到的重量是新得到的，還是前一次已經(jīng)得到的，即判重。由于

5、重量<=1000g，所以，可以開(kāi)一個(gè)a[1001]的數(shù)組來(lái)判重。核心參考代碼：核心參考代碼：核心參考代碼：核心參考代碼：readln(a,b,c,d,e,f)forc[1]:=0toado//1g砝碼的個(gè)數(shù)forc[2]:=0tobdo//2g砝碼的個(gè)數(shù)forc[3]:=0tocdo//3g砝碼的個(gè)數(shù)forc[4]:=0toddo//5g砝碼的個(gè)數(shù)forc[5]:=0toedo//10g砝碼的個(gè)數(shù)forc[6]:=0tofdo//20g砝碼的個(gè)數(shù)beginsum:=0;fori:=1to6dosum:=sum+c[i]*w[i];a[sum]:=1;//

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

7、一行，又一個(gè)整數(shù)n（n≤24）?！据敵觥枯敵鑫募atches.out共一行，表示能拼成的不同等式的數(shù)目。例題例題22：火柴棒等式（：火柴棒等式（NOIP2008NOIP2008））【問(wèn)題簡(jiǎn)述】給你n(n<=24)根火柴棒,叫你拼出“A+B=C”這樣的等式,求方案數(shù)?！舅悸伏c(diǎn)撥】本題主要考查對(duì)枚舉法的掌握，可以枚舉A和B的取值，考查等式是否剛好用了24根火柴棒。1S的時(shí)限對(duì)枚舉的范圍有所要求，必須要仔細(xì)分析A和B的取值。例題例題22：火柴棒等式（：火柴棒等式（NOIP2008NOIP2008））?本題最多24根火柴，等號(hào)和加號(hào)共用4根火柴，所以A,B,C

8、這3個(gè)數(shù)字需用20根火柴。我們考查A和B的最大的取值可能：0~9這10個(gè)數(shù)字所用