高精度运算

类型数值范围占字节数Byte0..2551Word0..655352Shortint-128..1271Integer-32768..32767;2Longint-2147483648..21474836474Longword0..42949672954Int64-9223372036854775808..92233720368547758078QWord0..1844674407370955161581、数据的输入2、数据的存储3、数据的运算：进位和借位4、结果的输出：小数点的位置、处理多于的0等高精度运算涉及到的问题：一、高精度运算：加法【问题描述】输入：第一行：正整数a。第二行：正整数b。已知：a和b（10240）。输出：a＋b的值。样例输入：99999样例输出：1098高精度加法解决的问题：１、数据的输入２、数据的存储３、加法运算，注意进位处理４、结果的输出１、数据的输入a和b（10240）字符串输入：Vars1,s2:string;Readln(s1);Readln(s2);如果求a+b，（a，b=102000）定义：a，b：ansistring;{长度最多2552=65025}２、数据的存储为了计算方便，采用数组存储。Vara,b:array[1..240]ofinteger;将字符串转换为数组存储。用a存s1，b存s2。A[1]存个位，便于以后计算和进位处理len1:=length(s1);fori:=1tolen1doa[i]:=ord(s1[len1+1-i])-48;len2:=length(s2);fori:=1tolen2dob[i]:=ord(s2[len2+1-i])-48;S1=’3452345’….a[3]a[2]a[1]３、加法运算，注意进位处理。把计算结果存到数组c中：c：array[1..241]ofinteger;先计算。…….a[3]a[2]a[1]……b[3]b[2]b[1]+……c[3]c[2]c[1]iflen1len2thenlen:=len1elselen:=len2;fori:=1tolendoc[i]:=a[i]+b[i];{直接先计算}计算后的c[i]可能=10,怎样处理？处理进位：fori:=1tolendobeginc[i+1]:=c[i+1]+c[i]div10;c[i]:=c[i]mod10;end;４、结果的输出：数组c。ifc[len+1]0thenlen:=len+1;fori:=lendownto1dowrite(c[i]);constmaxn=240;{c=a+b,先加，然后再处理进位}vars1,s2:string;a,b:array[1..maxn]ofinteger;c:array[1..maxn+1]ofinteger;len,len1,len2,k,j,i:integer;beginreadln(s1);readln(s2);{输入}len1:=length(s1);fori:=1tolen1doa[i]:=ord(s1[len1+1-i])-48;len2:=length(s2);fori:=1tolen2dob[i]:=ord(s2[len2+1-i])-48;iflen1len2thenlen:=len1elselen:=len2;fori:=1tolendoc[i]:=a[i]+b[i];fori:=1tolendobeginc[i+1]:=c[i+1]+c[i]div10;c[i]:=c[i]mod10;end;ifc[len+1]0thenlen:=len+1;fori:=lendownto1dowrite(c[i]);end.constmaxn=240;{c=a+b,边加边处理进位}vars1,s2:string;len,len1,len2,k,j,i:integer;a,b:array[1..maxn]ofinteger;c:array[1..maxn+1]ofinteger;beginreadln(s1);readln(s2);len1:=length(s1);fori:=1tolen1doa[i]:=ord(s1[len1+1-i])-48;len2:=length(s2);fori:=1tolen2dob[i]:=ord(s2[len2+1-i])-48;iflen1len2thenlen:=len1elselen:=len2;fori:=1tolendobeginc[i+1]:=(a[i]+b[i]+c[i])div10;c[i]:=(a[i]+b[i]+c[i])mod10;end;ifc[len+1]0thenlen:=len+1;fori:=lendownto1dowrite(c[i]);end.算法改进一：边计算边处理进位算法改进二：结果存在数组a中，不再定义多余的数组c，减少存储空间。（最好的方法：a=a+b）beginreadln(s1);readln(s2);len1:=length(s1);len2:=length(s2);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fori:=1tolen1doa[i]:=ord(s1[len1-i+1])-48;fori:=1tolen2dob[i]:=ord(s2[len2-i+1])-48;iflen1len2thenlen:=len1elselen:=len2;fori:=1tolendobegina[i+1]:=a[i+1]+(a[i]+b[i])div10;a[i]:=(a[i]+b[i])mod10;end;ifa[len+1]0thenlen:=len+1;fori:=lendownto1dowrite(a[i]);end.高精度加法的应用Fibonacci数列Fibonacci数列的代表问题是由意大利著名数学家Fibonacci提出的“兔子繁殖问题”(又称“Fibonacci问题”)。问题的提出：有雌雄一对兔子，假定过两个月后便每个月可繁殖雌雄各一的一对小兔子。问过n个月后共有多少对兔子？已知：N=93。F(i):第i个月后共有的兔子对数。F(1)=1;F(2)=1;f(3)=2;f(4)=3;f(5)=5;f(6)=8;F(i)=f(i-2)+f(i-1){N=93}varf:array[1..100]ofqword;varn,i:integer;beginreadln(n);f[1]:=1;f[2]:=1;fori:=3tondof[i]:=f[i-2]+f[i-1];writeln(f[n]);end.N=1000}varn,len,i,k:integer;f1,f2,f:array[1..210]ofinteger;beginfillchar(f1,sizeof(f1),0);fillchar(f2,sizeof(f2),0);readln(n);f1[1]:=1;F2[1]:=1;len:=1;fork:=3tondobeginfillchar(f,sizeof(f),0);fori:=1tolendobeginf[i+1]:=(f1[i]+f2[i]+f[i])div10;f[i]:=(f1[i]+f2[i]+f[i])mod10;end;iff[len+1]0thenlen:=len+1;f1:=f2;f2:=f;end;writeln(len);fori:=lendownto1dowrite(f[i]);end.二、高精度减法运算问题表述：输入a，b（10240）两个数，输出a-b的值。样例2输入：9991000样例2输出：-1样例1输入：456409样例1输出：47算法：1、读入被减数s12、读入减数s23、如果s1s2，那么交换s1和s2。{只需要计算s1-s2}4、把s1存到数组a5、把s2存到数组b6、从低到高位计算a[i]=a[i]-b[i];注意借位7、输出数组a就是运算结果解决的问题：1、输入、保存2、比较a和b的大小。从而确定结果的正负号3、借位问题4、输出1、比较大小：如果s1s2，不交换，如果s1s2，交换s1和s2，保证后边s1-s2S1s2的条件：if(length(s1)length(s2))or((length(s1)=length(s2))and(s1s2))thenbeginfh:='-';s:=s1;s1:=s2;s2:=s;end;然后数组a存s1，b存s2。计算a=a-b2、借位：ifa[i]b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10;end;a[i]:=a[i]-b[i];{a=a-b}typenumtype=array[1..240]ofinteger;vara,b:numtype;s1,s2,s:string;la,lb,k:integer;i:integer;fh:char;beginreadln(s1);readln(s2);ifs1=s2thenbeginwriteln(0);halt;end;if(length(s1)length(s2))or((length(s1)=length(s2))and(s1s2))thenbeginfh:='-';s:=s1;s1:=s2;s2:=s;end;la:=length(s1);lb:=length(s2);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fori:=1toladoa[i]:=ord(s1[la-i+1])-48;fori:=1tolbdob[i]:=ord(s2[lb-i+1])-48;k:=la;fori:=1tokdobeginifa[i]b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10;end;a[i]:=a[i]-b[i];end;whilea[k]=0dok:=k-1;iffh='-'thenwrite(fh);fori:=kdownto1dowrite(a[i]);writeln;end.{a=a-b}vara,b:array[1..240]ofinteger;s1,s2:string;proceduresub(x,y:string);varla,lb,k:integer;i:integer;beginla:=length(x);lb:=length(y);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);fori:=1toladoa[i]:=ord(x[la-i+1])-48;fori:=1tolbdob[i]:=ord(y[lb-i+1])-48;k:=la;fori:=1tokdobeginifa[i]b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10;end;a[i]:=a[i]-b[i];end;whilea[k]=0dok:=k-1;fori:=kdownto1dowrite(a[i]);end;beginreadln(s1);readln(s2);ifs1=s2thenbeginwriteln(0);halt;end;if(length(s1)length(s2))or((length(s1)=length(s2))and(s1s2))thensub(s1,s2)elsebeginwrite('-');sub(s2,s1);end;end.三、高精度乘法1、高精度乘单精度（整数），求a*b，a=10200,b=108vari,len:integer;s:string;b,m:longint;a:array[1..250]oflongint;beginreadln(s);{读入被乘数a}readln(b);{读入乘数b}len:=length(s);fori:=1