高精度運(yùn)算及其應(yīng)用

1、Jsoi2010Jsoi2010春季函授講義（春季函授講義（B2B2）11313高精度運(yùn)算及其應(yīng)用高精度運(yùn)算及其應(yīng)用一、引言一、引言利用計(jì)算機(jī)進(jìn)行數(shù)值運(yùn)算，經(jīng)常會(huì)遇到數(shù)值太大，超出Longint、int64等系統(tǒng)標(biāo)準(zhǔn)數(shù)據(jù)類型的有效范圍，如計(jì)算mn，而m、n≤100；有時(shí)又會(huì)遇到對(duì)運(yùn)算的精度要求特別高的情況，如計(jì)算圓周率π，要求精確到小數(shù)點(diǎn)后100位，此時(shí)real、double等數(shù)據(jù)類型也無(wú)能為力。這些情況下，我們都要用“高精度運(yùn)算”來(lái)解

2、決。一般我們將小數(shù)點(diǎn)后幾百位或者更多，當(dāng)然也可能是幾千億幾百億的大數(shù)字統(tǒng)稱為高精度數(shù)。高精度運(yùn)算首先要解決存儲(chǔ)問(wèn)題。一般都是定義一個(gè)一維數(shù)組來(lái)存儲(chǔ)一個(gè)高精度數(shù)，用每一個(gè)數(shù)組元素存儲(chǔ)該數(shù)的每一位或某幾位。高精度數(shù)的讀入可以采用兩種方法，一是采用字符串（StringAnsiString）方式一起讀入，再逐位處理成數(shù)字存儲(chǔ)在數(shù)組中；另一種方法是一位一位讀入并存儲(chǔ)到數(shù)組中。在實(shí)際使用時(shí)，請(qǐng)大家注意比較各自的優(yōu)、缺點(diǎn)。高精度運(yùn)算一般都是采用模擬的

3、方法解決。輸出時(shí)一定要注意格式和精度。二、高精度運(yùn)算二、高精度運(yùn)算1、編程實(shí)現(xiàn)編程實(shí)現(xiàn)高精度加法高精度加法[問(wèn)題描述]輸入兩個(gè)正整數(shù)（最多250位），輸出它們的和。比如輸入：99999999999999999999999999999999999999999999999999999912345678999999999999999999999999輸出：add=1000000000000000000000012345678999999999

4、999999999999998[問(wèn)題分析問(wèn)題分析]只要模擬“加法運(yùn)算”的過(guò)程，從低位（對(duì)齊）開(kāi)始逐位相加，最后再統(tǒng)一處理進(jìn)位即可。[參考程序參考程序]Programex1(inputoutput)constmax=250vars1s2:stringabc:array[1..max]ofbytel1l2li:integerbeginwriteln(inputtwolargeinteger:)readln(s1)readln(s2)用字符串

5、方式讀入兩個(gè)高精度數(shù)l1:=length(s1)l2:=length(s2)fi:=1tomaxdobegina[i]:=0b[i]:=0c[i]:=0end注意一定要初始化fi:=1tol1doa[i]:=d(s1[l11i])48Jsoi2010Jsoi2010春季函授講義（春季函授講義（B2B2）31313beginfj:=1tohdoa[j]:=a[j]i逐位乘fj:=1tohdo以下為統(tǒng)一處理進(jìn)位ifa[j]=10thenbe

6、gina[j1]:=a[j1]a[j]div10和高精度加法有何區(qū)別？a[j]:=a[j]mod10endwhilea[h1]0do最高位的進(jìn)位處理，和高精度加法有何區(qū)別？beginh:=h1a[h1]:=a[h]div10a[h]:=a[h]mod10endifa[h1]0thenh:=h1endwrite(n!=)輸出fi:=hdownto1dowrite(a[i])readlnend.[運(yùn)行示例運(yùn)行示例]輸入：inputn:500

7、輸出：500!=12201368259911100687012387854230469262535743428031928421924135883858453731538819976054964475022032818630136164771482035841633787220781772004807852051593292854779075719393306037729608590862704291745478824249127263

8、4430567017327076946106280231045264421887878946575477714986349436778103764427403382736539747138647787849543848959553753799042324106127132698432774571554630997720278101456108118837370953101635632443298702956389662891165897

9、4769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066

10、4450488246650759467358620746379251842004593696929810222639719525971909452178233317569345815085523328207628200234026269078983424517120062077146409794561161276291459512372299133401695523638509428855920187274337951730145863

11、5757082835578015873543276888868012039988238470215146760544540766353598417443048012893831389688163948746965881750450692636533817505547812864000000000000000000000000000000000000000000000000000000000000000000000000000000000