高精度計算加法

1、高精度加法所謂的高精度運算,是指參與運算的數(shù)(加數(shù),減數(shù),因子）范圍大大超出了標(biāo)準(zhǔn)數(shù)據(jù)類型（整型，實型）能表示的范圍的運算。例如，求兩個 200 位的數(shù)的和。這時，就要用到高精度算法了。在這里，先高精度加法。高精度運算主要解決以下三個問題：基本方法（如果你已經(jīng)會了，那就看看優(yōu)化后的方法）1、加數(shù)、減數(shù)、運算結(jié)果的輸入和運算因子超出了整型、實型能表示的范圍，肯定不能直接用一個數(shù)的形式來表示。在 Pascal中，能表示多個數(shù)的數(shù)據(jù)類型有兩種：數(shù)組和字符串。（1）數(shù)組：每個數(shù)組元素數(shù)組元素；1 位（在優(yōu)化時，這里是一個重點?。卸嗌傥痪托枰嗌賯€用數(shù)組表示數(shù)的優(yōu)點：每一位都是數(shù)的形式，可以直接加減

2、；運算時非常方便用數(shù)組表示數(shù)的缺點：數(shù)組不能直接輸入；輸入時每兩位數(shù)之間必須有分隔符，不符合數(shù)值的輸入；（2）字符串：字符串的最大長度是 255，可以表示 255 位。用字符串表示數(shù)的優(yōu)點：能直接輸入輸出，輸入時，每兩位數(shù)之間不必分隔符，符合數(shù)值的輸入；用字符串表示數(shù)的缺點：字符串中的每一位是一個字符，不能直接進行運算，必須先將它轉(zhuǎn)化為數(shù)值再進行運算；運算時非常不方便；（3）因此，綜合以上所述，對上面兩種數(shù)據(jù)結(jié)構(gòu)取長補短：用字符串讀入數(shù)據(jù)，用數(shù)組數(shù)據(jù)：var s1,s2:string;a,b,c:array 1.260 ofeger;i,l,k1,k2:begineger;write(inpu

3、t s1:);readln(s1);write(input s2:);readln(s2);讀入兩個數(shù) s1，s2，都是字符串類型l:=length(s1);求出 s1 的長度，也即 s1 的位數(shù)；有關(guān)字符串的知識。 k1:=260;for i:=l downto 1 do beginak1:=ord(s1i)-48;將字符轉(zhuǎn)成數(shù)值 k1:=k1-1;end; k1:=k1+1;以上將 s1 中的字符一位一位地轉(zhuǎn)成數(shù)值并存在數(shù)組 a 中；低位在后（從第260 位開始），（每存完一位，k1 減 1）對 s2 的轉(zhuǎn)化過程和上面一模一樣。2、運算過程在往下看之前，大家先列豎式計算 35+86。注意：

4、（1）運算順序：兩個數(shù)靠右對齊；從低位向運算；先計算低位再計算；運算規(guī)則：同一位的兩個數(shù)相加再加上從低位來的進位，成為該位的和；這個和去掉向的進位就成為該位的值；如上例：3+8+1=12，向前一位進 1，本位的值是 2；可借助 MOD、DIV 運算完成這一步；最后一位的進位：如果完成兩個數(shù)的相加后，進位位值不為 0，則應(yīng)添加一位；如果兩個加數(shù)位數(shù)不一樣多，則按位數(shù)多的一個進行計算；if k1k2 then k:=k1 else k:=k2; y:=0;for i:=260 downto k do beginx:=ai+bi+y; ci:=x mod 10;y:=x div 10;end;if

5、y0 then begin k:=k-1;ck:=y; 3、結(jié)果的輸出（這也是優(yōu)化的一個重點） 按運算結(jié)果的實際位數(shù)輸出for i:=k to 260 do write(ci);end;wrin;4、例子：求兩個數(shù)的加法 program sum;var s,s1,s2:string;a,b,c:array 1.260 ofeger;i,l,k1,k2:begineger;write(input s1:);readln(s1);write(input s2:);readln(s2); l:=length(s1);k1:=260;for i:=l downto 1 do beginak1:=ord

6、(s1i)-48; k1:=k1-1;end; k1:=k1+1;l:=length(s2); k2:=260;for i:=l downto 1 do beginbk2:=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 beginx:=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);wrin;end

7、.優(yōu)化：以上的方法的有明顯的缺點：（1）浪費空間：一個整型變量（-3276832767）只存放一位（09）；（2）浪費時間：一次加減只處理一位；針對以上問題，做如下優(yōu)化：一個數(shù)組元素存放四位數(shù)；（eger 的最大范圍是 32767，5 位的話可能導(dǎo)致出界）。具體方法：l:=length(s1); k1:=260;repeat 有關(guān)字符串的知識 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;而因為這個改進，算法要相應(yīng)改變：（1）運算時：不再逢十進位，而是逢萬進位

8、（mod 10000; div 10000);（2）輸出時：最直接輸出，其余各位，要判斷是否足夠 4 位，部分要補 0；例如：1，23，2345 這樣三段的數(shù)，輸出時，應(yīng)該是 100232345 而不是 1234567。改進后的算法：program sum;var s1,s2:string;a,b,c:array 1.260 ofeger;i,l,k1,k2,code:eger;beginwrite(input s1:);readln(s1);write(input s2:);readln(s2); l:=length(s1);k1:=260;repeat 有關(guān)字符串的知識 s:=copy(s

9、1,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;repeats:=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 beginx:=ai+bi+y; ci:=x mod 10000;y:=x div 10000; end;if y0 then begin k:=k