《历年noip普及组(c++)完善程序题总结归纳[精推]》由会员分享，可在线阅读，更多相关《历年noip普及组(c++)完善程序题总结归纳[精推]（19页珍藏版）》请在金锄头文库上搜索。
1、完善程序题总结归纳 By：七（6） yx 一、 【题目】（哥德巴赫猜想）哥德巴赫猜想是指，任一大于 2 的偶数都可写成两个 质数之和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写 程序，验证任一大于 2 且不超过 n 的偶数都能写成两个质数之和。 #include using 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=fa
2、lse; break; 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、100
3、4 【年份】2010 年 二、 【题目】(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一 的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的 是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独 过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有 一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入 N(2=N1000)和 这 N 个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸. 例如,有 3 个人甲、乙、丙,他们单独过桥的时间分别为 1、
4、2、4,则总共最少需要的时 间为 7.具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、 丙在一起过桥到河的左岸,总时间为 2+1+4=7. #include #include using 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
5、max(int a,int b)return ab?a:b; int go(bool stage) int i,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; po
6、si=right; posj=right; return ans; if(stage=left_to_right) 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 年 三、 【题目】 （子矩阵）（子矩阵）给输
7、入一个 n1*m1 的矩阵 a，和 n2*m2 的矩阵 b，问 a 中是否存在子矩阵和 b 相等。若存在，输出所有子矩阵左上角的坐标：若不存在输出“There isno answer” 。 #include using 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=
8、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(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） ，试用二
9、分法计算它的平方根的整数部分。 #include #include using 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+) +=
10、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 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
11、,hugeint b) /计算大整数 a 和 b 的平均数的整数部分 int i; hugeint ans; ans=add(a,b); for(i=ans.len;i=2;i-) ans.numi-1+=( )*10; ans.numi/=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+=
12、ans.numi/10; ans.numi%=10; i+; if(ans.numans.len+10) ; return ans; bool over(hugeint a,hugeint b) / 若大整数 ab 则返回 true，否则返回 false 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,mid
13、dle,right; cins; memset(target.num,0,sizeof(target.num); target.len=s.length(); for(i=1;i=1;i-) coutleft.numi; return 0; 【算法】每二分一次，就判断一下答案在哪个区间，然后 在那个区间继续二分，避免不必要的计算。 【代码】1、 ans.numi+j-1 2、 ans.numi%=10 3、a.numi+b.numi 4、ans.numi % 2 5、ans.len+ 6、a.lenb.len 7、0 8、times(middle,middle),target 【年份】2011 年 五、 【题目】（坐标统计）输入 n 个整点在平面上的坐标。对于每个点，可以控制所 有位于它左下方的点（即 x、y 坐标都比它小），它可以控制的点的数目称为“战斗力”。 依次输出每个点的战斗力，最后输出战斗力最高的点的编号（如果若干个点的战斗力并列 最高，输出其中最大的编号）。
