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

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

2、，模擬運(yùn)算。 先模擬幾次循環(huán)后，找出背后的規(guī)律。 從代碼結(jié)構(gòu)和運(yùn)算結(jié)果判斷程序功能。有時(shí)不知道算法，通過(guò)結(jié)構(gòu)和函數(shù)猜一猜。 了解程序本質(zhì)后，換一個(gè)熟悉的方法試試。對(duì)大多數(shù)人來(lái)說(shuō)，寫(xiě)程序是令人開(kāi)心的一件事情， 讀別人的程序卻很痛苦，很恐 懼，寧愿自己重寫(xiě)一遍。其實(shí)讀到好的程序，就像讀一篇美文，令人心曠神怡， 豁然開(kāi)朗，因?yàn)檫@背后是一個(gè)人的思維，甚至整個(gè)人生。閱讀別人的程序不僅可以鞏固自己的知識(shí)，啟發(fā)自己的思維，提升自己的修養(yǎng)， 讓你收獲滿(mǎn)滿(mǎn)，其實(shí)，這也是在學(xué)習(xí)、在競(jìng)賽、在工作中的最重要、最常用的基 本功。如果說(shuō)寫(xiě)程序是把自己的思維轉(zhuǎn)化為代碼， 讀程序就是把代碼轉(zhuǎn)化為你理解的別 人的思維。當(dāng)你閱讀

3、程序時(shí)有強(qiáng)烈的代入感，像演員一樣，真正進(jìn)入到編劇的精 神世界，面部表情也隨之日漸豐富起來(lái)。祝賀你！你通關(guān)了！ 總之，看得多，碼得多，拼得多，你就考得多NOIP2011-1 .#in elude vip會(huì)員免費(fèi)#in elude vestri ngusing n ames pace std;con st int SIZE = 100;int mai n()int n ,i,sum,x,aSIZE;cinn;memset(a,0,sizeof(a);for(i=1;i x;ax+;i=0;sum=0;while(sum( n/2+1)i+;sum+=ai;coutie ndl;return 0;輸

4、入:vip會(huì)員免費(fèi)11步步模擬，注意輸出的是 sum超出循環(huán)條件時(shí)的i值（中位數(shù)），而不是 sum，也不是ax1234561a1232120(11/2+1)二6EwuirpO+all二11=2suiri=l+a2=3i 二3suiTF3+a3=6折山3輸出：3NOIP2011-2 .#in elude using n ames pace std;int n;void f2(i nt x,i nt y);void f1(i nt x,int y)if(x n)f2(y,x+y);void f2(i nt x,i nt y) coutxn;f1(0,1)； return 0;輸入：30此為簡(jiǎn)單的遞

5、歸題，依次輸出 f2(x,y)中的x值，注意邊界條件時(shí)f1(x,y)的x=30fl Ql)|(X30打?。? fl 2) 1C30 任2(Z 3)I打印雲(yún)2in(3 5)330f2E 8) 俯;5830 fl (21, 3q)21 302(34亠 55)打印.34fl (5589)5530答案=1 2 5 13 34咦！這不是隔一個(gè)輸出一個(gè)的Fib on acci嗎?輸出：1 2 5 13 34NOIP2011-3 .#in elude using n ames pace std;con st int V=100;int n,m,a ns,eVV;bool visitedM;void dfs(

6、i nt x,i ntle n)int i;visitedx= true;if(le nans)an s=le n;for(i=1;inm;for(i=1;i=n ;i+)for(j=1;j=m;j+)eij=-1;for(i=1;i abc;eab=c;eba=c;for(i=1;i=n ;i+)visitedi=false;an s=0;for(i=1;i=n ;i+)dfs(i,0);couta nsans，則ans=len ,可以說(shuō)明這是個(gè)在圖中用DFS找最長(zhǎng)的路徑的程序。DFS以任意點(diǎn)作為起點(diǎn)，找一條路徑，本次走過(guò)的點(diǎn)不走，找到?jīng)]路走為止。由于就 就走3條邊，看看最長(zhǎng)的那 3條，結(jié)果

7、如下圖:輸出：150NOIP2011-4 .#in elude #in elude #in elude using n ames pace std;const int SIZE=10000;const int LENGTH=10;int n,m,aSIZELENGTH;int h(i nt u,i nt v)int an s,i;an s=0;for(i=1;in;memset(a,0,sizeof(a);m=1;while(1)i=1;while( (i n)break;m+;ami=1;for(j=i+1;j=n ;j+)amj=am-1j;vip會(huì)員免費(fèi)sum=O;for(i=1;i=m

8、;i+) for(j=1;j=m;j+) sum+=h(i,j);coutsume ndl;return 0;輸入：7根據(jù)while(1)的程序功能模擬幾行看看，觀察m*n的0-1 矩陣，此矩陣其實(shí)就是所有7位的二進(jìn)制數(shù)(順序左右顛倒)，m=2An 。再根據(jù)h(u,v)的程序功能判斷出本程序的目的。nmI23 456710000(J0)2100000030100000t1100000500 1:0000e1010G0070110GQ011100009000100O12K111111I每一列中有 2n-1 個(gè)1和0,在一列里每個(gè)1都有2人(n-1)個(gè)0與它不同，同樣每個(gè)0,n列的結(jié)果為也有2人(

9、n-1)個(gè)1與它不同，即每列的結(jié)果為2人(2n-2)*2=2A(2n-1)n*2A(2 n-1)，所以本題的結(jié)果為2人13*7。輸出：57344NOIP2012-1.#in elude using n ames pace std;int n ,i,te mp, sum,a100;int mai n()cinn;for (i=1;i=n ;i+)for (i=1;iai+1)temp=ai;ai= ai+1;ai+1=te mp;for (i=n ;i=2;i-)if(aiai-1)temp=ai;ai=ai-1;ai-1=te mp;sum=0;for (i=2;i=n-1;i+) sum +

10、=ai;coutsum/(n -2)e ndl;return 0;輸入:40 70 50 70 20 40 10 30兩輪冒泡，掐頭去尾，求均值。數(shù)據(jù)量不大，就直接模擬吧，速度也挺快的。123456；78a4070507020401030i二 ii二24050707020401030i=3405070207040lOi30i 二54050702040701030i=5405070204010703011=74050702040iO307012345678a405070204010!30l70i-81=7i=5405070201040,30170i二 54050701020403070i二 44

11、050107020403070i=34010507020403070i二2110405070204030701234567SalOi40507020403070suirF40+50+70+20+40+30=250sum/(n-2)二250/(8-2)二41輸出：41NOIP2012-2.#in elude using n ames pace std;int n ,i,a ns;int gcd(i nta,i ntb) if(a%b=0) return b;else return gcd(b,a%b);int mai n() cinn; an s=0;for (i=1;i=n ;i+) if(g

12、cd (n ,i)= i) ans+;couta nse ndl;return 0;輸入：120gcd就是求最大公約數(shù)，如果gcd(n,i)= i 則計(jì)數(shù)，即求120的因子數(shù)。輸出：16NOIP2012-3.#in elude using n ames pace std;con st int SIZE=20;int dataSIZE;int n ,i,h,a ns;void merge() datah-1=datah-1+datah;h-;ans+;int mai n() cinn;h= 1;datah=1;an s=0;for (i=2;i1 &datah=datah-1)merge();c

13、outa nse ndl;return 0;輸入：8語(yǔ)句中函數(shù)調(diào)用細(xì)心點(diǎn)即可。h-1 ans-Oi-2h-1ans-11=3h=2ans=l1=4h=lans=3i=5h=2ans=3i=6h=2ans=4：1=7h-3ans=41=8h=lans=7繼續(xù)模擬,whiledata1data2data21data4data41data42data421data8123輸出：7 輸入：2012對(duì)前面的模擬進(jìn)行觀察，得出如下規(guī)律后計(jì)算:i=2012=512+256+128+64+16+8+4即 data1=512data2=256 data3=128 data4=64 data5=16 data6=

14、8 data7=4 an s=512-1+256-1 + 128-1+64-1 + 16-1+8-1+4-1=2004輸出：2004NOIP2012-4.#in elude #in elude using n ames pace std;in t lefts20,rights20,father20;stri ng s1,s2,s3;int n,ans;void eale(i nt x,i nt dep) an s=a ns+de p*(s1 x -A+1);if(lefts x=0)eale(lefts x ,de p+1);if(rights x =0)calc(rightsx,de p+1

15、); /遞歸函數(shù)，返回ans，累計(jì)結(jié)點(diǎn)深度*結(jié)點(diǎn)權(quán)值之和vip會(huì)員免費(fèi)void check(i nt x) if(lefts x=0)check(le1tsx);s3=s3+s1x;if(rights x =0)check(rightsx);void dfs(i nt x,i nt th) if(th=n) s3=;check(0);if(s3=s2) an s=0;calc(0,1);couta nss1; /先序遍歷序列cin s2; /中序遍歷序列n= s1.size();memset(lefts, -1,sizeof(lefts);memset(nghts,-1,sizeof(nght

16、s);memset(father,-1,sizeof(father);dfs(0,1);輸入:ABCDEFBCAEDF這是二叉樹(shù)的遍歷題，先根據(jù)兩個(gè)輸入的遍歷序列確定二叉樹(shù)。再根據(jù)遞歸函數(shù)計(jì)算六個(gè)結(jié)點(diǎn)深度*權(quán)值之和： an s=1*1+2*2+3*3+4*2+5*3+6*3輸出：55NOIP2013-1.#in clude #in clude int main() stri ng Str;using n ames pacestd;cin str;int n = str.size();boolisP lali ndrome = true;for (int i =0; in /2;i+)if(st

17、ri !=str n-i-1)isP lali ndrome =false;if(is Plali ndrome)coutYes en dl;elsecoutNo en dl;判斷輸入的是不是一個(gè)回文串，字符串左右顛倒，結(jié)果不變。輸入：abceecba01234567sabceecban=8i=0;i3/2=4iOstr O=-str8-0-1-str71=1strl=str8-l-l=str6i=2str 23tr 8-2*1 =str 51=3str 3=str 8-3-str 4isPlalindrome-l輸出：YesNOIP2013-2.#in clude using n ames

18、pace std;int main()int a,b,u,v,i, num;cin abuv;num =0;for ( i= a; I =b;i+)if(i%u) =O)|(i%v)=O) num +;count num e ndl;return 0;輸入：11000 10 151-1000 范圍內(nèi)同時(shí)是10、15的倍數(shù)有多少？注意去重。輸出：133NOIP2013-3.#in elude using n ames pace std;int main() const int SIZE = 100;n, ans;int heightSIZE, nu mSIZE, cinn;for (int i=

19、0;i heighti;nu mi=1;for (int j=0;ji； j+) if(heightj= numi) nu mi=nu mj+1;ans =0;for(i ntI = 1; ia ns) ans =nu mj;cout a nse ndl;return 0;輸入:3 2 5 11 12 7 4 10求該字符串的最長(zhǎng)上升子序列的長(zhǎng)度。輸出：4NOIP2013-4.#in elude #in clude using n ames pacestd;const int SIZE = 100;int n, m, p, aSIZE SIZE, count;void colour (int

20、x,int y)Coun t+;axy = 1;if (x 1)&(ax-1y=0)colour(x - 1, y);if (y 1)&(axy-1=0)colour(x, y- 1);if (x n)&(ax+1y=0)colour(x +1, y);if (y nmp;for(i =1 ; I xy;axy= 1;ans0；for (i =1; i =n; i+)for (j =1; j =m;j+)if(aij0)count0;colour (i , j);if (ans co unt)an sco unt;coun ta nse ndl;return 0;輸入:根據(jù)輸入的x和y值畫(huà)出0

21、-1矩陣,再判斷同一區(qū)域 0最多的個(gè)數(shù)輸出：7NOIP2014-1.#in elude using n ames pace std;int mai n() int a, b, i, tot, c1, c2;cin a b;tot = 0;for (i = a; i = b; i+) c1 = i / 10;c2 = i % 10;if (c1 + c2) % 3= 0)tot+; II一個(gè)數(shù)的各位數(shù)之和是3的倍數(shù)，它就是3的倍數(shù)。cout tot en dl;return 0; /統(tǒng)計(jì)7-31之間有多少數(shù)是3的倍數(shù)輸入:731輸出：8NOIP2014-2.#in clude using n a

22、mes pace std;int fun (i nt n, int minNum, int maxNum) int tot, i;if(n = 0) return1;tot= 0;for(i = minNum; i n m;cout fun(m, 1, n) en dl;return 0;輸入：63遞歸邊界：當(dāng) n=0 時(shí)，fun(n,minNum,maxNum)=1fun( 3,1,6)=(2,2,6)+(2,3,6)+(2,4,6)+(2,5,6)+(2,6,6)+(2,7,6)=20 fun( 2,2,6)=(1,3,6)+(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=

23、10 fun( 2,3,6)=(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=6 fun( 2,4,6)=(1,5,6)+(1,6,6)+(1,7,6)=3 fun (2,5,6)=(1,6,6)+(1,7,6)=1 fun (2,6,6)=(1,7,6)=0 fun (1,3,6)=(0,4,6)+(0,5,6)+(0,6,6)+(0,7,6)=4 fun (1,4,6)=(0,5,6)+(0,6,6)+(0,7,6)=3 fun (1,5,6)=(0,6,6)+(0,7,6)=2fun (1,6,6)=(0,7,6)=1 fun (1,7,6)=0輸出：20NOIP2014

24、-3.#in elude #in elude using n ames pace std;con st int SIZE = 100;int mai n() string dictSIZE;int ran kSIZE;int in dSIZE;int i, j, n, tmp;cin n;for (i = 1; i = n; i+) ran ki = i;in di = i;for (i= 1; i n; i+)for (j = 1; j dicti ndj + 1) tmp = in dj;in dj = indj +1;indj + 1 = tmp; /冒泡排序 for (i = 1; i

25、 = n; i+)ran ki ndi = i; /輸出diet里字符排序后應(yīng)該在的位置for (i = 1; i = n; i+)cout ra nki ;cout en dl;return 0;輸入：aaaababbbaaaaaacccaadiet rankaaa2aba bbb2aaa3aaaccc5ind冒滋際拼行i二1冋j二rd+基本就可猜出ind鞭化情況 ind71覷兩加血mtuMiirank輸出：2 5 6 3 4 7 1NOIP2014-4.#in elude using n ames pace std;con st int SIZE = 100;int aliveSIZE;i

26、nt n;int n ext(i nt num) do nu m+;if (num n)vip會(huì)員免費(fèi)num = 1; while (alive num = 0);return num;int mai n() int m, i, j, num;cin n m;for (i = 1; i = n; i+) alivei = 1;num = 1;for (i = 1; i = n; i+) for (j = 1; j m; j+) num = n ext (nu m);cout numH H.alive num = 0;if (i n) num = n ext (nu m);cout en dl;

27、return 0;vip會(huì)員免費(fèi)輸入：11 3這就是約瑟夫環(huán)問(wèn)題，11個(gè)人圍一圈，從1開(kāi)始報(bào)數(shù)，報(bào)到 3的出局，再?gòu)某鼍值南乱粋€(gè)人開(kāi)始報(bào)1，直到全部出局，依次輸出出局人的編號(hào)。輸出：3 6 9 1 5 10 4 11 8 2 7NOIP2015-1. / 同普及組閱讀題 NOIP2015-2#in elude using n ames pace std;struct point int X； int y;int mai n() struct EX int a;int b;point c;e;e.a= 1;e.b= 2;e.c.x= e.a + e.b;e.c.y= e.a * e.b;cout

28、 e.c.x , e.c.y en dl;return 0;輸出：3,2 /注意輸出有逗號(hào)NOIP2015-2. / 同普及組閱讀題 NOIP2015-4#in clude using n ames pace std;void fun( char *a, char *b) a = b;(*a)+;int mai n() char c1, c2, * p1, * p2;c1 = A;c2 = a;p1 = & c1;p2 = &c2;fun(p 1, p2);cout c1 c2 en dl;return 0; /指針題，注意*a、&a、a的區(qū)別。輸出：AbNOIP2015-3.#in elud

29、e #in elude using n ames pace std;int mai n() in t le n, maxle n;stri ng s, ss;maxle n = 0;do cin ss;len = ss.len gth();if (ss0 = #) break;if (le n maxle n) s = ss;maxle n = len;輸出長(zhǎng)度最長(zhǎng)的字符串 s while (true);cout s en dl;return 0;輸入：am citize n ofChi na輸出:citizenNOIP2015-4.#in clude using n ames pace st

30、d;int fun (i nt n, int fromPos, int toPos) int t, tot;if (n = 0) return 0;for (t = 1; t n;cout fun(n, 1,3) en dl;return 0;輸入：5 遞歸邊界：當(dāng) n=0 時(shí)，fun(n,fromPos,toPos)=0fun (5,1,3)=(4,*,*)+1+(4,*,*)=31 fun (4,*,*)=(3,*,*)+1+(3,*,*)=15 fun (3,*,*)=(2,*,*)+1+(2,*,*)=7 fun (2,*,*)=(1,*,*)+1+(1,*,*)=3fun (1,*,

31、*)=(0,*,*)+1+(0,*,*)=1輸出：31NOIP2016-1.#in elude using n ames pace std;int mai n() int a6 = 1,2, 3, 4, 5, 6;int pi = 0;int pj = 5;in tt , i;while (pi pj) t = ap i;api = apj;apj = t;pi+;pj-;for (i = 0; i 6; i+)cout ai H H.cout en dl;return 0;/倒序輸出，注意逗號(hào)輸出：6,5,432,1,NOIP2016-2.#in elude using n ames pac

32、e std;int mai n() char a100100, b100100;string c100;stri ng tmp;intn, i = 0, j = 0, k = 0, total_le n 100, le ngth1003;cin n;getl in e(ci n, tmp);for (i = 0; i n; i+) 記錄ci的長(zhǎng)度getl in e(ci n, ci);total_le ni = ci.size(); / for (i = 0; i cijaiO-aik(k=j)中。k = k + 1;j+； len gthi1 = k - 1;/記錄:前的字符的個(gè)數(shù) aik

33、= 0; / 記錄:所在的位置k = 0;for (j = j + 1; j total_le n i; j+) bik = cij;為:后輸入的字符，并將其存入bik/由于j是掃描到:后的值再+1，所以此時(shí)的cij k = k + 1;len gthi2 = k - 1;/記錄:后的字符的個(gè)數(shù)bik = 0; /記錄終點(diǎn)位置k = 0;vip會(huì)員免費(fèi)for (i = 0; i =le ngthi2) cout NO,; / 如果:前的字符比:后的字符個(gè)數(shù)多,輸出NO,else k = 0;for (j = 0; j len gthi1) break;/如果k的值比:前的字符長(zhǎng)度大，即已經(jīng)找完

34、了:前的所有字符，那么退出循環(huán) if (j = len gthi2) cout NO,;:前的字符是否/如果j的值和:后的字符串長(zhǎng)度相等，即在掃描到最后一個(gè)點(diǎn)時(shí)，無(wú)論被全部找完，都輸出NO,else cout YES,;II如果在找完字符串之前已經(jīng)找到了:前的字符，那么輸出YES,vip會(huì)員免費(fèi)cout en dl;return 0;輸入:AB:ACDEbFBkBDAR:ACDBrTSARS:Severe Atyp ical Resp iratory Syn drome對(duì)！就是判斷冒號(hào)前的字母是否在冒號(hào)后的字符串中出現(xiàn)，大小寫(xiě)要區(qū)分，注意有逗號(hào)。輸出：YES,NO,YES,（注：輸入各行前后均無(wú)空格）NOIP2016-3.#in clude using n ames pace std;int Ip s(stri ng seq, int i, i nt j) in t le n1, le n2;if (i = j) return 1;/當(dāng)i=j時(shí)，則此時(shí)掃描到的項(xiàng)是一定可以放入該回文子序列中，長(zhǎng)度貢獻(xiàn)為 return 0;if (i j