高精度加法
高精度加法
简介
高精度加法是信息学的一种重要算法。这种算法使用多个存储单位进行计算,因此它的计算范围超过一般使用一个存储单位的算法。也是一些信息学竞赛的常考题目。
基本算法
以358934760892734899+38960302975237462为例:
1、计算结果的位数
358934760892734899共18位
38960302975237462 共17位
故结果不会超过19位。
2、将要计算的数字分割成多段,按照顺序排列(这里以0-32767作为每一存储单位存储的数的限制):
35 8934 7608 9273 4899
3 8960 3029 7523 7462(为提高空间利用效率,可以一个存储单位存储多位数。)
3、将两数相加。
35 8934 7608 9273 4899
3 8960 3029 7523 7462
和(不进位) 38 17894 10637 16796 12361
和(进位后) 39 7895 0638 6797 23614、输出结果。
从高位到低位依次输出。除最高位以外,其他低位上不足4位的要在前面补上0。
pascal程序
var
a,b,c:array[1..201] of 0..9;
n:string;
lena,lenb,lenc,i,x:integer;
begin
write(''Input augend:'');
readln(n);
lena:=length(n);
for i:=1 to lena do a[lena-i+1]:=ord(n)-ord(''0'');{加数放入a数组}
write(''Input addend:'');
readln(n);
lenb:=length(n);
for i:=1 to lenb do b[lenb-i+1]:=ord(n)-ord(''0'');{被加数放入b数组}
i:=1;
while (i<=lena) or(i<=lenb) do
begin
x := a + b + x div 10; {两数相加,然后加前次进位}
c := x mod 10; {保存第i位的值}
i := i + 1
end;
if x>=10 {处理最高进位}
then
begin
lenc:=i;
c:=1
end
else lenc:=i-1;
for i:=lenc downto 1 do write(c);
writeln {输出结果}
end.