NOIP复习资料终极版.docVIP

宜昌一中2009NOIP复习资料 感谢唐弢（TT）、刘炟呈（CRL）、陈艺（衬衣）、猫（向缪丹妮） 等众位大牛的倾力支持 特别感谢袁逸铭（yym）大牛的增添和指正 预祝宜昌一中NOIP2009大捷！ Quaty（高铭尉） 2009-11-19 高精度 ·读入与输出 用字符串读入数据，用数组存储数据。 为了便于计算，可以用数组下标为0的元素记录该高精度数的长度。 ｛说明部分｝ const maxn=250; type arr=array[0..maxn] of integer; var a,b:arr; ｛读入部分｝ procedure init(var a:arr); var str:string; i,j,l:integer; begin readln(str); fillchar(a,sizeof(a),0); a[0]:=length(str); for i:=1 to a[0] do a[i]:=ord(str[a[0]-i+1])-ord(‘0’); end; ｛输出部分｝ procedure print(a:arr); var i:integer; begin for i:=a[0] downto 1 do write(a[i]); writeln; end; {主程序部分} begin init(a); init(b); print(a); print(b); end. ·高精度加法 A[i]+B[i]+进位得到和M； M mod 10是结果的第i位数字； M div 10 是该位向下一位的进位。 procedure add(var a:arr;b:arr); var m,i,j:integer; begin if a[0]b[0] then a[0]:=b[0]; m:=0; for i:=1 to a[0] do begin m:=m+a[i]+b[i]; a[i]:=m mod 10; m:=m div 10; end; if m0 then begin inc(a[0]); a[a[0]]:=m; end; end; ·高精度减法 procedure minus(var a:arr;b:arr;var p:integer);{a-b} var i,j,k,m:integer; temp:arr; begin if a[0]b[0] then p:=1 else if a[0]b[0] then p:=-1 else begin k:=a[0]; while (a[k]=b[k]) and (k0) do dec(k); if a[k]b[k] then p:=-1; end; if p0 then begin temp:=a; a:=b; b:=temp; end; for i:=1 to a[0] do begin a[i]:=a[i]-b[i]; if a[i]0 then begin dec(a[i+1]); inc(a[i],10); end; end; k:=a[0]; while (a[k]=0) and (k1) do dec(k); a[0]:=k; end; ·高精度减法（by yym大牛） if (length(n1)length(n2)) or (length(n1)=length(n2)) and (n1n2) then begin n:=n1; n1:=n2; n2:=n; write(-); end; lena:=length(n1); lenb:=length(n2); for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord(0); for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord(0); i:=1; while (i=lena) or(i=lenb) do begin x:=a[i]-b[i]+10+x; c[i]:=x mod 10; x:=x div 10-1; i:=i+1; end; lenc:=i; while (c[lenc]=0) and (lenc1) do dec(lenc); ?高精度乘法 高精度乘以单精度 procedure multi1( var a:arr;x:integer); var i,m:integer; begin m:=0; f