NOIP高精度讲解.doc

高精度加法所谓的高精度运算,是指参与运算的数(加数,减数,因子）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了。在这里，我们先讨论高精度加法。高精度运算主要解决以下三个问题：基本方法（如果你已经会了，那就看看优化后的方法）1、加数、减数、运算结果的输入和存储运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pascal中，能表示多个数的数据类型有两种：数组和字符串。（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 ak1:=ord(s1i)-48;将字符转成数值 k1:=k1-1; end; k1:=k1+1; 以上将s1中的字符一位一位地转成数值并存在数组a中；低位在后（从第260位开始），高位在前（每存完一位，k1减1） 对s2的转化过程和上面一模一样。2、运算过程在往下看之前，大家先列竖式计算35+86。注意的问题：（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步；（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；（4）如果两个加数位数不一样多，则按位数多的一个进行计算； if k1k2 then k:=k1 else k:=k2; y:=0; for i:=260 downto k do begin x:=ai+bi+y; ci:=x mod 10; y:=x div 10; end; if y0 then begin k:=k-1;ck:=y; end;3、结果的输出（这也是优化的一个重点）按运算结果的实际位数输出for i:=k to 260 do write(ci);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 ak1:=ord(s1i)-48; k1:=k1-1; end; k1:=k1+1;l:=length(s2); k2:=260; for i:=l downto 1 do begin bk2:=ord(s2i)-48; k2:=k2-1; end; k2:=k2+1; if k1k2 then k:=k2 else k:=k1; y:=0; for i:=260 downto k do begin x:=ai+bi+y; ci:=x mod 10; y:=x div 10; end; if y0 then begin k:=k-1;ck:=y; end; for i:=k to 260 do write(ci); writeln; end. 优化：以上的方法的有明显的缺点：（1）浪费空间：一个整型变量（-3276832767）只存放一位（09）；（2）浪费时间：一次加减只处理一位；针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是32767，5位的话可能导致出界）。具体方法：l:=length(s1); k1:=260; repeat有关字符串的知识 s:=copy(s1,l-3,4); val(s,ak1,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,ak1,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,bk2,code); k2:=k2-1; s2:=copy(s2,1,l-4); l:=l-4; until l=0; k2:=k2+1; if k1k2 then k:=k1 else k:=k2; y:=0; for i:=260 downto k do begin x:=ai+bi+y; ci:=x mod 10000; y:=x div 10000; end; if y0 then begin k:=k-1;ck:=y;end; write(ck);for i:=k+1 to 260 dobegin -if ci1000 then write(0);-if ci100 then write(0);-if cik2 then k:=k2 else k:=k1;) 处理进位(jw): 注意:89+17,最终答案为106,而此时,k的位置在0,而不在1,则写成06,这时, 就得用if语句判断. (if jw0 then begin ) k:=k-1; ck:=jw; end; 这样,最终答案才是106. 4)打印补足零: 因为优化后的高精度加法,是把每四个数位分成一段,而每一段则必须有四个数,当有一段不足四个数时,就得用0补足. (如:第一位是1,第二位是34,第三位是345,第四位是8, 则应写为1003403450008)注意:第一位不用补零,(如:第一位为3,则写成3).高精度减法1、和高精度加法相比，减法在差为负数时处理的细节更多一点：当被减数小于减数时，差为负数，差的绝对值是减数减去被减数；在程序实现上用一个变量来存储符号位，用另一个数组存差的绝对值。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); if k1k2 then for i:=1 to k1-k2 do s2:=0+s2 else for i:=1 to k2-k1 do s1:=0+s1; （2）接着比较大小：直接比较字符串大小 fh:=; if s1s2 then begin fh:=-;s:=s1; s1:=s2; s2:=s; end; s1存被减数，符号存符号将字符串处理成数值：l:=length(s1);求出s1的长度，也即s1的位数；有关字符串的知识。 k1:=260; for i:=l downto 1 do begin ak1:=ord(s1i)-48;将字符转成数值 k1:=k1-1; end; k1:=k1+1; 打印结果：例：差：第一位是12，第二位是234，第三位是1234，最后一位：3。它的实际数值是12023412340003。从上例可以看出：打印时，从第二位开始，因为每一段都代表4位，不足4位的要补足0。write(fh,ck);k是差的第1位；for i:=k+1 to 260 dobegin if ci1000 then write(0);if ci100 then write(0);if cik2 then for i:=1 to k1-k2 do s2:=0+s2 else for i:=1 to k2+k1 do s1:=0+s1; fh:= ; if s1=25） 二.由于不为零的一位是在最大一位（k1）的左边， 所以，最后得用一个语句来赋值。（k1：=k1+1） 参考程序： while (ck1=0) and (k125 then write(0); else begin write(fh,ck1); for i:=k1+1 to 25 do beginif ci1000 then write(0);if ci100 then write(0);if ci10 then write(0);write(ci);end; end;程序完成。高精度乘法和阶乘一、高精度乘法基本思想和加法一样。其基本流程如下：读入被乘数s1，乘数s2把s1、s2分成4位一段，转成数值存在数组a,b中；记下a,b的长度k1,k2；i赋为b中的最低位；从b中取出第i位与a相乘，累加到另一数组c中；（注意：累加时错开的位数应是多少位？）i:=i-1；检测i值：小于k2则转,否则转打印结果例：程序program chengfa;const n=100;type ar=array 1.n of integer;var a,b:ar; k1,k2,k:integer; c:array 1.200 of integer; s1,s2:string;procedure fenge(s:string;var d:ar; var kk:integer);var ss:string; i,code:integer;begin i:=length(s); kk:=n; repeat ss:=copy(s,i-3,4); val(ss,dkk,code); kk:=kk-1; s:=copy(s,1,i-4); i:=i-4; until i0; kk:=kk+1;end;procedure daying;var i:integer;begin write(ck); for i:=k+1 to 2*n do begin if ci1000 then write(0); if ci100 then write(0); if ci10 then write(0); write(ci); end; writeln;end;begin init; jisuan; daying;end.二、求N！当N稍微大一点时结果就很大了（如n=10时N!=3628800；n=20时N!=2432902008176640000)；因此，求阶乘通常都要用到高精度算法。基本过程和乘法一样，只是多了控制乘法次数的一层循环。 高精度乘法（字符串相乘）一，优缺点评析； 同普通乘法比较，这里容纳量多了很多；唯一美中不足就是程序比较复杂，不如普通乘法容易理解。二，算法流程； 1）读入两个乘数s1，s2（字符串）； 2）将两个乘数转换成数值；参考程序： l:=length(s1); k1:=n; repeat s3:=copy(s1,l-3,4); val(s3,ak1,cq); k1:=k1-1; delete(s1,l-3,4); l:=l-4; until l=0; k1:=k1+1; l:=length(s2); k2:=n; repeat s4:=copy(s2,l-3,4); val(s4,bk2,cq); k2:=k2-1; delete(s2,l-3,4); l:=l-4; until l=0; k2:=k2+1; 3）整理积的最后一位以及乘数的最后一位；（这里是重点，不可缺少）参考程序： jin:=0; ch:=n; 4）1，进行两个乘数的初步相乘； 注意：这里要着重处理进位； 2，把两个乘数每个数位相乘的积相加； 注意：这里进位还要再次清零； 参考程序： for i:=n downto k2 do begin y:=bi; jw:=0; for h:=n downto k1 do begin x:=ah; x:=x*y+jw; ch:=x mod 10000; jw:=x div 10000; end; if jw0 then begin k:=k1-1; ck:=jw; end else k:=k1; jw:=0; p:=n; for o:=i downto 1 do begin x:=cp+do; p:=p-1; v:=x+jw; do:=v mod 10000; jw:=v div 10000; end; end; 5）1，因为上面是从i downto 1 do 然而并不知道1是哪一位， 所以，这里得拿一个字母来赋值1； 2.打印结果； 注意：最后得记得输出积。参考程序： e:=1; while (de=0) and (en then writeln(0) else begin write(de); for q:=e+1 to n do begin if dq 1000 then write(0); if dq100 then write(0); if dq10 then write(0); write(dq); end;end; writeln;end.一、优缺点分析 数组相乘的高精度乘法与普通的高精度乘法相比较，前者所能容纳的数位比后者多得多，但它的程序也比后者复杂。二、算法流程1）读入两个字符串s1，s2；procedure init;var i:integer;begin for i:=1 to n do begin ai:=0; bi:=0; end; for i:=1 to 2*n do ci:=0; writeln(input 2 numbers:); readln(s1); readln(s2); fg(s1,a,k1); fg(s2,b,k2);end;2）将这两个字符串转换为数值；procedure fg(s:string;var d:ar; var kk:integer);var ss:string; l,code:integer;begin l:=length(s); kk:=n; repeat ss:=copy(s,l-3,4); val(ss,dkk,code); kk:=kk-1; s:=copy(s,1,l-4); l:=l-4; until l0; kk:=kk+1;end;3）把两个数组a，b相乘，把乘积的后四位放进数组c里面，并把进位（即乘积除去后四位的其他部分）放在变量jw里面，接着把数组b截去后面四位，再与a相乘，然后把乘积与进位jw相加，放进数组c里面，重复上面的过程，直到乘完为止；procedure jisuan;var i,j,m:integer; x,y,z,jw:longint;begin i:=n; k:=2*n; repeat x:=bi; z:=0; m:=k; jw:=0; for j:=n downto k1 do begin y:=aj; z:=cm; x:=x*y+z+jw; jw:=x div 10000; cm:=x mod 10000;