历年noip普及组(c++)完善程序题总结归纳.doc
《历年noip普及组(c++)完善程序题总结归纳.doc》由会员分享,可在线阅读,更多相关《历年noip普及组(c++)完善程序题总结归纳.doc(21页珍藏版)》请在三一文库上搜索。
1、.完善程序题总结归纳 By:七(6) yx一、【题目】(哥德巴赫猜想)哥德巴赫猜想是指,任一大于2的偶数都可写成两个质数之和。迄今为止,这仍然是一个著名的世界难题,被誉为数学王冠上的明珠。试编写程序,验证任一大于2且不超过n的偶数都能写成两个质数之和。#includeusing namespace std;int main() const int SIZE=1000; int n,r,pSIZE,i,j,k,ans; 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;
2、if(tmp) r+; ; ans=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+; coutansendl; return 0;若输入n为2010,则输出 时表示验证成功,即大于2且不超过2010的偶数都满足哥德巴赫猜想。【算法】先for一遍,找出质数,然后对每一个偶数进行一一匹配(2除外),效率O(n3)【代码】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.#include#includeusing namespace 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(int a,int b)return ab?a:b;int go(bool stage) int i
5、,j,num,tmp,ans; if(stage=right_to_left) num=0; ans=0; for(i=1;ians) ans=houri; if( ) return ans; ans=infinity; 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(tmpans) ans=tmp; posi=right; posj=right; return ans; if(stage=left_to_righ
6、t)精品. ans=infinity; for(i=1;i=n;i+) if( ) posi=right; tmp= ; if(tmpn; for(i=1;ihouri; posi=right; coutgoright_to_left)endl; return 0;【算法】利用深搜,左右交替寻找最优解(maybe是动态规划)【代码】1、num=2;2、go1;3、posj=1;4、houri+go0;5、posi=1;【年份】2010年三、【题目】精品.(子矩阵)给输入一个n1*m1的矩阵a,和n2*m2的矩阵b,问a中是否存在子矩阵和b相等。若存在,输出所有子矩阵左上角的坐标:若不存在输出“
7、There isno answer”。#includeusing namespace std;const int SIZE = 50;int n1,m1,n2,m2,aSIZESIZE,bSIZESIZE;int main() int i,j,k1,k2; bool good,haveAns; cinn1m1; for(i=1;i=n1;i+) for(j=1;jaij; cinn2m2; for(i=1;i=n2;i+) for(j=1;j=m2;j+) ; haveAns=false; for(i=1;i=n1-n2+1;i+) for(j=1;j= ;j+) ; for(k1=1;k1=
8、n2;k1+) for(k2=1;k2= ;k2+) if(ai+k1-1j+k2-1!=bk1k2) good=false; if(good) couti jendl; ; if(!haveAns) coutThere is no answerbij;2、m1-m2+1;3、good=1;4、m2;5、haveAns=1;【年份】2011年四、【题目】(大整数开方) 输入一个正整数n(1n10100),试用二分法计算它的平方根的整数部分。#include#includeusing namespace std;const int SIZE=200;struct hugeint int len,
9、numSIZE;/其中len表示大整数的位数;num1表示个位,num2表示十位,以此类推hugeint times(hugeint a,hugeint b)/ 计算大整数a和b的乘积 int i,j; hugeint ans; memset(ans.num,0,sizeof(ans.num); for(i=1;i=a.len;i+) for(j=1;j=b.len;j+) +=a.numi*b.numj; for(i=1;i0) ans.len=a.len+b.len; else ans.len=a.len+b.len-1;精品. return ans;hugeint add(hugeint
10、 a,hugeint b)/计算大整数a和b 的和 int i; hugeint ans; memset(ans.num,0,sizeof(ans.num); if(a.lenb.len) ans.len=a.len; else ans.len=b.len; for(i=1;i0) ans.len+; return ans;hugeint average(hugeint a,hugeint b)/计算大整数a和b的平均数的整数部分 int i; hugeint ans; ans=add(a,b); for(i=ans.len;i=2;i-) ans.numi-1+=( )*10; ans.nu
11、mi/=2; ans.num1/=2; if(ans.numans.len=0) ans.len-; return ans;hugeint plustwo(hugeint a)/ 计算大整数a加2之后的结果精品. int i; hugeint ans; ans=a; ans.num1+=2; i=1; while( (i=10) ) ans.numi+1+=ans.numi/10; ans.numi%=10; i+; if(ans.numans.len+10) ; return ans;bool over(hugeint a,hugeint b)/ 若大整数ab则返回true,否则返回fals
12、e int i; if( ) return false; if( a.lenb.len ) return true; for(i=a.len;i=1;i-) if(a.numib.numi) return true; return false;int main() string s; int i; hugeint target,left,middle,right; cins; memset(target.num,0,sizeof(target.num); target.len=s.length(); for(i=1;i=1;i-) coutleft.numi; return 0;【算法】每二分
13、一次,就判断一下答案在哪个区间,然后在那个区间继续二分,避免不必要的计算。【代码】1、 ans.numi+j-1 2、 ans.numi%=103、a.numi+b.numi 4、ans.numi % 25、ans.len+6、a.lenb.len7、08、times(middle,middle),target【年份】2011年五、【题目】(坐标统计)输入n个整点在平面上的坐标。对于每个点,可以控制所有位于它左下方的点(即x、y坐标都比它小),它可以控制的点的数目称为“战斗力”。依次输出每个点的战斗力,最后输出战斗力最高的点的编号(如果若干个点的战斗力并列最高,输出其中最大的编号)。精品.#i
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 历年 noip 普及 完善 程序 总结 归纳
链接地址:https://www.31doc.com/p-8620232.html