高精度計(jì)算加法

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

2、；運(yùn)算時(shí)非常方便用數(shù)組表示數(shù)的缺點(diǎn)：數(shù)組不能直接輸入；輸入時(shí)每兩位數(shù)之間必須有分隔符，不符合數(shù)值的輸入；（2）字符串：字符串的最大長度是 255，可以表示 255 位。用字符串表示數(shù)的優(yōu)點(diǎn)：能直接輸入輸出，輸入時(shí)，每兩位數(shù)之間不必分隔符，符合數(shù)值的輸入；用字符串表示數(shù)的缺點(diǎn)：字符串中的每一位是一個(gè)字符，不能直接進(jìn)行運(yùn)算，必須先將它轉(zhuǎn)化為數(shù)值再進(jìn)行運(yùn)算；運(yùn)算時(shí)非常不方便；（3）因此，綜合以上所述，對上面兩種數(shù)據(jù)結(jié)構(gòu)取長補(bǔ)短：用字符串讀入數(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);讀入兩個(gè)數(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、運(yùn)算過程在往下看之前，大家先列豎式計(jì)算 35+86。注意：

4、（1）運(yùn)算順序：兩個(gè)數(shù)靠右對齊；從低位向運(yùn)算；先計(jì)算低位再計(jì)算；運(yùn)算規(guī)則：同一位的兩個(gè)數(shù)相加再加上從低位來的進(jìn)位，成為該位的和；這個(gè)和去掉向的進(jìn)位就成為該位的值；如上例：3+8+1=12，向前一位進(jìn) 1，本位的值是 2；可借助 MOD、DIV 運(yùn)算完成這一步；最后一位的進(jìn)位：如果完成兩個(gè)數(shù)的相加后，進(jìn)位位值不為 0，則應(yīng)添加一位；如果兩個(gè)加數(shù)位數(shù)不一樣多，則按位數(shù)多的一個(gè)進(jìn)行計(jì)算；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)化的一個(gè)重點(diǎn)） 按運(yùn)算結(jié)果的實(shí)際位數(shù)輸出for i:=k to 260 do write(ci);end;wrin;4、例子：求兩個(gè)數(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)化：以上的方法的有明顯的缺點(diǎn)：（1）浪費(fèi)空間：一個(gè)整型變量（-3276832767）只存放一位（09）；（2）浪費(fèi)時(shí)間：一次加減只處理一位；針對以上問題，做如下優(yōu)化：一個(gè)數(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àn)檫@個(gè)改進(jìn)，算法要相應(yīng)改變：（1）運(yùn)算時(shí)：不再逢十進(jìn)位，而是逢萬進(jìn)位

8、（mod 10000; div 10000);（2）輸出時(shí)：最直接輸出，其余各位，要判斷是否足夠 4 位，部分要補(bǔ) 0；例如：1，23，2345 這樣三段的數(shù)，輸出時(shí)，應(yīng)該是 100232345 而不是 1234567。改進(jìn)后的算法：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