高精度運算--Pascal語言

1、高 精 度 運 算為什么要進行高精度運算？為什么要進行高精度運算？PASCAL語言中整數(shù)： 最小的為byte型，范圍：0.255，占用一個字節(jié)； integer類型，范圍：-32768.32767，占用二個字節(jié)； longint類型，范圍：-2147483648. 2147483647，四個字節(jié)實數(shù)： real類型，達到10的38次方，占用六個字節(jié)； doubel型，達到10的308次方，占用8個字節(jié)； extended型，達到10的4932次方，占用10個字節(jié)。很多情況下仍然不夠用，只能采用高精度運算。很多情況下仍然不夠用，只能采用高精度運算。兩個大整數(shù)之間的四則運算兩個大整數(shù)之間的四則運算

2、例：例：9999999999+8888888888這兩個整數(shù)都是普通類型無法讀入的，這兩個整數(shù)都是普通類型無法讀入的，也不能用普通的整數(shù)數(shù)組直接讀入。也不能用普通的整數(shù)數(shù)組直接讀入。一般采用一般采用字符串字符串類型讀入，然后轉(zhuǎn)化類型讀入，然后轉(zhuǎn)化為整數(shù)數(shù)組，最后用數(shù)組模擬的方法運算。為整數(shù)數(shù)組，最后用數(shù)組模擬的方法運算。本本節(jié)節(jié)主主要要內(nèi)內(nèi)容容高精度算法的基本思想-分割、模擬：將無法直接處理的大整數(shù)，分割分割成若干個可以直接處理的小整數(shù)段，將原問題轉(zhuǎn)化為對小整數(shù)段的處理。 例如：3628800 這個數(shù)字范圍很大，但可以分割、轉(zhuǎn)化可以分割、轉(zhuǎn)化為數(shù)組進行處理和輸出。為數(shù)組進行處理和輸出。S7S6

3、S5S4S3S2S1在處理之前，首先要解決輸入的問題，對于范圍特別大的數(shù)字一般通過字符串進行輸入。字符串字符串 string字符串可以按照下標直接引用，如字符串字符串可以按照下標直接引用，如字符串S: “abcde888edcba”，S5即字符即字符“e”。這種引用方法。這種引用方法和數(shù)組是一樣的，所以可以把字符串看成一種特殊的和數(shù)組是一樣的，所以可以把字符串看成一種特殊的字符型數(shù)組。字符型數(shù)組。但是，字符串有一些字符數(shù)組所沒有的方便之處。但是，字符串有一些字符數(shù)組所沒有的方便之處。其中，最方便的地方是編譯系統(tǒng)通常都為字符串內(nèi)置了其中，最方便的地方是編譯系統(tǒng)通常都為字符串內(nèi)置了許多常用的函數(shù)（

4、對普通的字符數(shù)組則沒有），這對編許多常用的函數(shù)（對普通的字符數(shù)組則沒有），這對編寫程序有很大好處。而且，寫程序有很大好處。而且，PASCAL語言內(nèi)置的字符串語言內(nèi)置的字符串函數(shù)比函數(shù)比C語言要多一些。語言要多一些。一、字符串的定義一、字符串的定義 關(guān)鍵字關(guān)鍵字 String例例: a, b, c: string; 定義了三個字符串，默認長度為定義了三個字符串，默認長度為255；例例: d : string100; 定義了一個長度為定義了一個長度為100的字符串；的字符串；二、字符串的輸出二、字符串的輸出 不需要循環(huán)不需要循環(huán)例例: Write (a); 輸出整個字符串輸出整個字符串a(chǎn) Writ

5、e (a2); 輸出字符串的第輸出字符串的第2個字符個字符 三、字符串的常用函數(shù)三、字符串的常用函數(shù)注：注： 這些系統(tǒng)的內(nèi)部函數(shù)僅對字符串這些系統(tǒng)的內(nèi)部函數(shù)僅對字符串string才有效，才有效，對字符數(shù)組和整數(shù)數(shù)組均無效。對字符數(shù)組和整數(shù)數(shù)組均無效。（1） 求串長函數(shù)求串長函數(shù) length(s) s為為string類型，返回類型，返回s串的實際長度值串的實際長度值(整數(shù)整數(shù))。（2） 求子串函數(shù)求子串函數(shù) copy(s, i, L) s為為string類型，類型，i和和L為整數(shù)類型，返回類型為為整數(shù)類型，返回類型為string。 返回返回s串中，從第串中，從第i個字符開始，長度為個字符開始，

6、長度為L的子串。的子串。（3） 搜索子串位置函數(shù)搜索子串位置函數(shù) pos(s1, s2) s1s1和和s2s2均為均為stringstring類型，返回類型為整數(shù)。類型，返回類型為整數(shù)。 s1s1若是若是s2s2的一個子串，則返回的一個子串，則返回s1s1中第一個字符在中第一個字符在s2s2中中 的位置；若的位置；若s1s1若不是若不是s2s2的一個子串，則返回的一個子串，則返回0 0。常用！常用！ASCII表表四、將字符串轉(zhuǎn)化為整數(shù)數(shù)組四、將字符串轉(zhuǎn)化為整數(shù)數(shù)組注：僅限于注：僅限于“123456”這樣的串；這樣的串；類似類似“abcde”的純字符串不適合轉(zhuǎn)化的純字符串不適合轉(zhuǎn)化假設(shè)假設(shè)s為一

7、個串，如為一個串，如s=1234567890；K:=length(s);For i:=1 to k do datak-i+1 := ord(si) ord(0) ;函數(shù)函數(shù)ord求的是字符在求的是字符在ASCII表的位置，該表的位置，該位置減去字符位置減去字符0的位置，得到位置差。的位置，得到位置差。位置差就是該數(shù)字。位置差就是該數(shù)字。數(shù)組數(shù)組a a數(shù)組數(shù)組b b相加得相加得數(shù)組數(shù)組c c這時直接輸出會得到1717171717，顯然不對，因此要逐位處理一下。數(shù)組數(shù)組c c商 往前進：ci+1:=ci+1 + ci div 10 ;余數(shù) 留下：ci:=ci mod 10 ;注意：上面兩步的順序不

8、能顛倒！數(shù)組數(shù)組c c數(shù)組數(shù)組c c數(shù)組數(shù)組c c數(shù)組數(shù)組c c逐位處理完畢后，就可以倒序輸出了，但是為了避免輸出左邊沒用的零，要先確定第一個有效的數(shù)字在什么位置。這個可以用While循環(huán)從高到低掃描，遇到第一個非零的數(shù)字，記錄它的位置。 /尋找最高位尋找最高位 避免輸出避免輸出0 Top:=Max; While ctop=0 do top:=top-1;0000188887Topmax0000188887TopTop-1兩個大整數(shù)的加法運算兩個大整數(shù)的加法運算const max=100;Var s1,s2: string; a,b,c: array1.max of integer; i,to

9、p,k1,k2:integer;begin readln(s1); k1:=length(s1); / 輸入字符串s1，并求它的長度 readln(s2); k2:=length(s2); / 輸入字符串s2，并求它的長度 For i:=1 to k1 do ak1-i+1 := ord(s1i) - ord(0) ; /字符串s1轉(zhuǎn)化為數(shù)組a For i:=1 to k2 do bk2-i+1 := ord(s2i) - ord(0) ; /字符串s2轉(zhuǎn)化為數(shù)組b For i:=1 to max do ci:=ai + bi; /加法運算 逐位處理和輸出見下頁For i:=1 to max

10、do /逐位處理 begin ci+1:=ci+1 + ci div 10; ci:= ci mod 10; end; top:=max; /尋找第一個有效數(shù)字的位置 while ctop=0 do top:=top-1; for i:=top downto 1 do write(ci); /倒序輸出end.試一試試一試兩個大整數(shù)的減法運算兩個大整數(shù)的減法運算? c a b(減法運算時不需要再做減法運算時不需要再做“進位進位”的處理，但是需的處理，但是需要進行要進行”借位借位”，先減再判斷是否為負數(shù)，是的，先減再判斷是否為負數(shù)，是的話被減數(shù)的高位數(shù)字減話被減數(shù)的高位數(shù)字減1，差數(shù)加，差數(shù)加10

11、。)注：前面算法用在減法時的漏洞是無法處理小數(shù)注：前面算法用在減法時的漏洞是無法處理小數(shù)減大數(shù)的情況減大數(shù)的情況const max=100;Var s1,s2: string; a,b,c: array1.max of integer; i,top,k1,k2:integer;begin readln(s1); k1:=length(s1); readln(s2); k2:=length(s2); For i:=1 to k1 do ak1-i+1 := ord(s1i) - ord(0) ; For i:=1 to k2 do bk2-i+1 := ord(s2i) - ord(0) ; F

12、or i:=1 to max do ci:=ai - bi; For i:=1 to max do begin if ci0 then begin ci:=ci + 10;ci+1:=ci+1-1 end; top:=max; while ctop=0 do top:=top-1; for i:=top downto 1 do write(ci); end.兩個大數(shù)的乘法( 選 讀 )兩個大整數(shù)的乘法運算兩個大整數(shù)的乘法運算基本方法基本方法 輸入串輸入串S1和串和串S2， S1和和S2分別轉(zhuǎn)化為整數(shù)數(shù)組分別轉(zhuǎn)化為整數(shù)數(shù)組a和和b 乘法運算乘法運算 c a * b 逐個進位處理逐個進位處理 判斷

13、最高位的位置判斷最高位的位置Var a, b, c: array1.10000of longint; L1, L2, i, j, k: longint; s1, s2: string;Begin readln(s1); L1:=length(s1); for i:=1 to L1 do aL1-i+1:=ord(s1i)-ord(0); /s1轉(zhuǎn)化為整數(shù)數(shù)組a readln(s2); L2:=length(s2); for i:=1 to L2 do bL2-i+1:=ord(s2i)-ord(0); /s2轉(zhuǎn)化為整數(shù)數(shù)組b for i:=L1 downto 1 do for j:=L2 downto 1 do ci+j-1:=ci+j-1 + ai*bj; /逐位相乘 k:=L1+L2-1; /乘積的