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)你閱讀程序時有強烈的代入感，像演員一樣，真正

3、進(jìn)入到編劇的精神世界，面部表情也隨之日漸豐富起來。祝賀你！你通關(guān)了！總之，看得多，碼得多，拼得多，你就考得多NOIP2011-1#include #include using namespace std;const int SIZE = 100;int main()int n,i,sum,x,aSIZE;cinn;memset(a,0,sizeof(a);for(i=1;ix;ax+;i=0;sum=0;while(sum(n/2+1)i+;sum+=ai;coutiendl;return 0;輸入：114 5 6 6 4 3 3 2 3 2 1一步步模擬，注意輸出的是sum超出循環(huán)條件時的i

4、值（中位數(shù)），而不是sum，也不是ax輸出：3NOIP2011-2#include using namespace std;int n;void f2(int x,int y);void f1(int x,int y)if(xn)f2(y,x+y);void f2(int x,int y)coutxn;f1(0,1);return 0;輸入：30此為簡單的遞歸題，依次輸出f2(x,y)中的x值，注意邊界條件時f1(x,y)的x=30咦！這不是隔一個輸出一個的Fibonacci嗎？輸出：1 2 5 13 34NOIP2011-3#include using namespace std;const

5、 int V=100;int n,m,ans,eVV;bool visitedV;void dfs(int x,intlen)int i;visitedx= true;if(lenans)ans=len;for(i=1;inm;for(i=1;i=n;i+)for(j=1;j=m;j+)eij=-1;for(i=1;iabc;eab=c;eba=c;for(i=1;i=n;i+)visitedi=false;ans=0;for(i=1;i=n;i+)dfs(i,0);coutansans，則ans=len，可以說明這是個在圖中用DFS找最長的路徑的程序。DFS以任意點作為起點，找一條路徑，本次

6、走過的點不走，找到?jīng)]路走為止。由于就4個點，最多就走3條邊，看看最長的那3條，結(jié)果如下圖：輸出：150NOIP2011-4#include #include #include using namespace std;const int SIZE=10000;const int LENGTH=10;int n,m,aSIZELENGTH;int h(int u,int v)int ans,i;ans=0;for(i=1;in;memset(a,0,sizeof(a);m=1;while(1)i=1;while( (in)break;m+;ami=1;for(j=i+1;j=n;j+)amj=am

7、-1j;sum=0;for(i=1;i=m;i+)for(j=1;j=m;j+)sum+=h(i,j);coutsumendl;return 0;輸入：7根據(jù)while(1)的程序功能模擬幾行看看，觀察m*n的0-1矩陣，此矩陣其實就是所有7位的二進(jìn)制數(shù)（順序左右顛倒），m=2n。再根據(jù)h(u,v)的程序功能判斷出本程序的目的。每一列中有2n-1個1和0，在一列里每個1都有2(n-1)個0與它不同，同樣每個0也有2(n-1)個1與它不同，即每列的結(jié)果為2(2n-2)*2=2(2n-1)，n列的結(jié)果為n*2(2n-1)，所以本題的結(jié)果為213*7。輸出：57344NOIP2012-1.#incl

8、ude usingnamespacestd;int n,i,temp,sum,a100;int main()cinn;for (i=1;iai;for (i=1;iai+1)temp=ai;ai= ai+1;ai+1=temp;for (i=n;i=2;i-)if(aiai-1)temp=ai;ai=ai-1;ai-1=temp;sum=0;for (i=2;i=n-1;i+)sum +=ai;coutsum/(n -2)endl;return 0;輸入：840 7050 7020 401030兩輪冒泡，掐頭去尾，求均值。數(shù)據(jù)量不大，就直接模擬吧，速度也挺快的。輸出：41NOIP2012-2.

9、#include usingnamespacestd;int n,i,ans;int gcd(inta,intb)if(a%b=0)return b;elsereturn gcd(b,a%b);int main()cinn; ans=0;for (i=1;i=n;i+)if(gcd(n,i)= i)ans+;coutansendl;return 0;輸入：120gcd就是求最大公約數(shù)，如果gcd(n,i)= i則計數(shù)，即求120的因子數(shù)。輸出：16NOIP2012-3.#include usingnamespacestd;constintSIZE=20;int dataSIZE;int n,i

10、,h,ans;void merge()datah-1=datah-1+datah;h-;ans+;int main()cinn;h= 1;datah=1;ans=0;for (i=2;i1&datah=datah-1)merge();coutansendl;return 0;輸入：8繼續(xù)模擬，while語句中函數(shù)調(diào)用細(xì)心點即可。輸出：7輸入：2012對前面的模擬進(jìn)行觀察，得出如下規(guī)律后計算：i=2012=512+256+128+64+16+8+4即data1=512data2=256 data3=128 data4=64 data5=16 data6=8 data7=4ans=512-1+25

11、6-1+128-1+64-1+16-1+8-1+4-1=2004輸出：2004NOIP2012-4.#include #include usingnamespacestd;int lefts20,rights20,father20;string s1,s2,s3;int n,ans;void calc(intx,intdep)ans=ans+dep*(s1x -A+1);if(leftsx=0)calc(leftsx,dep+1);if(rightsx=0)calc(rightsx,dep+1); /遞歸函數(shù)，返回ans，累計結(jié)點深度*結(jié)點權(quán)值之和void check(int x)if(lef

12、tsx=0)check(leftsx);s3=s3+s1x;if(rightsx=0)check(rightsx);void dfs(int x,int th)if(th=n)s3=;check(0);if(s3=s2)ans=0;calc(0,1);coutans=0)dfs(fatherx,th);int main()cins1; /先序遍歷序列cins2; /中序遍歷序列n= s1.size();memset(lefts, -1,sizeof(lefts);memset(rights,-1,sizeof(rights);memset(father,-1,sizeof(father);df

13、s(0,1);輸入：ABCDEFBCAEDF這是二叉樹的遍歷題，先根據(jù)兩個輸入的遍歷序列確定二叉樹。再根據(jù)遞歸函數(shù)計算六個結(jié)點深度*權(quán)值之和:ans=1*1+2*2+3*3+4*2+5*3+6*3輸出：55NOIP2013-1.#include #include using namespace std;int main( )string Str;cinstr;int n = str.size();bool isPlalindrome = true;for (int i =0; in/2;i+)if(stri !=strn-i-1) isPlalindrome =false;if(isPlali

14、ndrome)cout ”Yes” endl;elsecout ”No” endl;輸入：abceecba判斷輸入的是不是一個回文串，字符串左右顛倒，結(jié)果不變。輸出：YesNOIP2013-2.#include using namespace std;int main( )int a,b,u,v,i, num;cinabuv;num =0;for ( i= a; I =b; i+)if(i%u) =0)|(i%v)=0)num +;count numendl;return 0;輸入：1 1000 10 151-1000范圍內(nèi)同時是10、15的倍數(shù)有多少？注意去重。輸出：133NOIP2013-

15、3.#include using namespace std;int main( )const intSIZE = 100;int heightSIZE,numSIZE, n, ans;cinn;for (inti=0; iheighti;numi=1;for (intj=0; ji; j+) if(heightj= numi)numi=numj+1;ans =0;for(int I = 1;ians) ans =numj;cout ansendl;return 0;輸入：83 2 5 11 12 7 4 10求該字符串的最長上升子序列的長度。輸出：4NOIP2013-4.#include #

16、include using namespace std;const int SIZE = 100;int n, m,p, aSIZE SIZE, count;void colour (intx, int y)Count+;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;ans = 0;for (i =1; i =n; i+)for (j =1;

17、 j =m;j+)if(aij = 0)count = 0;colour (i , j);if (ans count)anscount;countansendl;return 0;輸入：6 5 91 42 32 43 24 14 34 55 46 4根據(jù)輸入的x和y值畫出0-1矩陣，再判斷同一區(qū)域0最多的個數(shù)輸出：7NOIP2014-1.#include using namespace std;int main()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 (

18、c1 + c2) % 3= 0)tot+;/一個數(shù)的各位數(shù)之和是3的倍數(shù)，它就是3的倍數(shù)。cout tot endl;return 0;/統(tǒng)計7-31之間有多少數(shù)是3的倍數(shù)輸入: 7 31輸出: 8NOIP2014-2.#include using namespace std;int fun(int 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) endl;return 0;輸入: 6 3遞歸邊界：當(dāng)n=0時，fun(n,minNum,max

19、Num)=1fun(3,1,6)=(2,2,6)+(2,3,6)+(2,4,6)+(2,5,6)+(2,6,6)+(2,7,6)=20fun(2,2,6)=(1,3,6)+(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=10fun(2,3,6)=(1,4,6)+(1,5,6)+(1,6,6)+(1,7,6)=6fun(2,4,6)=(1,5,6)+(1,6,6)+(1,7,6)=3fun(2,5,6)=(1,6,6)+(1,7,6)=1fun(2,6,6)=(1,7,6)=0fun(1,3,6)=(0,4,6)+(0,5,6)+(0,6,6)+(0,7,6)=4fun(1,4,

20、6)=(0,5,6)+(0,6,6)+(0,7,6)=3fun(1,5,6)=(0,6,6)+(0,7,6)=2fun(1,6,6)=(0,7,6)=1fun(1,7,6)=0輸出: 20NOIP2014-3.#include #include using namespace std;const int SIZE = 100;int main()string dictSIZE;int rankSIZE;int indSIZE;int i, j, n, tmp;cin n;for (i = 1; i dicti;for (i= 1; i n; i+)for (j = 1; j dictindj

21、+ 1)tmp = indj;indj = indj +1;indj + 1 = tmp; /冒泡排序for (i = 1; i = n; i+)rankindi = i; /輸出dict里字符排序后應(yīng)該在的位置for (i = 1; i = n; i+)cout ranki ;cout endl;return 0;輸入:7aaaababbbaaaaaacccaa輸出: 2 5 6 3 4 7 1NOIP2014-4.#include using namespace std;const int SIZE = 100;int aliveSIZE;int n;int next(int num)do

22、 num+;if (num n)num = 1; while (alivenum = 0);return num;int main()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 = next(num);cout num ;alivenum = 0;if (i n)num = next(num);cout endl;return 0;輸入: 11 3這就是約瑟夫環(huán)問題，11個人圍一圈，從1開始報數(shù)，報到3的出局，再從

23、出局的下一個人開始報1，直到全部出局，依次輸出出局人的編號。輸出: 3 6 9 1 5 10 4 11 8 2 7NOIP2015-1. /同普及組閱讀題NOIP2015-2#include using namespace std;struct point int x;int y;int main()struct EXint 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 e.c.x , e.c.y endl;return 0;輸出: 3,2/注意輸出有逗號NOIP2015-2. /同普及組閱讀題NO

24、IP2015-4#include using namespace std;void fun(char *a, char *b) a = b;(*a)+;int main()char c1, c2, *p1, *p2;c1 = A;c2 = a;p1 = &c1;p2 = &c2;fun(p1, p2);cout c1 c2 endl;return 0; /指針題，注意*a、&a、a的區(qū)別。輸出: AbNOIP2015-3.#include #include using namespace std;int main()int len, maxlen;string s, ss;maxlen = 0

25、;do cin ss;len = ss.length();if (ss0 = #)break;if (len maxlen) s = ss;maxlen = len;/輸出長度最長的字符串s while (true);cout s endl;return 0;輸入:IamacitizenofChina#輸出: citizenNOIP2015-4.#include using namespace std;int fun(int n, int fromPos, int toPos)int t, tot;if (n = 0)return 0;for (t = 1; t n;cout fun(n, 1

26、, 3) endl;return 0;輸入: 5遞歸邊界：當(dāng)n=0時，fun(n,fromPos,toPos)=0fun(5,1,3)=(4,*,*)+1+(4,*,*)=31fun(4,*,*)=(3,*,*)+1+(3,*,*)=15fun(3,*,*)=(2,*,*)+1+(2,*,*)=7fun(2,*,*)=(1,*,*)+1+(1,*,*)=3fun(1,*,*)=(0,*,*)+1+(0,*,*)=1輸出: 31NOIP2016-1.#include using namespace std;int main()int a6 = 1, 2, 3, 4, 5, 6;int pi =

27、0;int pj = 5;intt , i;while (pi pj) t = api;api = apj;apj = t;pi+;pj-;for (i = 0; i 6; i+)cout ai ,;cout endl;return 0;/倒序輸出，注意逗號輸出：6,5,4,3,2,1,NOIP2016-2.#include using namespace std;int main()char a100100, b100100;string c100;string tmp;intn, i = 0, j = 0, k = 0, total_len100, length1003;cin n;get

28、line(cin, tmp);for (i = 0; i n; i+) getline(cin, ci);total_leni = ci.size(); /記錄ci的長度for (i = 0; i cij中的字符存入ai0-aik(k=j)中。k = k + 1;j+;lengthi1 = k - 1;/記錄:前的字符的個數(shù)aik = 0; /記錄:所在的位置k = 0;for (j = j + 1; j total_leni; j+) bik = cij;/由于j是掃描到:后的值再+1，所以此時的cij為:后輸入的字符，并將其存入bik中k = k + 1;lengthi2 = k - 1;

29、/記錄:后的字符的個數(shù)bik = 0; /記錄終點位置k = 0;for (i = 0; i =lengthi2)cout NO,; /如果:前的字符比:后的字符個數(shù)多,輸出NO,else k = 0;for (j = 0; j lengthi1)break;/如果k的值比:前的字符長度大，即已經(jīng)找完了:前的所有字符，那么退出循環(huán)if (j = lengthi2)cout NO,;/如果j的值和:后的字符串長度相等，即在掃描到最后一個點時，無論:前的字符是否被全部找完，都輸出NO,elsecout YES,;/如果在找完字符串之前已經(jīng)找到了:前的字符，那么輸出YES,cout endl;ret

30、urn 0;輸入：3AB:ACDEbFBkBDAR:ACDBrTSARS:Severe Atypical Respiratory Syndrome對！就是判斷冒號前的字母是否在冒號后的字符串中出現(xiàn)，大小寫要區(qū)分，注意有逗號。輸出：YES,NO,YES,（注：輸入各行前后均無空格）NOIP2016-3.#includeusing namespace std;int lps(string seq, int i, int j)int len1, len2;if (i = j)return 1;/當(dāng)i=j時，則此時掃描到的項是一定可以放入該回文子序列中，長度貢獻(xiàn)為1if (i j)return 0;/當(dāng)ij時，即掃描到的左邊的數(shù)在右邊已經(jīng)掃描過了，所以該項及往后的所有項都是已經(jīng)掃描過的項，長度貢獻(xiàn)為0if(seqi = seqj) /當(dāng)掃描到相同的字符時return lps(seq, i + 1, j - 1) + 2;/此時這兩個相同字符必定可以