精华区文章阅读

发信人: zjliu (fly), 信区: Algorithm
标  题: 高精度加法
发信站: 哈工大紫丁香 (Sat Jul  6 18:28:50 2002) , 转信

发信人: fdchosen (紫星), 信区: Algorithm
标  题: 高精度加法
发信站: 日月光华 (Thu Jul  4 19:36:43 2002)

高精度加法

------------------------------------------------------------------------------

--

所谓的高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类

型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高

精度算法了。在这里，我们先讨论高精度加法。高精度运算主要解决以下三个问题：

基本方法

1、加数、减数、运算结果的输入和存储
运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pasc

al中，能表示多个数的数据类型有两种：数组和字符串。
（1）数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多

少个数组元素；
用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便
用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数

值的输入习惯；

（2）字符串：字符串的最大长度是255，可以表示255位。
用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值

的输入习惯；
用字符串表示数的缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它

转化为数值再进行运算；运算时非常不方便；

（3）因此，综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数组存

储数据：
var s1,s2:string;
    a,b,c:array [1..260] of integer;
    i,l,k1,k2:integer;
begin
     write('input s1:');readln(s1);
     write('input s2:');readln(s2);
     {————读入两个数s1，s2，都是字符串类型}
     l:=length(s1);{求出s1的长度，也即s1的位数；有关字符串的知识。}
     k1:=260;
     for i:=l downto 1 do
     begin
          a[k1]:=ord(s1[i])-48;{将字符转成数值}
          k1:=k1-1;
     end;
     k1:=k1+1;
     {————以上将s1中的字符一位一位地转成数值并存在数组a中；低位在后（从第2

60位开始），高位在前（每存完一位，k1减1）}

对s2的转化过程和上面一模一样。

2、运算过程
在往下看之前，大家先列竖式计算35+86。
注意的问题：
（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；
（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉

向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助

MOD、DIV运算完成这一步；
（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；
（4）如果两个加数位数不一样多，则按位数多的一个进行计算；
     if k1>k2 then k:=k1 else k:=k2;
     y:=0;
     for i:=260 downto k do
     begin
         x:=a[i]+b[i]+y;
         c[i]:=x mod 10;
         y:=x div 10;
     end;
     if y<>0 then begin k:=k-1;c[k]:=y; end;

3、结果的输出（这也是优化的一个重点）
按运算结果的实际位数输出
for i:=k to 260 do write(c[i]);
writeln;

4、例子：求两个数的加法
program sum;
var s,s1,s2:string;
    a,b,c:array [1..260] of integer;
    i,l,k1,k2:integer;
begin
     write('input s1:');readln(s1);
     write('input s2:');readln(s2);
         l:=length(s1);
     k1:=260;
     for i:=l downto 1 do
     begin
          a[k1]:=ord(s1[i])-48;
          k1:=k1-1;
     end;
     k1:=k1+1;

    l:=length(s2);
     k2:=260;
     for i:=l downto 1 do
     begin
          b[k2]:=ord(s2[i])-48;
          k2:=k2-1;
     end;
     k2:=k2+1;

    if k1>k2 then k:=k2 else k:=k1;
     y:=0;
     for i:=260 downto k do
     begin
         x:=a[i]+b[i]+y;
         c[i]:=x mod 10;
         y:=x div 10;
     end;
    if y<>0 then begin k:=k-1;c[k]:=y;
end;
     for i:=k to 260 do write(c[i]);
     writeln;
end.

优化：

以上的方法的有明显的缺点：
（1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；
（2）浪费时间：一次加减只处理一位；

针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是327

67，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;
     until l<=0;
     k1:=k1+1;
而因为这个改进，算法要相应改变：
（1）运算时：不再逢十进位，而是逢万进位（mod 10000; div 10000);
（2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：

1，23，2345这样三段的数，输出时，应该是100232345而不是1234567。

改进后的算法：
program sum;
var s1,s2:string;
    a,b,c:array [1..260] of integer;
    i,l,k1,k2,code:integer;

begin
     write('input s1:');readln(s1);
     write('input s2:');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;
     until l<=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;
     until l<=0;
     k2:=k2+1;

    if k1<k2 then k:=k1 else k:=k2;
     y:=0;
     for i:=260 downto k do
     begin
         x:=a[i]+b[i]+y;
         c[i]:=x mod 10000;
         y:=x div 10000;
     end;
      if y<>0 then begin k:=k-1;c[k]:=y;end;

   write(c[k]);
    for i:=k+1 to 260 do
    begin
    ----if c[i]<1000 then write('0');
    ----if c[i]<100 then write('0');
    ----if c[i]<10 then write('0');
    ----write(c[i]);
     end;
     writeln;
end.

--

※ 来源:．日月光华 http://bbs.fudan.edu.cn [FROM: 10.11.12.201]

--

※ 来源:．哈工大紫丁香 http://bbs.hit.edu.cn [FROM: 202.118.229.86]

Algorithm 版 (精华区)