NOIP高精度讲解

《NOIP高精度讲解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、高精度加法所谓的高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了。在这里，我们先讨论高精度加法。高精度运算主要解决以下三个问题：基本方法（如果你已经会了，那就看看优化后的方法）1、加数、减数、运算结果的输入和存储运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pascal中，能表示多个数的数据类型有两种：数组和字符串。（1）数组：每个数组元素存储1位（在优化时，这里是一个

2、重点！），有多少位就需要多少个数组元素；用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；（2）字符串：字符串的最大长度是255，可以表示255位。用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；用字符串表示数的缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便；（3）因此，综合以上所述，对上面两种数据结构取长补短：

3、用字符串读入数据，用数组存储数据：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:=ldownt

4、o1do    begin        a[k1]:=ord(s1[i])-48;{将字符转成数值}        k1:=k1-1;    end;    k1:=k1+1;    {————以上将s1中的字符一位一位地转成数值并存在数组a中；低位在后（从第260位开始），高位在前（每存完一位，k1减1）}对s2的转化过程和上面一模一样。2、运算过程在往下看之前，大家先列竖式计算35+86。注意的问题：（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；（2）运算规则：同一位的两个数相加再加

5、上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步；（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；（4）如果两个加数位数不一样多，则按位数多的一个进行计算；    ifk1>k2thenk:=k1elsek:=k2;    y:=0;    fori:=260downtokdo    begin        x:=a[i]+b[i]+y;        c[i]:=xmod10

6、;        y:=xdiv10;    end;    ify<>0thenbegink:=k-1;c[k]:=y;end;3、结果的输出（这也是优化的一个重点）按运算结果的实际位数输出fori:=kto260dowrite(c[i]);writeln;4、例子：求两个数的加法programsum;vars,s1,s2:string;    a,b,c:array[1..260]ofinteger;    i,l,k1,k2:integer;begin    write('inputs1:');readln(

7、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;      

8、  k2:=k2-1;    end;    k2:=k2+1;   ifk1>k2thenk:=k2elsek:=k1;    y:=0;    fori:=260downtokdo    begin        x:=a[i]+b[i]+y;        c[i]:=xmod10;        y:=xdiv10;    end;   ify<>0