《历年noip普及组c++)完善程序题总结归纳资料》由会员分享，可在线阅读，更多相关《历年noip普及组c++)完善程序题总结归纳资料（18页珍藏版）》请在金锄头文库上搜索。
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; i
2、f(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,j,num,
5、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_right) ans=
6、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相等。若存在，输出所有子矩阵左上角的坐标：若不存在输出“There isno an
7、swer”。#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=n2;k1+) for(k
8、2=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,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.l
