2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 多精度数值处理.doc

2019-2020年高中信息技术 全国青少年奥林匹克联赛教案 多精度数值处理课题：多精度数值的处理目标：知识目标：多精度值的加、减、乘、除能力目标：多精度值的处理，优化！重点：多精度的加、减、乘难点：进位与借位处理板书示意：1） 输入两个正整数，求它们的和2） 输入两个正整数，求它们的差3） 输入两个正整数，求它们的积4） 输入两个正整数，求它们的商授课过程：所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。例1 从键盘读入两个正整数，求它们的和。分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。这样，我们方便写出两个整数相加的算法。 8 5 6 + 2 5 5 1 1 1 1 图1 A3 A2 A1+ B3 B2 B1 C4 C3 C2 C1 图2如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。则上例有A1=6, A2=5, A3=8, B1=5,B2=5, B3=2, C4=1,C3=1, C2=1,C1=1,两数相加如图2所示。由上图可以看出：Ci:= Ai+Bi;if Ci>10 then begin Ci:= Ci mod 10; Ci+1:= Ci+1+1 end;因此，算法描述如下：procedure add(a,b;var c); a,b,c都为数组，a存储被加数，b存储加数，c存储结果 var i,x:integer;begin i:=1 while (i<=a数组长度>0) 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;begin write(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<=lenb) do begin x := ai + bi + x div 10; 两数相加，然后加前次进位 ci := x mod 10; 保存第i位的值 i := i + 1 end; if x>=10 then 处理最高进位begin lenc:=i;ci:=1 end else lenc:=i-1; for i:=lenc downto 1 do write(ci); 输出结果 writelnend.例2 高精度减法。从键盘读入两个正整数，求它们的差。分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。因此，可以写出如下关系式if ai<bi then begin ai+1:=ai+1-1;ai:=ai+10 endci:=ai-bi类似，高精度减法的参考程序：program exam2;const max=200; var a,b,c:array1.max of 0.9; n,n1,n2:string; lena,lenb,lenc,i,x:integer;begin write(Input minuend:); readln(n1); write(Input subtrahend:); readln(n2); 处理被减数和减数 if (length(n1)<length(n2) or (length(n1)=length(n2) and (n1<n2) then begin n:=n1;n1:=n2;n2:=n; write(-) n1<n2,结果为负数 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(i<=lenb) do begin x := ai - bi + 10 + x; 不考虑大小问题，先往高位借10 ci := x mod 10 ; 保存第i位的值 x := x div 10 - 1; 将高位借掉的1减去 i := i + 1 end; lenc:=i; while (clenc=0) and (lenc>1) do dec(lenc); 最高位的0不输出 for i:=lenc downto 1 do write(ci); writelnend.例3 高精度乘法。从键盘读入两个正整数，求它们的积。分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进乘法运算时，必须进行错位相加，如图3, 图4。 8 5 6 2 5 4 2 8 0 1 7 1 2 2 1 4 0 0 图3A 3 A 2 A 1 B 3 B 2 B 1 C4C3 C2 C1 C”5C”4C”3C”2 C 6 C 5 C 4 C 3 C 2 C 1 图4分析C数组下标的变化规律，可以写出如下关系式C i = C i +C ”i +由此可见，C i跟Ai*Bj乘积有关，跟上次的进位有关，还跟原C i的值有关，分析下标规律，有x:= Ai*Bj+ x DIV 10+ Ci+j-1;Ci+j-1 := x mod 10; 类似，高精度乘法的参考程序：program exam3;const max=200;var a,b,c:array1.max of 0.9; n1,n2:string; lena,lenb,lenc,i,j,x:integer;begin write(Input multiplier:); readln(n1); write(Input multiplicand:); readln(n2); 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); for i:=1 to lena do begin x:=0; for j:=1 to lenb do begin 对乘数的每一位进行处理 x := ai*bj + x div 10 + ci+j-1; 当前乘积+上次乘积进位+原数 ci+j-1 := x mod 10; end; ci+j:= x div 10; 进位 end; lenc:=i+j; while (clenc=0) and (lenc>1) do dec(lenc); for i:=lenc downto 1 do write(ci); writelnend.例 高精度除法。从键盘读入两个正整数，求它们的商（做整除）。分析：做除法时，每一次上商的值都在，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度乘法，用09次循环减法取代得到商的值。这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法。参考程序：program exam4;const max=200;var a,c:array1.max of 0.9; x,b:longint; n1,n2:string; lena:integer; code,i,j:integer;begin write(Input dividend:); readln(n1); write(Input divisor:); readln(n2); lena:=length(n1); for i:=1 to lena do ai := ord(n1i) - ord(0); val(n2,b,code); 按位相除 x:=0; for i:=1 to lena do begin ci:=(x*10+ai) div b; x:=(x*10+ai) mod b; end; 显示商 j:=1; while (cj=0) and (j<lena) do inc(j); 去除高位的0 for i:=j to lena do write(ci) ; writelnend.实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。例如图5就是采用4位保存的除法运算，其他运算也类似。具体程序可以修改上述例题予以解决，程序请读者完成。