高精度的算法思路

1.大整數(shù)存儲(chǔ)

2.高精度的加減乘除

大整數(shù)存儲(chǔ)

正常情況下，書寫一個(gè)數(shù)是從高位到低位的，但在高精度中，應(yīng)該從低位到高位存儲(chǔ)。因?yàn)閷?duì)于一個(gè)數(shù)組來說，從末尾添加數(shù)據(jù)會(huì)比從開頭添加數(shù)據(jù)容易。而在計(jì)算中，通常都是從個(gè)位數(shù)往高位數(shù)計(jì)算，也就是從計(jì)算是不斷的往高位數(shù)靠的，所以，高位數(shù)應(yīng)該被置于某位。即，對(duì)1234而言，a[0]=4，a[1]=3，a[2]=2，a[3]=1。

高精度加法思路

首先，我們令t為進(jìn)位。a,b為加數(shù)和被加數(shù)，c為a,b相加后的結(jié)果。那么，a為一個(gè)大的數(shù)組（如1234），a[0]=4，a[1]=3，a[2]=2，a[3]=1。

如果a[0]+b[0]<10,那么c[0]=a[0]+b[0]

a[0]+b[0]>=10,那么存在進(jìn)位，即進(jìn)位t=a[0]+b[0]的十位數(shù),c[0]=a[0]+b[0]個(gè)位數(shù)

由于a,b,c均為十進(jìn)制數(shù)，而兩位的十進(jìn)制數(shù)=十位*10的1次方+個(gè)位*10的零次方。

所以，取進(jìn)制的方法就是t=(a[0]+b[0])/10,c[0]=(a[0]+b[0])%10

而對(duì)c[1]而言，需要加上進(jìn)位，c[1]=a[1]+b[1]+t

這么一來,可以認(rèn)為c[i]=a[i]+b[i]+t

高精度加法過程

1.判斷加數(shù)和被加數(shù)進(jìn)位是否存在，存在便加

2.分別取相加結(jié)果之和，取個(gè)位壓入存儲(chǔ)結(jié)果的數(shù)組，取十位作為進(jìn)位

3.判斷是否存在進(jìn)位，存在，壓入

由于c數(shù)組的長(zhǎng)度未知，而數(shù)組在定義聲明時(shí),必須使用常量表達(dá)式給出其容量大小,而且程序運(yùn)行時(shí)數(shù)組不允許動(dòng)態(tài)的增刪元素，vector允許動(dòng)態(tài)的增刪元素。故采用vector。

使用vector需要加上#include <vector>

vector相當(dāng)于一個(gè)動(dòng)態(tài)數(shù)組，類似于java中的list。

push_back在數(shù)組的最后添加一個(gè)數(shù)據(jù)

auto 就是編譯器自動(dòng)判斷類型，比如在這里會(huì)自動(dòng)判斷為vector<int>(add函數(shù)的類型)

a[i]-’0’的目的是將a[i]變成數(shù)字，a[i]定義成了字符串來便于輸入。

高精度減法思路

減法與加法之間存在相似之處。

如果a[0]-b[0]>=0，那么不存在問題可以直接相減，即c[0]=a[0]-b[0]。

但如果a[0]-b[0]<0，那么就會(huì)出現(xiàn)結(jié)果為負(fù)的情況，這時(shí)候，需要向a[1]進(jìn)行借位。而與上面相同的是，個(gè)位向十位借位就是需要加上10，即c[i]=a[i]-b[i]+10。

同樣，從a[1]開始，都存在被借位的可能，因此上述表達(dá)式都需要前去借位t

a[0]-b[0]>=0時(shí)，c[i]=a[i]-b[i]-t;

a[0]-b[0]<0，c[i]=a[i]-b[i]+10-t;

而對(duì)于整個(gè)數(shù)a,b而言，存在類似的問題。

a-b>=0時(shí)，c=a-b;

a-b<0時(shí)，c=-(a-b);

最后，還需考慮前導(dǎo)0的問題，即119-110會(huì)被視為009，但我們需要的答案是9，所以需要去掉前面的0。在去掉0的時(shí)候，還需考慮有1-1=0的情況，這種情況的0是不能被刪除的，判斷的條件應(yīng)為c的長(zhǎng)度是否為1。

高精度減法過程

1.如果減數(shù)和被減數(shù)在位置上均有數(shù),帶上進(jìn)位,相減

2.進(jìn)行借位得到位置上的結(jié)果

3.判斷是否真的進(jìn)行了借位來更改借位得值

4.去除前導(dǎo)零

5.比較結(jié)果是否大于零,小于零的話,反過來相減并加上負(fù)號(hào)

高精度乘法思路

整體思想上，高精度乘法和高精度加法相似，這里進(jìn)行討論高精度的整數(shù)乘以低精度的整數(shù)的情況，也就是需要一個(gè)高精度的整數(shù)乘以低精度的整數(shù)。也就是說，不必將b進(jìn)行大整數(shù)存儲(chǔ)。

通過加法的思路，可得：

c[0]=(a[0]*b)%10

t=(a[0]*b)/10

c[1]=(a[0]*b+t)%10

t=(a[0]*b+t)/10

可見，乘法在這方面跟加法是一毛一樣的。

但是，由于最后的進(jìn)位存在為零的可能性，需要去除前導(dǎo)零。

高精度乘法過程

1.將每有位數(shù)依次和,并加上進(jìn)位

2.將結(jié)果的十位數(shù)壓入

3.將結(jié)果個(gè)位數(shù)更新為進(jìn)位

4.去除前導(dǎo)零

高精度除法思路

令c為商，a為被除數(shù)，b為除數(shù)，r為余數(shù)。

由于push_back的壓入操作中,是對(duì)c[0]往后走的,所以,與大整數(shù)存儲(chǔ)的思路相反,故還需將整個(gè)數(shù)的序列進(jìn)行反轉(zhuǎn)。

乘法與除法的輸入輸出相同且同樣存在前導(dǎo)零的問題。

高精度除法過程

1.通過余數(shù)和a[]求新的被除數(shù)

2.將新的被除數(shù)的十位數(shù)壓入

3.求余數(shù)

4.求出商后,反轉(zhuǎn)序列

5.去除前導(dǎo)零

使用reverse函數(shù)需要加上#include <algorithm>。

勤奮，今天的夕弦也很努力呢！