高精度運算及其應用

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

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

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

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

5、方式讀入兩個高精度數(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)一處理進位ifa[j]=10thenbe

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

7、輸出：500!=12201368259911100687012387854230469262535743428031928421924135883858453731538819976054964475022032818630136164771482035841633787220781772004807852051593292854779075719393306037729608590862704291745478824249127263

8、4430567017327076946106280231045264421887878946575477714986349436778103764427403382736539747138647787849543848959553753799042324106127132698432774571554630997720278101456108118837370953101635632443298702956389662891165897

9、4769572087926928871281780070265174507768410719624390394322536422605234945850129918571501248706961568141625359056693423813008856249246891564126775654481886506593847951775360894005745238940335798476363944905313062323749066

10、4450488246650759467358620746379251842004593696929810222639719525971909452178233317569345815085523328207628200234026269078983424517120062077146409794561161276291459512372299133401695523638509428855920187274337951730145863

11、5757082835578015873543276888868012039988238470215146760544540766353598417443048012893831389688163948746965881750450692636533817505547812864000000000000000000000000000000000000000000000000000000000000000000000000000000000