高精度的本質是將數字以字元串的形式讀入,然後將每一位分別存放入`int`數組中,通過模擬每一位的運算過程,來實現最終的運算效果。 ...
高精度減法(C語言實現)
介紹
眾所周知,整數在C和C++中以int
,long
,long long
三種不同大小的數據存儲,數據大小最大可達2^64
,但是在實際使用中,我們仍不可避免的會遇到爆long long
的超大數運算,這個時候,就需要我們使用高精度演算法,來實現巨大數的運算。
高精度的本質是將數字以字元串的形式讀入,然後將每一位分別存放入int
數組中,通過模擬每一位的運算過程,來實現最終的運算效果。
書接上回,我們今天繼續講解高精度減法的C語言實現:
代碼實現
#include<stdio.h>
const int N = 100001;
int cmp(int a[], int b[], int len1, int len2)
{//大小比較函數
if (len1 > len2)//先對比長度
return 0;
else if (len1 < len2)//長度不一樣直接返回結果
return 1;
else//長度一致則依次比較每一位大小
{
for (int i = len1 - 1; i >= 0; i--)
{
if (a[i] > b[i])
return 0;
if (a[i] < b[i])
return 1;
}
}
return 0;//如果完全一致則返回0,避免減法函數中調用導致無限遞歸
}
int minus(int a[], int b[], int c[], int len1, int len2)
{//高精度減法函數
if (cmp(a, b, len1, len2))//減法函數只計算大減小,小減大則反過來,然後輸出時加負號
return minus(b, a, c, len2, len1);
int t = 0;//t標識是否借位
for (int i = 0; i < len1; i++)
{
c[i] = (a[i] - b[i] + t + 10) % 10;//c[i]表示這一位運算結果
if (a[i] - b[i] + t < 0) t = -1;//計算是否借位
else t = 0;
}
int len3 = len1;
while (c[len3 - 1] == 0)//去除前導0,返回結果的位數
{
if (len3 == 1) return len3;
len3--;
}
return len3;
}
int main()
{
char str1[N], str2[N];//----------------------------
int a[N] = { 0 }, b[N] = { 0 }, c[N] = { 0 };
char x;
int len1 = 0, len2 = 0;
do
{
scanf("%c", &x);
str1[len1++] = x;
} while (x != '\n');
do// 數據讀入部分不作贅述
{
scanf("%c", &x);
str2[len2++] = x;
} while (x != '\n');
len1--; len2--;
for (int i = len1 - 1; i >= 0; i--)
a[i] = str1[len1 - i - 1] - '0';
for (int i = len2 - 1; i >= 0; i--)
b[i] = str2[len2 - i - 1] - '0';//---------------
int len3 = minus(a, b, c, len1, len2);//執行高精度減法函數
if (cmp(a, b, len1, len2))//大小比較函數
printf("-");//結果為負數則打個負號先
for (int i = len3 - 1; i >= 0; i--)
printf("%d", c[i]);
return 0;
}
思路解析
鑒於在高精度加法一篇中我們已經講解過了數據的讀入,所以我們這一篇不再贅述,沒看過上一篇的可以點擊下方鏈接:
高精度減法思路和高精度加法基本一致,區別就是加法考慮進位,減法考慮退位,以及減法的結果的位數變動是極大的。
我們對每一位分別計算,得出結果,存入新數組c
,同時用臨時變數t
來標識是否借位。
但小數減大數的結果是負數,在實際操作中十分不便,所以我們另外聲明一個cmp
函數來比較二者大小,如果被減數比較小,那我們就可以用減數減去被減數,輸出結果前先輸出一個負號,達到同樣的效果。
數據的讀入上,高精度加減乘除基本一模一樣,所以我們直接跳到第一個關鍵部分,大小比較函數:
int cmp(int a[], int b[], int len1, int len2)
{//大小比較函數
if (len1 > len2)//先對比長度
return 0;
else if (len1 < len2)//長度不一樣直接返回結果
return 1;
else//長度一致則依次比較每一位大小
{
for (int i = len1 - 1; i >= 0; i--)
{
if (a[i] > b[i])
return 0;
if (a[i] < b[i])
return 1;
}
}
return 0;//如果完全一致則返回0,避免減法函數中調用導致無限遞歸
}
在數據的讀入中,我們已經知道了兩數的位數,那就可以通過比較位數來判斷二者大小誰長誰大。
倘若二者長度一致,那就依次比較每一位的大小,也就是比較二者的字典序。
倘若二者完全一致,那我們返回0,原因後面說。
有了大小比較函數,我們就可以保證計算時是大數減去小數了,這樣,我們就規避了負數的困擾,可以更輕鬆地實現高精度減法的函數:
int minus(int a[], int b[], int c[], int len1, int len2)
{//高精度減法函數
if (cmp(a, b, len1, len2))//減法函數只計算大減小,小減大則反過來,然後輸出時加負號
return minus(b, a, c, len2, len1);
int t = 0;//t標識是否借位
for (int i = 0; i < len1; i++)
{
c[i] = (a[i] - b[i] + t + 10) % 10;//c[i]表示這一位運算結果
if (a[i] - b[i] + t < 0) t = -1;//計算是否借位
else t = 0;
}
int len3 = len1;
while (c[len3 - 1] == 0)//去除前導0,返回結果的位數
{
if (len3 == 1) return len3;
len3--;
}
return len3;
}
如你所見,第一步就是對二者大小的判斷,如果被減數比減數小,我們直接改變入參的順序來改變二者位置。
倘若二者完全一致時cmp
返回1
,那麼再調換位置後,minus
函數將繼續調用cmp
函數來判斷二者大小,每次都會返回1
,導致無限遞歸,這就是我們規定完全一致時返回0的原因。
其中我們用c[i] = (a[i] - b[i] + t + 10) % 10;
來計算結果的第i
位,之所以要+10
,是模擬結果為負時向前一位借10
的過程,而如果(a[i] - b[i] + t)
不為負數,那因為%10
的存在,也不會產生影響。
下一行if (a[i] - b[i] + t < 0)
也很好理解,若是(a[i] - b[i] + t)
為負數,那就需要向前一位借位,那我們就標記t=-1
,來影響下一位的結果計算即可。
最後我們需要去除前導0
,首先因為運算數都是正整數,所以結果最大位數也就和被減數一樣,所以我們從被減數的最高位數開始判斷結果c
,如果為0
,那就把返回的長度len3
減去1
,而值得註意的是,若是結果只有1
位了那就不能減了,因為這意味著結果為0
。
那此時我們就已經完成了高精度減法的運算,將結果存入了數組c
,但別忘了結果正負的判斷:
if (cmp(a, b, len1, len2))//大小比較函數
printf("-");//結果為負數則打個負號先
如果被減數比減數小,我們需要提前把負號補上。
那就此,大功告成。
結尾
那麼以上便是對高精度減法演算法的介紹,本文由涼茶coltea撰寫,思路來自AcWing,大佬yxc的課程。