noip提高组初赛历年试题及答案阅读题篇.docx

NOIP提高组初赛历年试题及答案阅读题篇阅读程序写结果（共4?题，每题8?分，共计32?分）阅读程序的最好方法并非是依次从头到尾。程序不像迷语，我们无法从末尾几页找到答案，也不像一本引人入胜的书籍，只需直接翻到褶皱最多的那几页，我们就能找到最精彩的片断。因此我们在阅读程序时，最好逐一考察研究每一段代码，搞清楚每一段代码的来龙去脉，理解每一段代码在程序中所起的作用，进而形成一个虚拟的程序结构，并以此为基础来进行阅读。1、分层读：高层入手，逐层深入，正确理解程序。2、写注解：固化、总结、提炼已有的理解成果。3、先模拟：根据代码顺序跟踪变量，模拟运算。4、找规律：先模拟几次循环后，找出背后的规律。5、看功能：从代码结构和运算结果判断程序功能。6、猜算法：有时不知道算法，通过结构和函数猜一猜。7、换方法：了解程序本质后，换一个熟悉的方法试试。对大多数人来说，写程序是令人开心的一件事情，读别人的程序却很痛苦，很恐惧，宁愿自己重写一遍。其实读到好的程序，就像读一篇美文，令人心旷神怡，豁然开朗，因为这背后是一个人的思维，甚至整个人生。阅读别人的程序不仅可以巩固自己的知识，启发自己的思维，提升自己的修养，让你收获满满，其实，这也是在学习、在竞赛、在工作中的最重要、最常用的基本功。如果说写程序是把自己的思维转化为代码，读程序就是把代码转化为你理解的别人的思维。当你阅读程序时有强烈的代入感，像演员一样，真正进入到编剧的精神世界，面部表情也随之日渐丰富起来。祝贺你！你通关了！总之，看得多，码得多，拼得多，你就考得多……NOIP2011-1．#include iostream#include cstringusing namespace std;const int SIZE = 100;int main(){int n,i,sum,x,a[SIZE];cinn;memset(a,0,sizeof(a));for(i=1;i=n;i++){cinx;a[x]++;}i=0;sum=0;while(sum(n/2+1)){i++;sum+=a[i];}coutiendl;return 0;}输入：114 5 6 6 4 3 3 2 3 2 1一步步模拟，注意输出的是sum超出循环条件时的i值（中位数），而不是sum，也不是a[x]输出：3NOIP2011-2．#include iostreamusing 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){coutx ;f1(y,x+y);}int main(){cinn;f1(0,1);return 0;}输入：30此为简单的递归题，依次输出f2(x,y)中的x值，注意边界条件时f1(x,y)的x=30咦！这不是隔一个输出一个的Fibonacci吗？输出：1 2 5 13 34NOIP2011-3．#include iostreamusing namespace std;const int V=100;int n,m,ans,e[V][V];bool visited[V];void dfs(int x,intlen){int i;visited[x]= true;if(lenans)ans=len;for(i=1;i=n;i++)if( (!visited[i]) (e[x][i]!=-1) )dfs(i,len+e[x][i]);visited[x]=false;}int main(){int i,j,a,b,c;cinnm;for(i=1;i=n;i++)for(j=1;j=m;j++)e[i][j]=-1;for(i=1;i=m;i++){cinabc;e[a][b]=c;e[b][a]=c;}for(i=1;i=n;i++)visited[i]=false;ans=0;for(i=1;i=n;i++)dfs(i,0);coutansendl;return 0;}输入：4 61 2 102 3 203 4 304 1 401 3 502 4 60一看就知这是深搜算法（DFS），输入是个四个顶点的无向图（邻接矩阵如下）：如lenans，则ans=len，可以说明这是个在图中用DFS找最长的路径的程序。DFS以任意点作为起点，找一条路径，本次走过的点不走，找到没路走为止。由于就4个点，最多就走3条边，看看最长的那3条，结果如下图：输出：150NOIP2011-4．#include iostream#include cstring#include stringusing namespace std;const int SIZE=10000;const int