高精度計(jì)算48916

1、高精度運(yùn)算所謂的高精度運(yùn)算是指參與運(yùn)算的數(shù)(加數(shù)減數(shù)因子……）范圍大大超出了標(biāo)準(zhǔn)數(shù)據(jù)類型（整型，實(shí)型）能表示的范圍的運(yùn)算。例如，求兩個(gè)200位的數(shù)的和。這時(shí)，就要用到高精度算法了。在這里，我們先討論高精度加法。高精度運(yùn)算主要解決以下三個(gè)問題：一、加數(shù)、減數(shù)、運(yùn)算結(jié)果的輸入和存儲運(yùn)算因子超出了整型、實(shí)型能表示的范圍，肯定不能直接用一個(gè)數(shù)的形式來表示。在Pal中，能表示多個(gè)數(shù)的數(shù)據(jù)類型有兩種：數(shù)組和字符串。數(shù)組：每個(gè)數(shù)組元素存儲1位（在優(yōu)化

2、時(shí)，這里是一個(gè)重點(diǎn)?。?，有多少位就需要多少個(gè)數(shù)組元素；用數(shù)組表示數(shù)的優(yōu)點(diǎn)：每一位都是數(shù)的形式，可以直接加減；運(yùn)算時(shí)非常方便。用數(shù)組表示數(shù)的缺點(diǎn)：數(shù)組不能直接輸入；輸入時(shí)每兩位數(shù)之間必須有分隔符，不符合數(shù)值的輸入習(xí)慣；字符串：字符串的最大長度是255，可以表示255位。用字符串表示數(shù)的優(yōu)點(diǎn)：能直接輸入輸出，輸入時(shí)，每兩位數(shù)之間不必分隔符，符合數(shù)值的輸入習(xí)慣；用字符串表示數(shù)的缺點(diǎn)：字符串中的每一位是一個(gè)字符，不能直接進(jìn)行運(yùn)算，必須先將它轉(zhuǎn)化

3、為數(shù)值再進(jìn)行運(yùn)算；運(yùn)算時(shí)非常不方便；綜合以上所述，對上面兩種數(shù)據(jù)結(jié)構(gòu)取長補(bǔ)短：用字符串讀入數(shù)據(jù)，用數(shù)組存儲數(shù)據(jù)：vars1s2:stringabc:array[1..260]ofintegerilk1k2:integerbeginwrite(inputs1:)readln(s1)write(inputs2:)readln(s2)————讀入兩個(gè)數(shù)s1，s2，都是字符串類型l:=length(s1)求出s1的長度，也即s1的位數(shù)；有關(guān)字符

4、串的知識。k1:=260fi:=ldownto1dobegina[k1]:=d(s1[i])48將字符轉(zhuǎn)成數(shù)值k1:=k11endk1:=k11————以上將s1中的字符一位一位地轉(zhuǎn)成數(shù)值并存在數(shù)組a中；低位在后（從第260位開始），高位在前（每存完一位，k1減1），完后，k1指向最高位對s2的轉(zhuǎn)化過程和上面一模一樣。二、運(yùn)算過程在往下看之前，大家先列豎式計(jì)算3586。注意的問題：（1）運(yùn)算順序：兩個(gè)數(shù)靠右對齊；從低位向高位運(yùn)算；先計(jì)算

5、低位再計(jì)算高位；（2）運(yùn)算規(guī)則：同一位的兩個(gè)數(shù)相加再加上從低位來的進(jìn)位，成為該位的和；這個(gè)和去掉向高位的進(jìn)位就成為該位的值；如上例：381=12，向前一位進(jìn)1，本位的值是2；可借助MOD、DIV運(yùn)算完成這一步；（3）最后一位的進(jìn)位：如果完成兩個(gè)數(shù)的相加后，進(jìn)位位值不為0，則應(yīng)添加一位；y:=xdiv10endify0thenbegink:=k1c[k]:=yendfi:=kto260dowrite(c[i])writelnend.四、優(yōu)

6、化：以上的方法的有明顯的缺點(diǎn)：（1）浪費(fèi)空間：一個(gè)整型變量（32768~32767）只存放一位（0~9）；（2）浪費(fèi)時(shí)間：一次加減只處理一位；針對以上問題，我們做如下優(yōu)化：一個(gè)數(shù)組元素存放四位數(shù)；（integer的最大范圍是32767，5位的話可能導(dǎo)致出界）。具體方法：l:=length(s1)k1:=260repeat————有關(guān)字符串的知識s:=copy(s1l34)val(sa[k1]code)k1:=k11s1:=copy(s1

7、1l4)l:=l4untill=0k1:=k11而因?yàn)檫@個(gè)改進(jìn)，算法要相應(yīng)改變：（1）運(yùn)算時(shí)：不再逢十進(jìn)位，而是逢萬進(jìn)位（mod10000div10000)（2）輸出時(shí)：最高位直接輸出，其余各位，要判斷是否足夠4位，不足部分要補(bǔ)0；例如：1，23，2345這樣三段的數(shù)，輸出時(shí)，應(yīng)該是100232345而不是1234567。改進(jìn)后的算法：programsumvars1s2s:stringabc:array[1..260]ofinteger