高精度学习教程和方法.docx
《高精度学习教程和方法.docx》由会员分享,可在线阅读,更多相关《高精度学习教程和方法.docx(14页珍藏版)》请在冰点文库上搜索。
![高精度学习教程和方法.docx](https://file1.bingdoc.com/fileroot1/2023-5/12/80dfcd04-cd3a-44ea-b829-31d9d03a0b28/80dfcd04-cd3a-44ea-b829-31d9d03a0b281.gif)
高精度学习教程和方法
高精度加法
vars1,s2:
string;
a,b,c:
array[1..260]ofinteger;
i,l,k1,k2:
integer;
begin
write('inputs1:
');readln(s1);
write('inputs2:
');readln(s2);
{————读入两个数s1,s2,都是字符串类型}
l:
=length(s1);{求出s1的长度,也即s1的位数;有关字符串的知识。
}
k1:
=260;
fori:
=ldownto1do
begin
a[k1]:
=ord(s1)-48;{将字符转成数值}
k1:
=k1-1;
end;
k1:
=k1+1;
{————以上将s1中的字符一位一位地转成数值并存在数组a中;低位在后(从第260位开始),高位在前(每存完一位,k1减1),完后,k1指向最高位}
对s2的转化过程和上面一模一样。
二、运算过程
在往下看之前,大家先列竖式计算35+86。
注意的问题:
(1)运算顺序:
两个数靠右对齐;从低位向高位运算;先计算低位再计算高位;
(2)运算规则:
同一位的两个数相加再加上从低位来的进位,成为该位的和;这个和去掉向高位的进位就成为该位的值;如上例:
3+8+1=12,向前一位进1,本位的值是2;可借助MOD、DIV运算完成这一步;
(3)最后一位的进位:
如果完成两个数的相加后,进位位值不为0,则应添加一位;
(4)如果两个加数位数不一样多,则按位数多的一个进行计算;
ifk1>k2thenk:
=k1elsek:
=k2;
y:
=0;
fori:
=260downtokdo
begin
x:
=a+b+y;
c:
=xmod10;
y:
=xdiv10;
end;
ify<>0thenbegink:
=k-1;c[k]:
=y;end;
三、结果的输出(这也是优化的一个重点)
按运算结果的实际位数输出
fori:
=kto260dowrite(c);
writeln;
例子:
求两个数的加法
programsum;
vars,s1,s2:
string;
a,b,c:
array[1..260]ofinteger;
x,y,i,l,k1,k2,k:
integer;
begin
write('inputs1:
');readln(s1);
write('inputs2:
');readln(s2);
l:
=length(s1);
k1:
=260;
fori:
=ldownto1do
begin
a[k1]:
=ord(s1[i])-48;
k1:
=k1-1;
end;
k1:
=k1+1;
l:
=length(s2);
k2:
=260;
fori:
=ldownto1do
begin
b[k2]:
=ord(s2[i])-48;
k2:
=k2-1;
end;
k2:
=k2+1;
ifk1>k2
thenk:
=k2
elsek:
=k1;
y:
=0;
fori:
=260downtokdo
begin
x:
=a[i]+b[i]+y;
c[i]:
=xmod10;
y:
=xdiv10;
end;
ify<>0
then
begin
k:
=k-1;
c[k]:
=y;
end;
fori:
=kto260dowrite(c[i]);
writeln;
end.
四、优化:
以上的方法的有明显的缺点:
(1)浪费空间:
一个整型变量(-32768~32767)只存放一位(0~9);
(2)浪费时间:
一次加减只处理一位;
针对以上问题,我们做如下优化:
一个数组元素存放四位数;(integer的最大范围是32767,5位的话可能导致出界)将标准数组改为紧缩数组。
第一步的具体方法:
l:
=length(s1);
k1:
=260;
repeat{————有关字符串的知识}
s:
=copy(s1,l-3,4);
val(s,a[k1],code);
k1:
=k1-1;
s1:
=copy(s1,1,l-4);
l:
=l-4;
untill<=0;
k1:
=k1+1;
而因为这个改进,算法要相应改变:
(1)运算时:
不再逢十进位,而是逢万进位(mod10000;div10000);
(2)输出时:
最高位直接输出,其余各位,要判断是否足够4位,不足部分要补0;例如:
1,23,2345这样三段的数,输出时,应该是100232345而不是1232345。
改进后的算法:
programsum;
vars1,s2,s:
string;
a,b,c:
packedarray[1..260]ofinteger;
i,l,k1,k2,code:
integer;
begin
write('inputs1:
');readln(s1);
write('inputs2:
');readln(s2);
l:
=length(s1);
k1:
=260;
repeat{————有关字符串的知识}
s:
=copy(s1,l-3,4);
val(s,a[k1],code);
k1:
=k1-1;
s1:
=copy(s1,1,l-4);
l:
=l-4;
untill<=0;
k1:
=k1+1;
l:
=length(s2);
k2:
=260;
repeat
s:
=copy(s2,l-3,4);
val(s,b[k2],code);
k2:
=k2-1;
s2:
=copy(s2,1,l-4);
l:
=l-4;
untill<=0;
k2:
=k2+1;
ifk1=k1elsek:
=k2;
y:
=0;
fori:
=260downtokdo
begin
x:
=a+b+y;
c:
=xmod10000;
y:
=xdiv10000;
end;
ify<>0thenbegink:
=k-1;c[k]:
=y;end;
write(c[k]);
fori:
=k+1to260do
begin
ifc<1000thenwrite('0');
ifc<100thenwrite('0');
ifc<10thenwrite('0');
write(c);
end;
writeln;
end.
高精度减法
减法:
和高精度加法相比,减法在差为负数时处理的细节更多一点:
当被减数小于减数时,差为负数,差的绝对值是减数减去被减数;在程序实现上用一个变量来存储符号位,用另一个数组存差的绝对值。
2、算法流程:
(1)读入被减数S1,S2(字符串);
(2)置符号位:
判断被减数是否大于减数:
大则将符号位置为空;小则将符号位置为“-”,交换减数与被减数;
(3)被减数与减数处理成数值,放在数组中;
(4)运算:
A、取数;
B、判断是否需要借位;
C、减,将运算结果放到差数组相应位中;
D、判断是否运算完成:
是,转5;不是,转A;
(5)打印结果:
符号位,第1位,循环处理第2到最后一位;
3、细节:
▲如何判断被减数与减数的大小:
字符串知识
(1)首先将两个字符串的位数补成一样(因为字符串的比较是从左边对齐的;两个字符串一样长才能真正地比较出大小):
短的在左边补0
k1:
=length(s1);
k2:
=length(s2);
ifk1>k2thenfori:
=1tok1-k2dos2:
='0'+s2
elsefori:
=1tok2-k1dos1:
='0'+s1;
(2)接着比较大小:
直接比较字符串大小
fh:
='';
ifs1='-';s:
=s1;s1:
=s2;s2:
=s;end;
{————s1存被减数,fh存符号}
▲将字符串处理成数值:
l:
=length(s1);{求出s1的长度,也即s1的位数;有关字符串的知识。
}
k1:
=260;
fori:
=ldownto1do
begin
a[k1]:
=ord(s1)-48;{将字符转成数值}
k1:
=k1-1;
end;
k1:
=k1+1;
▲运算(减法跟加法比较,减法退位处理跟加法进位处理不一样):
a.处理退位;
跟加法一样,在for语句外面先将退位清零,
用被减数再减去退位,
{注意:
由于每一个数位不一定都得向前一位借位,所以这里退位得清零。
例如,234-25,个位需借位,而十位不用}
接着,再判断,当被减数某一位不够减时,则需加上前一位退位过来的数。
{注意:
由于这里采用优化方法,所以退一位,就等于后一位加上10000。
)
最后,再拿一个数组来存储两个减数的差。
jw:
=0;
fori:
=260downtok1do
begin
a:
=a-jw;{此处jw为下一位从I位的借位}
jw:
=0;{此处jw为I位准备向上一位的借位}
ifa begin
jw:
=1;
a:
=a+10000;
end;
c:
=a-b;
end;
▲打印结果:
先找到差的第一个非零数,如果差的所有位数都为零,就直接输出零。
如果不是,就输出符号位和差的第一位。
剩下部分,打印补足零:
因为优化后的高精度减法,是把每四个数位分成一段,而每一段则必须有四个
数,当有一段不足四个数时,就得用"0"补足.(如:
第一位是'1',第二位是'34',第三位是'345',第四位是'8',则应写为'1003403450008').注意:
第一位不用补零,(如:
第一位为'3',则写成'3').
while(c[k]=0)and(k<=260)dok:
=k+1;
ifk>260thenwrite('0')
elsebegin
write(fh,c[k]);{k是差的第1位;}
fori:
=k+1to260do
begin
ifc<1000thenwrite('0');
ifc<100thenwrite('0');
ifc<10thenwrite('0');
write(c);
end;
end;
参考程序:
programZfjianfa;
constn=25;
vars1,s2,s3,s4,s:
string;
a,b,c:
array[1..n]ofinteger;
i,k1,k2,l,code,jw:
integer;
cq:
char;
begin
readln(s1);
readln(s2);
k1:
=length(s1);
k2:
=length(s2);
ifk1>k2thenfori:
=1tok1-k2dos2:
='0'+s2
elsefori:
=1tok2-k1dos1:
='0'+s1;
cq:
='';
ifs1='-';s:
=s1;s1:
=s2;s2:
=s;end;
l:
=length(s1);
k1:
=n;
repeat
s3:
=copy(s1,l-3,4);
val(s3,a[k1],code);
k1:
=k1-1;
delete(s1,l-3,4);
l:
=l-4;
untill<=0;
k1:
=k1+1;
i:
=length(s2);
k2:
=n;
repeat
s4:
=copy(s2,i-3,4);
val(s4,b[k2],code);
k2:
=k2-1;
delete(s2,i-3,4);
i:
=i-4;
untili<=0;
k2:
=k2+1;
jw:
=0;
fori:
=ndowntok1do
begin
a[i]:
=a[i]-jw;
jw:
=0;
ifa[i]
jw:
=1;
a[i]:
=a[i]+10000;
end;
c[i]:
=a[i]-b[i];
end;
while(c[k1]=0)and(k1<=n)do
k1:
=k1+1;
ifk1>nthenwriteln('0')
elsebegin
write(cq,c[k1]);
fori:
=k1+1tondo
begin
ifc[i]<1000thenwrite('0');
ifc[i]<100thenwrite('0');
ifc[i]<10thenwrite('0');
write(c[i]);
end;
end;
writeln;
end.
高精度乘法
高精度乘法基本思想和加法一样。
其基本流程如下:
①读入被乘数s1,乘数s2
②把s1、s2分成4位一段,转成数值存在数组a,b中;记下a,b的长度k1,k2;
③i赋为b中的最低位;
④从b中取出第i位与a相乘,累加到另一数组c中;(注意:
累加时错开的位数应是多少位?
)
⑤i:
=i-1;检测i值:
小于k2则转⑥,否则转④
⑥打印结果
参考程序:
programchengfa;
constn=100;
typear=array[1..n]ofinteger;
vara,b:
ar;k1,k2,k:
integer;
c:
array[1..200]ofinteger;
s1,s2:
string;
procedurefenge(s:
string;vard:
ar;varkk:
integer);{将s分割成四位一组存放在d中,返回的kk值指向d的最高位}
varss:
string;
i,code:
integer;
begin
i:
=length(s);
kk:
=n;
repeat
ss:
=copy(s,i-3,4);
val(ss,d[kk],code);
kk:
=kk-1;
s:
=copy(s,1,i-4);
i:
=i-4;
untili<0;
kk:
=kk+1;
end;
procedureinit;
vari:
integer;
begin
fori:
=1tondobegina:
=0;b:
=0;end;
fori:
=1to2*ndoc:
=0;
write('input2numbers:
');
readln(s1);
readln(s2);
fenge(s1,a,k1);
fenge(s2,b,k2);
end;
procedurejisuan;
vari,j,m:
integer;x,y,z,jw:
longint;
begin
i:
=n;k:
=2*n;
repeat
x:
=b;z:
=0;m:
=k;jw:
=0;
forj:
=ndowntok1do
begin
y:
=a[j];
z:
=c[m];
x:
=x*y+z+jw;
jw:
=xdiv10000;
c[m]:
=xmod10000;
m:
=m-1;
x:
=b;
end;
ifjw<>0thenc[m]:
=jwelsem:
=m+1;
i:
=i-1;
k:
=k-1;
untili k:
=m;
end;
proceduredaying;
vari:
integer;
begin
write(c[k]);
fori:
=k+1to2*ndo
begin
ifc<1000thenwrite('0');
ifc<100thenwrite('0');
ifc<10thenwrite('0');
write(c);
end;
writeln;
end;
begin
init;
jisuan;
daying;
end.
教材“基础编”P87高精乘法参考程序:
programex3_1;
var
a,b,c:
array[0..1000]ofword;
procedureinit;
var
s:
string;
ok,i,j:
integer;
begin
readln(s);
a[0]:
=length(s);
fori:
=1toa[0]do
val(s[a[0]-i+1],a[i],ok);
readln(s);
b[0]:
=length(s);
b[0]:
=length(s);
fori:
=1tob[0]do
val(s[b[0]-i+1],b[i],ok);
end;
procedurehighmul;
vari,j,k:
integer;
begin
c[0]:
=a[0]+b[0];
fori:
=1tob[0]do
forj:
=1toa[0]+1do
begin
inc(c[i+j-1],a[j]*b[i]mod10);
c[i+j]:
=c[i+j]+(a[j]*b[i]div10)+(c[i+j-1]div10);
c[i+j-1]:
=c[i+j-1]mod10;
end;
end;
procedureprint;
vari:
integer;
begin
whilec[c[0]]=0dodec(c[0]);
fori:
=c[0]downto1do
write(c[i]);
writeln;
end;
begin
init;
highmul;
print;
end.