《2006~2011noip初赛程序设计题(含答案).doc》由会员分享，可在线阅读，更多相关《2006~2011noip初赛程序设计题(含答案).doc（20页珍藏版）》请在金锄头文库上搜索。
1、程序设计题集锦NOIP20111（子矩阵）输入一个n1*m1的矩阵a，和n2*m2的矩阵b。问a中是否存在子矩阵和b相等。若存在，输出所有子矩阵左上角的坐标；若不存在输出“There is no answer”。constsize=50;varn1,m1,m2,i,j,k1,k2:integer;a,b:array1.size,1.size of integer;good,haveAns:boolen;beginreadln(n1,m1);for i:=1 to n1 dofor j:=1 to m1 doread(aij);readln(n2,m2);for i:=1 to n2 dofor
2、 j:=1 to m2 do ;haveAns:=false;for i:=1 to n1-n2+1 dofor j:=1 to dobegin ;for k1:=1 to n2 dofor k2:=1 to doif ai+k1-1j+k2-1bk1k2 thengood:=false;if good thenbeginwriteln(i, ,j); ;end;end;if not haveAns then writeln(There is no answer);end.2.（大整数开方）输入一个正整数n（1n10100），试用二分法计算它的平方根的整数部分。const SIZE=200;t
3、ype hugeint=record len:integer; num:array1.SIZE of integer; end; /len表示大整数的位数;num1表示个位num2表示十位，以此类推var s:string; i:integer; target,left,middle,right:hugeint;function times(a,b:hugeint):hugeint;/计算大整数a和b的乘积var i,j:integer; ans:hugeint;begin fillchar(ans,sizeof(ans),0); for i:=1 to a.len do for j:=1 t
4、o b.len do :=ans.numi+j-1 +a.numi*b.numj; for i:=1 to a.len+b.len do begin ans.numi+1:=ans.numi+1+ans.numi div 10; ; if ans.numa.len+b.len0 then ans.len:=a.len+b.len else ans.len:=a.len+b.len-1; end; times:=ans;end;function add(a,b:hugeint):hugeint;/计算大整数a和b的和var i:integer; ans:hugeint;begin fillcha
5、r(ans.num,sizeof(ans.num),0); if a.lenb.len then ans.len:=a.len else ans.len:=b.len; for i:=1 to ans.len do begin ans.numi:= ； ans.numi+1:=ans.numi+1+ans.numi div 10; ans.numi:=ans.numi mod 10; end; if ans.numans.len+10 then inc(ans.len); add:=ans;end;function average(a,b:hugeint):hugeint;/计算大整数a和b的
6、平均数的整数部分var i:integer; ans:hugeint;begin ans:=add(a,b); for i:=ans.len downto 2 do begin ans.numi-1:=ans.numi-1+（ ）*10; ans.numi:=ans.numi div 2; end; ans.num1:=ans.num1 div 2; if ans.numans.len=0 then dec(ans.len); average:=ans;end;function plustwo(a:hugeint):hugeint;/计算大整数a加2后的结果var i:integer; ans
7、:hugeint;begin ans:=a; ans.num1:=ans.num1 + 2; i:=1; while (i=10) do begin ans.numi+1:=ans.numi+1+ans.numi div 10; ans.numi:=ans.numi mod 10; inc(i); end; if ans.numans.len+10 then ; plustwo:=ans;end;function over(a,b:hugeint):boolean;/若大整数ab则返回1，否则返回0var i:integer;begin if ( ;) then begin over:=fal
8、se; exit; end; if a.lenb.len then begin over:=true; exit; end; for i:=a.len downto 1 do begin if a.numib.numi then begin over:=true; exit; end; end; over:=false;end;begin readln(s); fillchar(target.num,sizeof(target.num),0); target.len:=length(s); for i:=1 to target.len do target.numi:=ord(starget.l
9、en-i+1)- ; fillchar(left.num,sizeof(left.num),0); left.len:=1; left.num1:=1; right:=target; repeat middle:=average(left,right); if over( ) then right:=middle else left:=middle; until over(plustwo(left),right); for i:=left.len downto 1 do write(left.numi); writeln;End.NOIP20101.（哥德巴赫猜想）哥德巴赫猜想是指，任一大于2
10、的偶数都可写成两个质数的和。迄今为止，这仍然是一个著名的世界难题，被誉为数学王冠上的明珠。试编写程序，验证任一大于2且不超过n的偶数都能写成两个质数之和。const size=1000;var n,r,I,j,k,ans:integer; p：array1.size of integer; tmp:Boolean;begin readln(n); r:=1; p1:=2; for i:=3 to n do begin ； for j:=1 to r do if I mod =0 thenbegin tmp:=false; break;end;if tmp thenbegin inc(r); ;end; end; ans:=0; for i:=2 to (n div 2) do begin tmp:=false; for j:=1 to r do for k:=j to r do if i+i=
