历年noip普及组完善程序题总结归纳

1、完善程序题总结归纳By:( 6) yx一、【题目】 (哥德巴赫猜想)哥德巴赫猜想是指，任一大于2的偶数都可写成两个质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。 试编写程序,验证任一大于2且不超过n的偶数都能写成两个质数之和。#in cludeusing n amespace std;int mai n()const int SIZE=1000;int n ,r,pSIZE,i,j,k,a ns;bool tmp;cinn;r=1;p1=2;for(i=3;i=n ;i+) ;for(j=1;j=r;j+)if(i%=0)tmp=false;break;if(tmp)

2、r+;an s=0;for(i=2;i=n/2;i+)tmp=false;for(j=1;j=r;j+)for(k=j;k=r;k+)if(i+i=)tmp=true;break;if(tmp)ans+;couta nse ndl;return 0;若输入n为2010，则输出 时表示验证成功，即大于 2且不超过2010的偶数都满足哥德巴赫猜想。【算法】先for 一遍，找出质数，然后对每一个偶数进行一一匹配(2除外)，效率0(23)【代码】1、tmp=1 ； 2、pj;3、pr=j;4、pj+pk5、1004【年份】2010年二、【题目】 (过河问题)在一个月黑风高的夜晚，有一群人在河的右岸，想

3、通过唯一的 一根独木桥走到河的左岸.在伸手不见五指的黑夜里，过桥时必须借照灯光来照明，不幸的是, 他们只有一盏灯.另外，独木桥上最多能承受两个人同时经过，否则将会坍塌.每个人单独过独木桥都需要一定的时间，不同的人要的时间可能不同.两个人一起过独木桥时，由于只有一 盏灯，所以需要的时间是较慢的那个人单独过桥所花费的时间现在输入 N(2=N1000)和这N个人单独过桥需要的时间，请计算总共最少需要多少时间，他们才能全部到达河左岸例如，有3个人甲、乙、丙，他们单独过桥的时间分别为 1、2、4,则总共最少需要的 时间为7.具体方法是：甲、乙一起过桥到河的左岸 ，甲单独回到河的右岸将灯带回 ，然后甲、

4、丙在一起过桥到河的左岸，总时间为2+1+4=7.#in clude#in cludeusing n amespace std;const int size=100;const int infinity = 10000;const bool left=1;const bool right =0;const bool left_to_right=1;const bool right_to_left=0;int n, hoursize;bool possize;int max(i nt a,i nt b)retur n ab?a:b;int go(bool stage)int i,j,num,tmp

5、,ans;if(stage=right_to_left)num=0;an s=0;for(i=1;ia ns)an s=houri;if()return ans;ans=infini ty;for(i=1;i=n _1;i+)if(posi=right)for(j=i+1;j=n ;j+)if(posj=right)posi=left;posj=left;tmp=max(houri,hourj)+if(tmpa ns) an s=tmp;posi=right;posj=right;return ans;if(stage=left_to_right)ans=infini ty;for(i=1;i

6、=n ;i+)if()posi=right;tmp=;if(tmpa ns)an s=tmp; ;return ans;return 0;int mai n()int i;cinn;for(i=1;i houri;posi=right;coutgoright_to_left)e ndl;return 0;【算法】利用深搜，左右交替寻找最优解（maybe是动态规划）【代码】1、num=2;2、go1;3、posj=1;4、houri+go0;5、posi=1;【年份】2010年三、【题目】（子矩阵）给输入一个n 1*m1的矩阵a，和n2*m2的矩阵b，问a中是否存在子矩阵和 bThere isn

7、o an swer相等。若存在，输出所有子矩阵左上角的坐标：若不存在输出#in clude using n amespace std;const int SIZE = 50;int n1,m1, n2,m2,aSIZESIZE,bSIZESIZE;int mai n()int i,j,k1,k2;bool good,haveA ns;cinn 1m1;for(i=1;i=n 1;i+)for(j=1;jaij;cinn 2m2;for(i=1;i=n 2;i+)for(j=1;j=m2;j+) ;haveA ns=false;for(i=1;i=n1-n 2+1;i+)for(j=1;j=;j

8、+) ;for(k1=1;k1=n2;k1+)for(k2=1;k2=;k2+)if(ai+k1-1j+k2-1!=bk1k2)good=false;if(good)couti je ndl; ;if(!haveA ns)coutThere is no an swerbij;2、m1-m2+1; 3、good=1;4、m2;5、haveAns=1;【年份】2011年四、【题目】(大整数开方) 输入一个正整数 n (1 nw 100),试用二分法计算它的平方根的整数部分。#in clude#in cludeusing n amespace std;con st int SIZE=200;stru

9、ct huge intint len,nu mSIZE;/其中len表示大整数的位数；num1表示个位，num2表示十位，以此类推huge int times(huge int a,huge int b)/计算大整数a和b的乘积int i,j;huge int ans;memset(a ns.nu m,0,sizeof(a ns. nu m);for(i=1;i=aen ;i+)for(j=1;j=ben ;j+)+=a. numi*b. nu mj;for(i=1;i0) ans.len=a.len+b.len;elsean s.le n=a.le n+b.le n-1;return ans

10、;huge int add(huge int a,huge int b)/计算大整数a和b的和int i;huge int ans;memset(a ns.nu m,0,sizeof(a ns. nu m);if(a.lenb.len)ans.len=a.len;elseans.len=b.len;for(i=1;i0)ans.len+;return ans;huge int average(huge int a,huge int b)/计算大整数a和b的平均数的整数部分int i;huge int ans;an s=add(a,b);for(i=a nsen ;i=2;i_)ans.n um

11、i-1+=()*10;ans.nu mi/=2;ans.nu m1/=2;if(ans.nu ma ns.le n=0)ans.len-;return ans;huge int plustwo(huge int a)/计算大整数a加2之后的结果int i;huge int ans;an s=a;ans.nu m1+=2;i=1;while( (i=10)ans.nu mi+1+=a ns.nu mi/10;ans.nu mi%=10;i+；if(ans.nu ma ns.len+10) ；return ans;bool over(huge int a,huge int b)/ 若大整数ab则返

12、回true ，否则返回false int i;if()return false;if( a.lenb.len )return true;for(i=a.le n; i=1;i_)if(a. nu mib. nu mi)return true;return false;int mai n()stri ng s;int i;huge int target,left,middle,right;cin s;memset(target .num ,0,sizeof(target. nu m);target.le n=s.len gth();for(i=1;i=1;i-)coutleft.numi;ret

13、urn 0;【算法】每二分一次，就判断一下答案在哪个区间，然后在 那个区间继续二分，避免不必要的计算。【代码】 1、 ans.numi+j-12、ans.numi%=103、a.numi+b.numi4、ans.numi % 25、ans.len+6、a.lenb.len7、08、times(middle,middle),target【年份】 2011 年五、【题目】 (坐标统计)输入 n 个整点在平面上的坐标。对于每个点，可以控制所 有位于它左下方的点(即 x 、y 坐标都比它小)，它可以控制的点的数目称为“战斗力”。 依次输出每个点的战斗力， 最后输出战斗力最高的点的编号 (如果若干个点的

14、战斗力并列最 高，输出其中最大的编号)。#include using namespace std;const int SIZE =100;int xSIZE,ySIZE,fSIZE;int n,i,j,max_f,ans;int main()cinn;for(i=1;i xiyi; max_f=O;for(i=1;i=n ;i+)fi=；for(j=1;j=n ;j+)if(xjxi &) ；if()max_f=fi;；for(i=1;i=n ;i+) coutfie ndl; couta nse ndl;return 0;【算法】依次进行战斗力的计算，找出最大的一个【代码】1、0 2、yjm

15、ax_f )4、 （ i1）& （fifi-1）（我写的是5、ans=max_f （我写的是 ans=i）其实我做的是对的，正确答案有bug;【年份】2012年六、【题目】（排列数）输入两个正整数n, m（ 1*20,1mn），在1n中任取m个数，按字典序从小到大输出所有这样的排列。例如:输入：3 2输出：1 22 33 13 2#in elude #in elude using n amespaee std;const int SIZE =25;bool usedSIZE;int dataSIZE;int n,m,i,j,k;bool flag;int mai n()cinnm;memset

16、(used,false,sizeof(used); for(i=1;i=m;i+)datai=i;usedi=true;flag=true;while(flag)for(i=1;i=m-1;i+) coutdatai; coutdatam=1;i-)；for(j=datai+1;j=n ;j+) if(!usedj)usedj=true;datai=；flag=true;break;if(flag)for(k=i+1;k=m;k+) for(j=1;j=；j+)if(!usedj)datak=j;usedj=true; break;；return 0;【算法】直接进行枚举，一个个进行选择【代码

17、】1、02、useddatai=03、j4、n5、break【年份】2012年七、【题目】（二叉查找树）二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。试判断一棵树是否为二叉查找树。输入的第一行包含一个整数n,表示这棵树有n个顶点，编号分别为1,2, -n,其中编号为1的为根结点。之后的第i行有三个数value, left_child , right_child，分别表示该节点关键字的值、 左子节点的编号、右子节点的编号；如果不存在左子节点或右子节点，则用0代替。输出1表示这棵树是二叉查找树，输出0则表示不是。#in clude using n a

18、mespace std;con st int SIZE = 100;con st in tINFINITE = 1000000;struct node in t left_child, right_child, value;node aSIZE;int is_bst(int root, int lower_bound, int upper_bound)int cur;if (root = 0) return 1; cur = aroot.value;if (cur lower_bound) & (1) ) &/( 3分)(is_bst(aroot.left_child, lower_bound

19、, cur) = 1) & (is_bst(2) ,(3) ,(4) ) = 1)/ (3分， 3分， 3分) return 1;return 0;int main()int i, n;cinn;2分）for (i = 1; i ai.valueai.left_childai.right_child; coutis_bst(5) , -INFINITE, INFINITE)endl;/ return 0;【算法】 就是遍历一遍。【代码】 1、 j-i ；2、 cur1 ； 3、 count1-;4 、count2-;5 cur1=aj ；年份】 2013 年八、【题目】（数字删除 ）下面程序的

20、功能是将字符串中的数字字符删除后输出。请填空。（每空 3 分，共12 分 ）#include using namespace std;int delnum(char *s)int i, j;j = 0;for(i = 0; si != 0; i+)if(si 9) sj = si; 2 ;return 3 ;const int SIZE = 30;int main()char sSIZE;int len, i;cin.getline(s, sizeof(s);len = delnum(s);for(i = 0; i len; i+)cout 4) ;cout endl;return 0;【算法

21、】搜索一遍，把非字母的字符保留【代码】1、| 2 、j+ ； 3 、j 4 、si【年份】 2014 年九、【题目】（最大子矩阵和）给出m行n列的整数矩阵，求最大的子矩阵和 （子矩阵不能为空）。输入第一行包含两个整数 m和n,即矩阵的行数和列数。之后 m行，每行n个整数，描述整 个矩阵。程序最终输出最大的子矩阵和。 （最后一空 4分，其余 3分，共 16分） 比如在如下这个矩阵中：4 40 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2拥有最大和的子矩阵为：9 2-4 1-1 8其和为 153 3-2 10 20-1 100 -20 -2 -3最大子矩阵和为 1284 40

22、 -2 -9 -9-9 11 5 7-4 -3 -7 -6-1 7 7 5最大子矩阵和为 26#include using namespace std;const int SIZE = 100;int matrixSIZE + 1SIZE + 1;记录第 i 行前 j 个数的和int rowsumSIZE + 1SIZE + 1; /rowsumij int m, n, i, j, first, last, area, ans;int main()cin m n; for(i = 1; i = m; i+)for(j = 1; j matrixij;ans = matrix 1for(i =

23、1; i = m; i +) 2 ; for(i = 1; i = m; i+)for(j = 1; j = n; j+)rowsumij = 3for(first = 1; first = n; first+)for(last = first; last = n; last+) 4for(i = 1; i ans) ans = area;if(area 0)area = 0;cout ans endl;return 0;算法】三个 for ，枚举子矩阵左上，右上和高。遇到目前最大值就记录下来。 【代码】 1、 11 【 3】【 4】、【 4】 2、 rowsumi0 = 0（其实可以随便填，

24、比如【 2】【 3】、【 6 】都可以）3、 rowsumij - 1 + matrixij； 4、 area = 0 ；5、rowsumilast - rowsumifirst - 1【年份】 2014十、【题目】 （打印月历）输入月份m（iw me 12），按一定格式打印2015年第m月的月 历。 （第三、四空 2.5分，其余 3分）例如， 2015年1月的月历打印效果如下 （第一列为周日 ）：S M T W T F S1 2 34 5 6 7 8 9 1011 12 13 14 15 16 1718 19 20 21 22 23 2425 26 27 28 29 30 31#include #include using namespace std;const int dayNum = -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 3