(word完整版)NOIP提高组初赛历年试题及答案阅读题篇推荐文档

1、NOIP 提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4 题，每题 8 分，共计 32 分）阅读程序的最好方法并非是依次从头到尾。 程序不像迷语， 我们无法从末尾几页找到答案，也不像一本引人入胜的书籍， 只需直接翻到褶皱最多的那几页， 我们就能找到最精彩的片断。 因此我们在阅读程序时， 最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉， 理解每一段代码在程序中所起的作用， 进而形成一个虚拟的程序结构，并以此为基础来进行阅读。1、分层读：高层入手，逐层深入，正确理解程序。2、写注解：固化、总结、提炼已有的理解成果。3、先模拟：根据代码顺序跟踪变量，模拟运算。4、找规律：先模拟几次循环

2、后，找出背后的规律。5、看功能：从代码结构和运算结果判断程序功能。6、猜算法：有时不知道算法，通过结构和函数猜一猜。7、换方法：了解程序本质后，换一个熟悉的方法试试。对大多数人来说， 写程序是令人开心的一件事情， 读别人的程序却很痛苦， 很恐惧，宁愿自己重写一遍。其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。如果说写程序是把自己的思维转化为代码， 读程序就是把代码转化为你理解的别人的思维。当你阅读程

3、序时有强烈的代入感， 像演员一样， 真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多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;输入：1145664332321一步步模拟，注意输出的是s

4、um超出循环条件时的i 值（中位数），而不是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吗？输出： 1251334NOIP2011-3 #include using na

5、mespace std;const 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找最长的路径的程序。DF

6、S以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就4 个点，最多就走3条边，看看最长的那3 条，结果如下图：输出： 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;f

7、or(j=i+1;j=n;j+)amj=am-1j;sum=0;for(i=1;i=m;i+)for(j=1;j=m;j+)sum+=h(i,j);coutsumendl;return 0;输入： 7根据 while(1)的程序功能模拟几行看看，观察 m*n的 0-1矩阵，此矩阵其实就是所有7位的二进制数 （顺序左右颠倒），m=2n。再根据 h(u,v) 的程序功能判断出本程序的目的。每一列中有2n-1个 1 和 0 ，在一列里每个 1都有 2(n-1)个 0与它不同， 同样每个 0也有 2(n-1)个 1与它不同，即每列的结果为2(2n-2)*2=2(2n-1)， n 列的结果为n*2(2n

8、-1)，所以本题的结果为 213*7 。输出： 57344NOIP2012-1.#include using namespace std;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 70 50 70 20 40 10 3

9、0两轮冒泡，掐头去尾，求均值。数据量不大，就直接模拟吧，速度也挺快的。输出： 41NOIP2012-2.#include using namespace std;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 就是求最大公约数，如果gcd(n,i)= i则计数，即求120的因子数。输出： 16NOIP2012-3.#inclu

10、de using namespace std;const int SIZE=20;int dataSIZE;int n,i,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继续模拟， while语句中函数调用细心点即可。输出： 7输入： 2012对前面的模拟进行观察，得出如下规律后计算：i=2012=512+256+128+64+16+8+4即 data1=51

11、2data2=256 data3=128 data4=64 data5=16 data6=8data7=4ans=512-1+256-1+128-1+64-1+16-1+8-1+4-1=2004输出： 2004NOIP2012-4.#include #include using namespace std;int lefts20,rights20,father20;string s1,s2,s3;int n,ans;void calc(int x,int dep)ans=ans+dep*(s1x -A+1);if(leftsx=0)calc(leftsx,dep+1);if(rightsx=0

12、)calc(rightsx,dep+1); / 递归函数，返回 ans ，累计结点深度 * 结点权值之和void check(int x)if(leftsx=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,sizeo

13、f(lefts);memset(rights,-1,sizeof(rights);memset(father,-1,sizeof(father);dfs(0,1);输入：ABCDEFBCAEDF这是二叉树的遍历题，先根据两个输入的遍历序列确定二叉树。再根据递归函数计算六个结点深度* 权值之和 :ans=1*1+2*2+3*3+4*2+5*3+6*3输出： 55NOIP2013-1.#include #include using namespacestd;int main( )string Str;cinstr;intn = str.size( );boolisPlalindrome = tru

14、e;for (inti =0; in/2;i+)if(stri !=strn-i-1)isPlalindrome =false;if(isPlalindrome)cout” Yes” endl;elsecout” No ” endl;输入： abceecba判断输入的是不是一个回文串，字符串左右颠倒，结果不变。输出： YesNOIP2013-2.#include using namespace std;int main( )inta,b,u,v,i, num;cinabuv;num=0;for( i= a; I =b;i+)if(i%u) =0)|(i%v)=0)num +;count num

15、endl;return0;输入： 11000 10 151-1000范围内同时是10 、 15的倍数有多少？注意去重。输出： 133NOIP2013-3.#include using namespace std;int main( )constint SIZE = 100;intheightSIZE, numSIZE,n, ans;cinn;for(int i=0;iheighti;numi=1;for(int j=0;ji;j+) if(heightj= numi)numi=numj+1;ans =0;for(intI = 1; ians) ans =numj;cout ansendl;re

16、turn 0;输入：832511127410求该字符串的最长上升子序列的长度。输出： 4NOIP2013-4.#include #include using namespacestd;constintSIZE = 100;intn, m, p,aSIZE SIZE, count;voidcolour(int x,inty)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 =

17、1 ; I xy;axy= 1;ans=0;for(i =1; i =n; i+)for(j =1; j =m;j+)if(aij=0)count= 0;colour(i , j);if(ans count)anscount;countansendl;return0;输入：6 5 91 42 32 43 24 14 34 55 46 4根据输入的x 和 y 值画出 0-1矩阵，再判断同一区域0 最多的个数输出： 7NOIP2014-1.#include using namespace std;int main()int a, b, i, tot, c1, c2;cin a b;tot = 0;

18、for (i = a; i = b; i+)c1 = i / 10;c2 = i % 10;if (c1 + c2) % 3= 0)tot+; /一个数的各位数之和是3 的倍数，它就是3 的倍数。cout tot endl;return 0; / 统计 7-31 之间有多少数是 3 的倍数输入: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(

19、m, 1, n) endl;return 0;输入:63递归边界：当n=0时， 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)=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,

20、6)=0fun(1,3,6)=(0,4,6)+(0,5,6)+(0,6,6)+(0,7,6)=4fun(1,4,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

21、= 1; i dicti;for(i= 1; i n; i+)for (j = 1; j dictindj + 1)tmp = indj;indj = indj +1;indj + 1 = tmp; / 冒泡排序for (i = 1; i = n; i+)rankindi = i; /输出 dict里字符排序后应该在的位置for (i = 1; i = n; i+)cout ranki ;cout endl;return 0;输入 :7aaaababbbaaaaaacccaa输出:2563471NOIP2014-4.#include using namespace std;const int

22、SIZE = 100;int aliveSIZE;int n;int next(int num)do 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

23、;return 0;输入:113这就是约瑟夫环问题，11个人围一圈，从1 开始报数，报到3 的出局，再从出局的下一个人开始报1 ，直到全部出局，依次输出出局人的编号。输出:3691510411827NOIP2015-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;ret

24、urn 0;输出 : 3,2 /注意输出有逗号NOIP2015-2. / 同普及组阅读题NOIP2015-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 的区别。输出 : AbNOIP2015-3.#include #include using namespace

25、std;int main()int len, maxlen;string s, ss;maxlen = 0;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, 3) endl;return 0;输入:5递归边界：当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.#includ