历年noip普及组完善程序题总结归纳_第1页
历年noip普及组完善程序题总结归纳_第2页
历年noip普及组完善程序题总结归纳_第3页
历年noip普及组完善程序题总结归纳_第4页
历年noip普及组完善程序题总结归纳_第5页
已阅读5页,还剩13页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论