高精度运算(加减).doc

安阳一中信息学奥赛辅导资料高精度计算(一)一、 教学目标l 了解什么是高精度计算。为什么要进行高精度计算。l 熟练掌握基本的加、减高精度计算二、 重点难点分析l 高精度数的存储方式；三、 教具或课件使用多媒体演示文稿四、 主要教学过程(一) 引入新课利用计算机进行数值计算,有时会遇到这样的问题:有些计算要求精度高,希望计算的数的位数可达几十位甚至几百位,虽然计算机的计算精度也算较高了,但因受到硬件的限制,往往达不到实际问题所要求的精度.我们可以利用程序设计的方法去实现这们的高精度计算.这里仅介绍常用的几种高精度计算的方法。(二) 教学过程设计1、高精度计算中需要处理好以下几个问题:（1）数据的接收方法和存贮方法数据的接收和存贮:当输入的数很长时,可采用字符串方式输入,这样可输入数字很长的数,利用字符串函数和操作运算,将每一位数取出,存入数组中.Type numtype=array1.500of word；整数数组类型Var a，b:numtype； a和b为整数数组la，lb:integer； 整数数组a的长度和b的长度s:string； 输入数串将数串s转化为整数数组a的方法如下：readln(s); la:=length(s)； for i:=1 to la do ala-i+1:=ord(si)-ord(0); 另一种方法是直接用循环加数组方法输入数据.Type arr= array1.100 of integer;prucedure readdata(var int:arr); var ch:char; i,k:integer; begin read(ch);k:=0; while ch in0.9 do begin inc(k);intk:=ord(ch)-ord(0); read(ch); end; end;储存数据一律用数组。根据不同的需要，数据的储存可分正向与反向两种。以输入数1234为例： 正向储存：数位权的大小与储存数组的下标的大小一致 下标大 下标小数组各元素 a4 a3 a2 a1 所存的数字 1 2 3 4 最高位 最低位反向储存：数位权的大小与储存数组的下标的大小相反 下标小 下标大数组各元素 a1 a2 a3 a4 所存的数字 1 2 3 4 最高位 最低位 加法、减法、乘法的运算是从低位开始的，所以数据储存采取正向储存比较方便。(2) 计算结果位数的确定两数之和的位数最大为较大的数的位数加1。乘积的位数最大为两个因子的位数之和。(3) 进位,借位处理加法进位: Ci:= Ai+Bi;if Ci=10 then begin Ci:= Ci mod 10; Ci+1:= Ci+1+1 end;减法借位: if aibi then begin ai+1:=ai+1-1;ai:=ai+10 endci:=ai-bi乘法进位: x:= Ai*Bj+ x DIV 10+ Ci+j-1;Ci+j-1 := x mod 10;(4) 商和余数的求法商和余数处理:视被除数和除数的位数情况进行处理.2、高精度计算举例【例1】 从键盘读入两个正整数，求它们的和。分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal 语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。 这样，我们方便写出两个整数相加的算法。8 5 6+ 2 5 5-1 1 1 1图1如果我们用数组A、B分别存储加数和被加数，用数组C 存储结果。则上例有A1=6, A2=5, A3=8, B1=5,B2=5, B3=2, C4=1,C3=1, C2=1,C1=1,两数相加如图2所示。A3 A2 A1+B3 B2 B1-C4 C3 C2 C1图2因此，算法描述如下：procedure add(a,b;var c); a,b,c 都为数组，a存储被加数，b 存储加数，c 存储结果 var i,x:integer;begini:=1while (i=a 数组长度) or(i=b 数组的长度) do beginx := ai + bi + x div 10; 第i位相加并加上次的进位ci := x mod 10; 存储第i 位的值i := i + 1 位置指针变量endend;通常，读入的两个整数用可用字符串来存储，程序设计如下：program exam1;const max=200;var a,b,c:array1.max of 0.9; n:string; lena,lenb,lenc,i,x:integer;beginwrite(Input augend:); readln(n);lena:=length(n); 加数放入a 数组for i:=1 to lena do alena-i+1:=ord(ni)-ord(0);write(Input addend:); readln(n);lenb:=length(n); 被加数放入b数组for i:=1 to lenb do blenb-i+1:=ord(ni)-ord(0);i:=1;while (i=lena) or(i=10 then 处理最高进位begin lenc:=i;ci:=1; endelse lenc:=i-1;for i:=lenc downto 1 do write(ci); 输出结果writelnend.【例2】 高精度减法（a-b）(ab且a,b均为正整数) 。从键盘读入两个正整数，求它们的差。分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。高精度减法的参考程序：program exam2;constmax=200;vara,b,c:array1.max of 0.9;n,n1,n2:string;lena,lenb,lenc,i,x:integer;beginwrite(Input minuend:); readln(n1);write(Input subtrahend:); readln(n2); 处理被减数和减数if (length(n1)length(n2) or (length(n1)=length(n2) and (n1n2) thenbeginn:=n1;n1:=n2;n2:=n;write(-) n1n2,结果为负数end;lena:=length(n1); lenb:=length(n2);for i:=1 to lena do alena-i+1:=ord(n1i)-ord(0);for i:=1 to lenb do blenb-i+1:=ord(n2i)-ord(0);i:=1;while (i=lena) or(i1) do dec(lenc); 最高位的0 不输出for i:=lenc downto 1 do write(ci);writelnend.【补充例题】高精度加减法，把输入的数可能有负数也考虑进去的程序。【变量与算法设计】用两个逻辑变量f与f1。用f1来控制运算：当f1为假做加法，当f1为真做减法。当f为真来控制数前负号的输出。具体设置如下：两个数同号f1为假（做加法运算）两个数都是正数，f为假两个数都是负数，f为真。（f为真输出负号，下同） 两个数异号f1为真（做减法运算）第一个为负数，第二个为正数。第一个数的绝对值大于第二个数的绝对值。f为真第一个为负数，第二个数正数。第一个数的绝对值小于第二个数的绝对值。f为假第一个数正数，第二个为负数。第一个数的绝对值大于第二个数的绝对值。f为假第一个为正数，第二个为负数。第一个数的绝对值小于第二个数的绝对值。f为真【程序清单】PROGRAM P12_10A;CONST n=200;VAR str1,str2,str:STRING; k,l1,l2,i,j,t:Integer; a,b:ARRAY 1.n OF Integer; fa,fb:Char; f1,f:Boolean;BEGIN Write(Input a string str1 : ); Readln(str1); Write(Input a string str2 : ); Readln(str2); l1:=Length(str1); l2:=Length(str2); fa:=str11; fb:=str21; f1:=False; f:=f1; 取符号位，设置f1、f的值 IF (fa=-) AND (fb=-) 如都是负数，去掉符号位 THEN BEGIN重新设置f1、f的值 f1:=False; f:=True; str1:=Copy(str1,2,l1); l1:=l1-1; str2:=Copy(str2,2,l2); l2:=l2-1 END ELSE BEGIN IF fa=- THEN 如第一个数是负数，去掉其符号位，重新设置f1、f的值 BEGIN f1:=True; f:=f1; str1:=Copy(str1,2,l1); l1:=l1-1 END; IF fb=- THEN如第二个数是负数，去掉其符号位，重新设置f1、f的值 BEGIN f1:=True; f:=False; str2:=Copy(str2,2,l2); l2:=l2-1 END END; j:=l1; 如第二个数的绝对值大于第一个数的绝对值就交换，重新设置f的值 IF (l2l1) OR f1 AND (l2=l1) AND (str2str1) THEN BEGIN f:=NOT(f); j:=l2; str:=str1; str1:=str2; str2:=str END; FOR i:=length(str1) DOWNTO 1 DO BEGIN 字符串分离同时转换成数字,存入a数组 Val(str1i,al1+1-i,k); 不能转换成数字时，输出出错信息 IF k0 THEN BEGIN Writeln(Str1 data error !); Readln; Exit END END; FOR i:=length(str2) DOWNTO 1 DO BEGIN 字符串分离同时转换成数字,存入b数组 Val(str2i,bl2+1-i,k); 不能转换成数字时，输出出错信息 IF k0 THEN BEGIN Writeln(Str2 data error !); Readln; Exit END END; IF f1 THEN BEGINf1为真做减法 FOR i:=1 TO j DO BEGIN ai:=ai-bi; k:=Ord(ai0) DO j:=j-1有效数字前无用的0不输出 END ELSE BEGINf1为假做加法 FOR i:=1 TO j DO BEGIN k:=ai+bi; ai:=k MOD 10; 加法进位 ai+1:=ai+1+k DIV 10 END; IF ai+10 THEN j:=j+1 最后一次进位 END; Write(Xiang Jia He : ); 输出 IF j=0 THEN Write(0) ELSE BEGIN IF f THEN Write(-); 输出符号位 FOR i:=j DOWNTO 1 DO Write(ai)高精度输出 END; Writeln; ReadlnEND.3、【上机练习】1 将例1、例2中的程序用过程函数完善程序。2 高精度加法/vijos/Problem_Show.asp?id=15703 高精度减法/vijos/Problem_Show.asp?id=15694 费波那契数列:8000/vijos/Problem_Show.asp?id=1435费波那契数列的前两项分别为1,1。以后每项为前两项之和。输入n,求费波那契数列前n项的和(1=n=5000)。 输入：仅一个数，n输出：费波那契数列前n项之和。Sample Input3Sample Output4-对于样例的解释费波那契数列前三项是1,1,2，和为4。5 回文数。:8000/vijos/Problem_Show.asp?id=1008 若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把56从右向左读），得