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