NOIP提高組初賽歷年試題及答案閱讀題篇

1、NOIP提高組初賽歷年試題及答案閱讀題篇閱讀程序?qū)懡Y(jié)果（共4題，每題8分，共計32分）閱讀程序的最好方法并非是依次從頭到尾。程序不像迷語，我們無法從末尾幾頁找到答案，也不像一本引人入勝的書籍，只需直接翻到褶皺最多的那幾頁，我們就能找到最精彩的片斷。因此我們在閱讀程序時，最好逐一考察研究每一段代碼,搞清楚每一段代碼的來龍去脈，理解每一段代碼在程唐中所起的作用，進(jìn)而形成一個虛擬的程序結(jié)構(gòu)，并以此為基礎(chǔ)來進(jìn)行閱讀。1、分層讀：高層入手，逐層深入，正確理解程序。2、寫注解：固化、總結(jié)、提煉已有的理解成果。3、先模擬：根據(jù)代碼順序跟蹤變量，模擬運算。4、找規(guī)律：先模擬幾次循環(huán)后，找出背后的規(guī)律。5、看功

2、能：從代碼結(jié)構(gòu)和運算結(jié)果判斷程序功能。6、猜算法：有時不知道算法，通過結(jié)構(gòu)和函數(shù)猜一猜。7、換方法：了解程序本質(zhì)后，換一個熟悉的方法試試。對大多數(shù)人來說，寫程序是令人開心的一件事情，讀別人的程序卻很痛苦，很恐懼，寧愿自己重寫一遍。其實讀到好的程序，就像讀一篇美文，令人心曠神怡，豁然開朗，因為這背后是一個人的思維，甚至整個人生。閱讀別人的程序不僅可以鞏固自己的知識，啟發(fā)自己的思維，提升自己的修養(yǎng)，讓你收獲滿滿，其實，這也是在學(xué)習(xí)、在競賽、在工作中的最重要、最常用的基本功。如果說寫程序是把自己的思維轉(zhuǎn)化為代碼，讀程序就是把代碼轉(zhuǎn)化為你理解的別人的思維。當(dāng)你閱讀程序時有強(qiáng)烈的代入感，像演員一樣，真正

3、進(jìn)入到編劇的精神世界，面部表情也隨之日漸豐富起來。祝賀你！你通關(guān)了！總之，看得多，碼得多，拼得多，你就考得多NOIP2011-1.usMg八Mespacestd;cotstMtSIZE=1(9(9;mtMai八0(Znt八/，小xmS/NEJ;cM人;foi二工;k=八;i+)ci八x;久岡；)i=O;Sum-C;wkc(sufrvW/2”)i+；Si/v+二ij;con僅ieU;returnO;1輸入:一步步模擬，注意輸出的是弘多超出循環(huán)條件時的i值（中位數(shù)），而不是少，也不是123456a1232120(11/2+1)=61=1si.iiD=O+aLl=li=2suiTHl+a2=3i二3

4、suirF3+a3=6打印，3輸出：3NOIP2011-2.#inc【b(deusingiaiespacestd;int八；voidf2(i八txj八ty);voidxj八ty)(f2(9網(wǎng));1voidf2（intX/認(rèn)亡y）（coutx/&x+9）;1mtkvai（）（ci八八;爾?？冢籸eturnO;）輸入：30此為簡單的遞歸題，依次輸出f2（xg）中的x值，注意邊界條件時f*x,9）的x=3。打91)030打印g1fl(L2)130f23)打印：2fl5)330f2$打?。?fl13)8302(1221)打印，13flgL34)213。2(3455)打?。?4H(55,89)5530

5、答案，1251334咦！這不是隔一個輸出一個的F曲。八牝6嗎?輸出：2251334NOIP2011-3.#Mc(tAde“sing八amespacestd;c。八st認(rèn)tV=1OO;mt八.hoolvisitedV;voiddfs(7八七xj八力。八)(mtgvisitedx=true；if(/e八a八s)a八s=/g=八;i+)if(&(exj皿=-l)婀ije岡i);visitedx=fake；1mtmm()(Mtij,aRjC；Cmrvm;=八;i+)for(/=lj=mj+)紅眥T；foi二工;(eabj=c；e回同=c;=八;i+)visited二fake；。八s二。；foi=*;k

6、=八;i+)dfs(iQ);co僅八s八山;return。；)輸入：4612rO203 45(94 14013SO246。一看就知這是深搜算法（DFS）,輸入是個四個頂點的無向圖（鄰接矩陣如下）：如他八a八則即$二他八,可以說明這是個在圖中用DFS找最長的路徑的程序.PFS以任意點作為起點，找一條路徑，本次走過的點不走，找到?jīng)]路走為止。由于就4個點，最多就走3條邊，看看最長的那3條，結(jié)果如下圖：輸出：rsoNOIP2011-4.#認(rèn)elude#izcudeusi八g八akvespcestd)c。八stRSIZE二工。O。;costi八七LENGTH二工。;Mt八jkvjaS/NEjLEN6TT

7、Hj;mtk。八七v)(mta八$/;a八s二。；foi二1;i=八;i+)if（a八殲4；returna八s；mt（mtsum/tj;cM八;m=l;while（工）（wke（k=八）&（可。=工）i；咐八）break;m4-+；對口/;for。=i+Lj=八加+）。收川卜以收-勾/J;Sum4-=h（rj）；cosFve八W/;return。）輸入：7根據(jù)wke（2）的程序功能模擬幾行看看，觀察八的。-2矩陣，此矩陣其實就是所有7位的二進(jìn)制數(shù)（順序左右顛倒），小二2八八。再根據(jù)的程序功能判斷出本程序的目的。nm1234567iii10000000210000003|-|1C)()01;04

8、1100000500100006I01000070110000811100009000100099t91281111111每一列中有2八八T個1和。，在一列里每個1都有2效八-1）個。與它不同，同樣每個。也有27八T）個1與它不同，即每列的結(jié)果為272八-2）*2=2八（2八-為，隊列的結(jié)果為八大2A（2八-1），所以本題的結(jié)果為2A工:3*70輸出：5-7344NOIP2012-1.#認(rèn)eludeusingiaiespacestd;mth/亡0??？戶小必8;（cM人;for（7二1;k=八;+）for（7二1;k=八T;i）為兒tCkvxp二a。；ai=叩+為；叩+為二笈岬；）for（i二八

9、力=2;i-）此哂叩-功（叩一勾二笈岬；for（i=2；i二八-&a+）Sum十二口；coksm/-2）八山；returnO;1輸入：84。70SO702。401O30兩輪冒泡，掐頭去尾，求均值。數(shù)據(jù)量不大，就直接模擬吧，速度也挺快的。12345678a40705070204010301-1i二24050707020401030i=31=44050702070401030i二540507020407010301-64050702040107030i二7405070204010307012345678a40507020401030701=81=7i=64050702010403070i=5405

10、0701020403070i二44050107020403070i=34010507020403070i=2104050702040307012345678a1040507020403070su40+50+70+20+40+30=250sum/(n-2)=250/(8-2)=41輸出：41NOIP2012-2.usingaiespacestd;mt八八s；i八tgcd(認(rèn)tajntb)(=二6)returnb;elsereturnged色a%。)；)i八七mm()(cM八；a八s=O；for。二力二八;i+)if(gcdg)=i)MS；c。僅*ae八山；returnO;輸入：22。gcd就是求

11、最大公約數(shù)，如果二：則許數(shù)，即求工2。的因子數(shù)。輸出：16NOIP2012-3.#認(rèn)eludeusing八aiAACspacestd;c。八stMtS/ZE二2。；MtdataSlZE;mt八/k/ms；voidmergO（一勾二-Ij+Wa僅kJ;k-;a八纖+;）mtMai八0（ci八）八;h二1;datak-l；a八s二。for。以水=八;i+）人+；datak=l;CO僅。八60八山；returnO;輸入：8繼續(xù)模擬，wke語句中函數(shù)調(diào)用細(xì)心點即可,123h=lans=0data11=2h=lans二1data21=3h=2ans二Idata211=4：h=lans=3data41=5

12、h=2ans=3data411=6h=2ans=4data421=7h=3ans=4data421i=8h=lans=7data8輸出：7輸入：282對前面的模擬進(jìn)行觀察，得出如下規(guī)律后計算：i二2。12二即=5224亡。2=256Wat4刃=128亡4=64=工6=8data7=4a八S=S12-1+2S6-1+128-1+64-1+16-1+8-Z+4-，=2。4輸出：2004NOIP2012-4.#includeI乂歸木際zj：/ai”h向僅來正旺wor。八乂平可制胃耳.“sMg八std;mt/efts2O60Kts2Ojfatkev2。;stringsrtJ2,s3mthMus；voi

13、dca(c(itxJ八七dep)(a八s=。八s+dep*(sxj-%；if(eftsx=O)catc(le(tM,dep+l);if(Q0ktsxJ=O)ca/c(Q?ktsxjWep+2);)/遞歸函數(shù)，返回八s,累出結(jié)點深度*結(jié)點權(quán)值之和void,check(認(rèn)tx)(if(leftsx=O)ckeck(eftsx);S3=SSxj；if(rightsx=O)ckeck(rhtsfxj);1voiddfs(ictX/rvtth)(設(shè)飲二二八)Sg代ceck(。)；if(0=s2)(a八s二。ca做。.)；cota八se八/;1/輸出遞歸函數(shù)，“做。田的值return;)if(eftsx=

14、rightsx-=-1)(/eftsx=th;fatherth=x；d匕(g#+2);father協(xié)卜-1;/eftsx=-1-;1if(rightsx=-1)(rightsx-tk;fatherth=x；fathertk=-2;力gtsxj=-1;)if(fatherx=O)dfs(fatherxLth);1mtrvai八0(a認(rèn)x；/先序遍歷序列cMs2;/中序遍歷序列八二slsize()；ievset(rights-l,sizeof(rigkts);keiA/set(fats-2j/Zeof俏亡hev);1輸入：ABCDEF0CAEDF這是二叉樹的遍歷題，先根據(jù)兩個輸入的遍歷序列確定二叉

15、樹。再根據(jù)遞歸函數(shù)計算六個結(jié)點深度*權(quán)值之和：MS二1*分2*2+3*夕4*2+廣：3+6*：5輸出：SSNOIP2013-1.#認(rèn)elude#incLde認(rèn)g八ai/wespacestd;ivt)(stringStr;cMstfZmt八二stY.size();hoolisPMidroc=true；for(inti=。；i八/2；i+兒if(stri!=str八t-勾)isp同MdYoae二fake；)if(isPla(iiadroie)coutYes。八d(;elsecoutnNone八d/;)輸入：abceecba判斷愉入的是不是一個回文串，字符串左右顛倒，結(jié)果不變,飛123i567sab

16、ceecban=8i=0;i8/2=4i=0str0=str8-0-l=str7i=lstrl=str8-l-l=str6i=2str2=str8-2-1=str5i=3str3=str8-3-l=str4：lsPlalindroine=l輸出：YesNOIP2013-2.#認(rèn)eludeusing八Mespacestd;（mt八M；ciabuv;num=C;for（i=a；I=b；r+）if（a%）=。）|依%6=。）rum+;count八kve八山；return。1輸入：11OOO工。15,1T。范圍內(nèi)同時是i。、15的倍數(shù)有多少？注意去重。LI123415HLoJoIFo。一。q11i30

17、Z100L04-011aIIif1MB0III1輸出：153NOIP2013-3.using八aMespacestd;C。八StintSIZE=mtke0MtSINE，。八s；ci八八;for。認(rèn)ti=。；k八；Z+4-)cMheighti;rum(7=l;forji;j+)(0kt口)&(八laumf/)八見二八)a八s二。；foi八七I=/；i八；+)設(shè)八皿ans=numj;)coutanse八山；returnO;輸入：832S111274119求該字符串的最長上升子序列的長度。輸出：4NOIP2013-4.namespacestd;C。八intSIZE.=1(9(9;mt八Mjp,aSI

18、NEjSIZE,coimt;voidcolour(7八七x,八十g)(Cou八十+;。岡=1;ifXl)&：(ax-ly=O)cotour(x-1g);if的)&(以卜加-勾=。)colour(Xjg-1);ifax八)&x+勾也J=O)colour(x+1,g);if(ykm/9；for(i=1;I=p；i)ciX(J；岡9=1;)ms=O;for(i=1;i=n;+)for(j=1；j=mj+)曲叩加1=O)COlAlt=(9；coloura,jJ)；if(。八SCOlAt)a八sc。八十；cotmtxans八山；returnO)1輸入:6sq1 42 33 44 25 16 37 5-8

19、 49 4根據(jù)輸入的X和9值畫出矩陣，再判斷同一區(qū)域。最多的個數(shù)NOIP2014-1.#，八c/udeusiig八kvespacestd;mt小川八0(mta,/Jtot,clc2;ci八ab；tot-。；for(i=a；i=b；r+)(Cl=i/1。；C2=i%1(9;if(cl+C2)%3=O)亡。6+；一個數(shù)的各位數(shù)之和是3的倍數(shù)，它就是3的倍數(shù)。1couttotC八山；return。；1/統(tǒng)計7T2之間有多少數(shù)是3的倍數(shù)輸入：7”輸出：8NOIP2014-2.#認(rèn)udeusing八aMespacestd;mtfix八（7八亡八jm/HAJum,mtmxA7um）1文檔米源為:從網(wǎng)絡(luò)收集

20、整理.word版本口J編輯.inttot,i;if（八=O）retunal;tot-O;foi=i=/+）tot+-=八（八-i+kvxA/um）;retumtot;）mt小川認(rèn)。（mt八m;cM八m;coutf八（八工）八）e八山；returnO;輸入：63遞歸邊界：當(dāng)八二。時，缶八（八?。喊薔kvjM4XA/M）=2小火力1=（22后）+（2產(chǎn)向+（2,4+（2,S向+（2后向+（2,7=20缶八（2,2,6）=（1/,6）+（2,4,）+（，$,6）+（，6）+（工,74尸1。小八（2產(chǎn)后）=（1）+（1產(chǎn)后）+（工,旬6）+（工17/）=6fM2/b6）=（1萬后）+（1后4）+（九乙

21、6）二3八（2）5后戶（工4遍）+（工74）二工缶八（2,6/6）二（1,7,6）二。缶八（2產(chǎn)后）二（。,44）+（。,6后）+。,6后）+（。,7后）二46八（九4后）=（。,5+（。后）+（。7后尸：3fixM4jS,6）=（O后后）+（。74）=2ftm（1j6,6）=（O,7,6）二：rfcm（2j7j6）二。輸出：2。NOIP2014-3.#認(rèn)cLdeincludeias%八MespacestA;consti八tSIZE=1。;Mtmm()(st力八gdictSlZE;mtrak$IZE;mti八dSIZE;mt八tmp；ci八八；for(i=1;i=h;i+)1文檔米源為:從網(wǎng)絡(luò)

22、收集整理.word版本口J編輯.6a八ki=I；M口=I;ci八dicti)for(i=1;i八；i+)for(j=1;jdictiidj+勾J)=i八W/J;iWJ=M如+；法3+勾二tmp；)/冒泡排序for(i=1；i=h;i)M八k口認(rèn)WR=(;/輸出diet里字符排序后應(yīng)該在的位置for(i=1;i=八；i+)coutraikicout。八dl;returnO;輸入：7ababbbaaaaaacccaa1234567dietaaaababbbaaaaaacccaarank1234567ind1234567胃泡排的撕亍閆jR;j;j+基本就可將出ind的變化情配ind_J7L_J452

23、36lank,也蹦出身噩rank25634_712563471輸出：256347，NOIP2014-4.#認(rèn)eludeusingiaiespacestd;c。八stRSIZE=1OO;ivtWeS/NEj;mt八;mt八ext(7八tnum)(doiif(numK)rvum=1;while(a(iveium=O);returnnum;)intkvM0(mt人ij八m;cM八m;for(i=1;i=八；+)alivei=1;rvum二1;for(i=1;i=八；/+)(for0二工;jm;j+)kvum=八extWfrv);coutnum11H;We八um=O;if(i八)八m=八ext（八m）

24、；1cout。八山;）輸入：113這就是約瑟夫環(huán)問題，22個人圍一圈，從工開始報數(shù)，報到3的出局，再從出局的下一個人開始報1,直到全部出局，依次輸出出局人的編號。輸出：36q1S1。411827NOIP2015-1.同普及組閱讀題NOIP2015-2#認(rèn)加加ias%八MespacestA;structpoint(mtx;Mt9；);mtkvM0(structEXiit可mtb;poi八tC；論0。二1；2;ecx=e.a+e.b；e.c電=e.a*e.b；coute.c.xVe.c.yeM;returnO;輸出：3/注意輸出有逗號NOIP20152同普及組閱讀題NOIP2015-4#認(rèn)db(4

25、e“sing八aMespacestd;voidfui(ckarckar坨)(a-b；(*4)+；)mtkvxai八0(charcl,*p2;cl-A;C2=0;pl=&c，；p2-&c2;p2);coutclc2。八山；returnO)/指針題，注意*“、&、0的區(qū)別。輸出:AbNOIP2015-3.#認(rèn)cLdeincludeusing八Mespacestd;i八七八0(mt/e八)Mx/e八；st力八gsss；mx/cn=O;doci八ss；(e八二sse八gtk。；if(ssO=#)break;if(7e八八)s=ss；=Ie八;)/輸出長度最長的字符串Swhile(true);couts

26、。八山；returnO;輸入：IacitizenofSuha#輸出：citizenNOIP2015-4.#incLdeusMg八ai/vcspacestW;1文檔米源為:從網(wǎng)絡(luò)收集整理.word版本口J編輯.mt八。認(rèn)七八ji八tfroiPoSjtoPos)(Mtt,tot;if(k=0)returnO;for(t=1;t=3;t+)if(t/=卅0MPos&t/=toPos)break;tot=。；tot+=缶八(八-1”%0Mp0Sjt);亡。t+;tot+=八-t,toPos);returntot;)(mt八；cM八；cout八()3)e八山；returnO;輸入：s遞歸邊界：當(dāng)八二。時

27、，ftm(%fromPos/0pos)二。產(chǎn))=(4先*)+分(4九*)1fui廣力=(2咒*)”-+(2八*)二7&監(jiān),*產(chǎn))=)+工+4*產(chǎn))=3fuFv(l*)=(0*)+l+(O/*)=1輸出：31NOIP2016-1.#incl(A&eusing八aMespacestd)i八亡a6=工j2)3,4)S6);pi=O;mt0=5；inttji;while(pipj)alpjl=t；pi+；同一；1for(i=(9;(6;+)coutaiJ;coutc八山；returnO)/倒序輸出，注意逗號輸出：產(chǎn)NOIP2016-2.#認(rèn)eludeusMg八平ce允必mtMai八0(charar00

28、ir00,blOOlOO;st力八gclOO)sWMgtmp；Mt%i=O,j=O)k=O)totaUe.100,letklOO3)ci八八；getK八j亡叫9);for(i=O;i八；/+)get八e*%totaUei=cisize（）;/記錄c。的長度1for（i=O;i砌kjgj）中。k=k+1;j；1=k-記錄:“前的字符的個數(shù)aijk=。；/記錄:“所在的位置k=O;for（j=j+1;j;/記錄終點位置k二。；）for（i=。；i=leitki2.）coutNOJ;/如果:前的字符比”:“后的字符個數(shù)多，輸出NO,eke（k=O;for（j=O;jkhg協(xié)口勾）break;/如果k

29、的值比:“前的字符長度大，即已經(jīng)找完了:前的所有字符，那么退出循環(huán)1if（j=怙八coutNOJ;/如果j的值和:后的字符串長度相等，即在掃描到最后一個點時，無論,前的字符是否被全部找完,都輸出ekecoutYESJ;/如果在找完字符串之前已經(jīng)找到了:前的字符，那么輸出“YES,11cout。八山；returnO;輸入：3ABACDEbFBkBDAR:ACPBrTSARSScve%AtypicalRespiratorySyn.c/rome對！就是判斷冒號前的字母是否在冒號后的字符串中出現(xiàn)，大小寫要區(qū)分，注意有逗號。輸出：YES,NOYES,（注：輸入各行前后均無空格）NOIP2016-3.的八using八aMespqcestd;mt/ps(strihgseq