大整數(shù)運(yùn)算
大整數(shù)存儲(chǔ)
在C語(yǔ)言中若要計(jì)算A+B，如果A和B的在范圍int(或long)范圍內(nèi)，那很容易就可以寫(xiě)出來(lái)，但是若A和B是有著1000個(gè)位數(shù)的整數(shù)就沒(méi)辦法用數(shù)據(jù)類(lèi)型來(lái)表示了，這時(shí)只能去模擬加減乘除的運(yùn)算過(guò)程。此外，大整數(shù)又稱(chēng)高精度整數(shù)，其含義就是用基本數(shù)據(jù)類(lèi)型無(wú)法存儲(chǔ)其精度的整數(shù)。
若要計(jì)算大整數(shù)首先要先把需要計(jì)算的大整數(shù)存儲(chǔ)下來(lái)，對(duì)于存儲(chǔ)大整數(shù)使用數(shù)據(jù)即可，例如定義int型數(shù)組d[1000]，那么這個(gè)數(shù)組中的一位就代表整數(shù)的每一位，不過(guò)這就產(chǎn)生一個(gè)問(wèn)題，當(dāng)我們把整數(shù)例如：258369當(dāng)字符串用%s讀入數(shù)組S時(shí)，則S[0]=2,S[1]=5,S[2]=8……S[5]=9此時(shí)若兩數(shù)相加需要進(jìn)位則需要數(shù)組集體向后移一位才可以進(jìn)位十分麻煩，所以我們將讀入之后需將數(shù)組翻轉(zhuǎn)一下及：S[0]=9,S[1]=6,S[2]=3……S[5]=2
而為了方便獲取大整數(shù)我們首先定義一個(gè)int類(lèi)型的變量len來(lái)記錄大整數(shù)的長(zhǎng)度，并和數(shù)組 d 組合成結(jié)構(gòu)體并利用構(gòu)造函數(shù)為結(jié)構(gòu)體初始化，代碼如下
struct bign{
int d[1000]; //定義數(shù)組用來(lái)存儲(chǔ)大整數(shù)
int len; //用來(lái)存儲(chǔ)大整數(shù)的位數(shù)
bign(){
memset(d, 0, sizeof(d)); //初始化數(shù)據(jù)b全部存儲(chǔ)為0
len = 0; //初始化大整數(shù)長(zhǎng)度
}
};
而輸入大整數(shù)時(shí)，一般先用字符串讀入，然后再把字符串另存為bing結(jié)構(gòu)體，由于使用 char 數(shù)組讀入，所以要將翻轉(zhuǎn)一下然后在賦值給結(jié)構(gòu)體中的 d數(shù)組：
bign change(shar str[]){ //將大整數(shù)存入bign
bign a;
int i;
a.len = strlen(str); //bign的長(zhǎng)度就是字符串的長(zhǎng)度
for(i = 0; i < a.len; i++)
a.d[i] = str[a.len - i -1] - '0'; //逆著賦值
return a;
}
若需要比較兩個(gè)大整數(shù)的大小，則首先判斷兩者的len大小，如果不相等，則len長(zhǎng)的大；如果相等，則從高位到低位一次比較，直到某一位不等時(shí)就可以判斷出兩數(shù)的大小，代碼如下：
int compare(bign a, bign b){ //比較a和b的大小
if(a.len > b.len) return 1; //a大返回 1
else if(a.len < b.len) return -1; //b大返回 -1
else{
int i;
for(i = a.len - 1; i >= 0; i--){
if(a.d[i] > b.d[i]) return 1; //a大返回 1
else if(a.b[i] < b.d[i]) return -1; //b大返回 -1
}
return 0; //兩數(shù)相等返回 0
}
}
大整數(shù)的四則運(yùn)算
高精度加法
若將153+86看做兩個(gè)大整數(shù)相加，我按照小學(xué)的豎式進(jìn)行相加如下：
-
3 + 6 = 9，個(gè)位取作為該結(jié)果9，十位取0作為進(jìn)位。 -
5 + 8 = 13，再加上進(jìn)位0還為13，然后個(gè)位取3作為結(jié)果，十位1作為進(jìn)位。 -
1 + 0 = 1，再加上進(jìn)位1，然后取個(gè)位2為結(jié)果
將上述步驟歸納可得出如下代碼：
bign add(bign a, bign b){ //高精度a+b
bign c;
int carry = 0; //表示進(jìn)位
int i;
for(i = 0; i<a.len || i<b.len; i++){ //以較長(zhǎng)的為界限
int temp = a.d[i] + b.len[i] + carry; //兩數(shù)相加并加上進(jìn)位
c.d[c.len++] = temp % 10; //個(gè)位為該位結(jié)果
carry = temp / 10; //十位為進(jìn)位
}
if(carry !=0 ) c.d[c,len++] = carry; //軟工最后進(jìn)位不為零則直接賦值給最高位
return c;
}
完整高精度A+B代碼如下：
#include<stdio.h>
struct bign{
int d[1000]; //定義數(shù)組用來(lái)存儲(chǔ)大整數(shù)
int len; //用來(lái)存儲(chǔ)大整數(shù)的位數(shù)
bign(){
memset(d, 0, sizeof(d)); //初始化數(shù)據(jù)b全部存儲(chǔ)為0
len = 0; //初始化大整數(shù)長(zhǎng)度
}
};
bign change(shar str[]){ //將大整數(shù)存入bign
bign a;
int i;
a.len = strlen(str); //bign的長(zhǎng)度就是字符串的長(zhǎng)度
for(i = 0; i < a.len; i++)
a.d[i] = str[a.len - i -1] - '0'; //逆著賦值
return a;
}
bign add(bign a, bign b){ //高精度a+b
bign c;
int carry = 0; //表示進(jìn)位
int i;
for(i = 0; i<a.len || i<b.len; i++){ //以較長(zhǎng)的為界限
int temp = a.d[i] + b.len[i] + carry; //兩數(shù)相加并加上進(jìn)位
c.d[c.len++] = temp % 10; //個(gè)位為該位結(jié)果
carry = temp / 10; //十位為進(jìn)位
}
if(carry !=0 ) c.d[c,len++] = carry; //軟工最后進(jìn)位不為零則直接賦值給最高位
return c;
}
void print(bign a){ //輸出bign
int i;
for(i = a.len-1; i >=0; i--)
printf("%d",a.d[i]);
}
main()
{
char s1[1000],s2[1000];
scanf("%s%s",s1,s2);
bign a = change(s1);
bign b = change(s2);
print(add(a,b));
}
高精度減法
若將 169-96 看做兩個(gè)大整數(shù)減法，我按照小學(xué)的豎式進(jìn)行相加如下：
-
9-6>0夠減，不需要借位，則直接減，結(jié)果為：3 -
6-9<0不夠減，向高位1借1，于是改結(jié)果為16-9=7 - 兩數(shù)最高位均為
0，計(jì)算結(jié)束
將上述步驟歸納可得出如下代碼：
bign sub(bign a,bign b){ //高精度A-B
bign c;
int i;
for(i = 0; i<a.len || i<b.len; i++){ //以較長(zhǎng)的為界限
if(a.d[i] < b.d[i]){ //如果不夠減
a.d[i+1] --; //向高位借位
a.d[i] += 10; //當(dāng)前位+10
}
c.d[c.len++] = a.[i] - b.d[i]; //計(jì)算當(dāng)前結(jié)果
}
while(c.len-1 >= 1 && c.d[c.len -1] == 0)
c.len -- ; //去除高位的0，同時(shí)若兩數(shù)相見(jiàn)為0則保留一位0
return c;
}
若題目涉及的高精度減法A-B<0則利用函數(shù)compare()判斷一下，若 A<B 則計(jì)算 B-A 并輸出一個(gè)符號(hào)即可。
高精度與低精度的乘法
所謂低精度就是可以用基本數(shù)據(jù)類(lèi)型存儲(chǔ)的數(shù)據(jù)，而高精度與低精度的乘法就是講述 bign 與 int 類(lèi)型的乘法，其做法與小學(xué)學(xué)的豎式略有不同，若以258 × 25（258看做高精度數(shù)據(jù)、25看做低精度數(shù)據(jù)）為例，在計(jì)算過(guò)程中要把低精度數(shù)據(jù)25看做一個(gè)整體，具體做法如下：
-
25×8=200，個(gè)位數(shù) 0 作為該位的結(jié)果，20 作為進(jìn)位。 -
25×5=125，再加上進(jìn)位的 20，結(jié)果為145，個(gè)位數(shù) 5 作為該位結(jié)果，14作為進(jìn)位。 -
2×25=50，再加上進(jìn)位的 14，結(jié)果為64，個(gè)位數(shù) 4 作為該位結(jié)果，6作為進(jìn)位。
將上述步驟歸納可得出如下代碼：
bign multi(bign a,bign b){
bign c;
int carry = 0; //進(jìn)位
int i;
for(i = 0; i < a.len; i++){
int temp = a.d[i] * b + carry;
c.d[c.len++] = temp % 10; //個(gè)位為該位結(jié)果
carry = temp / 10; //十位為進(jìn)位
}
while(carry !=0 ){ //乘法的進(jìn)位和加法不一樣，乘法的可能不止一一位
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}
高精度除以低精度
除法計(jì)算和小學(xué)學(xué)的豎式相同，以 1234/7 為例：
- 1與7比較，不夠除，因此該位商為0，余數(shù)為1。
- 余數(shù)1與新位2組合成12，12與7比較，夠除，商為1,余數(shù)為5。
- 余數(shù)5與新位3組合成53，53與7比較，夠除，商為7,余數(shù)為4。
- 余數(shù)4與新位4組合成44，44與7比較，夠除，商為6,余數(shù)為2。
將上述步驟歸納可得出如下代碼：
bign divde(bign a, bign b, int& r){ //r為余數(shù)
bign c;
c.len = a.len; //被除數(shù)的每一位和商的每一位是一一對(duì)應(yīng)的，因此先另長(zhǎng)度相等
int i;
for(i = a.len - 1; i >=0 ; i--){ //從高位開(kāi)始除
r = r * 10 + a.d[i]; //和上一位遺留的余數(shù)組合
if(r < b) c.d[i] = 0; //不夠除則為0
else{
c.d[i] = r / b ; //夠除則求出商
r %= b; //獲得新的余數(shù)
}
}
while(c.len -1 >= 1 && c.d[c.len - 1] == 0)
c.len --; //去除高位的0，同時(shí)若兩數(shù)相見(jiàn)為0則保留一位0
return c;
}
