C語(yǔ)言實(shí)現(xiàn)高精度減法
介紹
眾所周知，整數(shù)在C和C++中以int ，long，long long三種不同大小的數(shù)據(jù)存儲(chǔ)，數(shù)據(jù)大小最大可達(dá)2^64，但是在實(shí)際使用中，我們?nèi)圆豢杀苊獾臅?huì)遇到爆long long的超大數(shù)運(yùn)算，這個(gè)時(shí)候，就需要我們使用高精度算法，來(lái)實(shí)現(xiàn)巨大數(shù)的運(yùn)算。
高精度的本質(zhì)是將數(shù)字以字符串的形式讀入，然后將每一位分別存放入int數(shù)組中，通過(guò)模擬每一位的運(yùn)算過(guò)程，來(lái)實(shí)現(xiàn)最終的運(yùn)算效果。
書(shū)接上回，我們今天繼續(xù)講解高精度減法的C語(yǔ)言實(shí)現(xiàn)：
代碼實(shí)現(xiàn)
#include<stdio.h>
const int N = 100001;
int cmp(int a[], int b[], int len1, int len2)
{//大小比較函數(shù)
if (len1 > len2)//先對(duì)比長(zhǎng)度
return 0;
else if (len1 < len2)//長(zhǎng)度不一樣直接返回結(jié)果
return 1;
else//長(zhǎng)度一致則依次比較每一位大小
{
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，避免減法函數(shù)中調(diào)用導(dǎo)致無(wú)限遞歸
}
int minus(int a[], int b[], int c[], int len1, int len2)
{//高精度減法函數(shù)
if (cmp(a, b, len1, len2))//減法函數(shù)只計(jì)算大減小，小減大則反過(guò)來(lái)，然后輸出時(shí)加負(fù)號(hào)
return minus(b, a, c, len2, len1);
int t = 0;//t標(biāo)識(shí)是否借位
for (int i = 0; i < len1; i++)
{
c[i] = (a[i] - b[i] + t + 10) % 10;//c[i]表示這一位運(yùn)算結(jié)果
if (a[i] - b[i] + t < 0) t = -1;//計(jì)算是否借位
else t = 0;
}
int len3 = len1;
while (c[len3 - 1] == 0)//去除前導(dǎo)0，返回結(jié)果的位數(shù)
{
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// 數(shù)據(jù)讀入部分不作贅述
{
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);//執(zhí)行高精度減法函數(shù)
if (cmp(a, b, len1, len2))//大小比較函數(shù)
printf("-");//結(jié)果為負(fù)數(shù)則打個(gè)負(fù)號(hào)先
for (int i = len3 - 1; i >= 0; i--)
printf("%d", c[i]);
return 0;
}
思路解析
鑒于在高精度加法一篇中我們已經(jīng)講解過(guò)了數(shù)據(jù)的讀入，所以我們這一篇不再贅述，沒(méi)看過(guò)上一篇的可以點(diǎn)擊下方鏈接：
高精度減法思路和高精度加法基本一致，區(qū)別就是加法考慮進(jìn)位，減法考慮退位，以及減法的結(jié)果的位數(shù)變動(dòng)是極大的。
我們對(duì)每一位分別計(jì)算，得出結(jié)果，存入新數(shù)組c，同時(shí)用臨時(shí)變量t來(lái)標(biāo)識(shí)是否借位。
但小數(shù)減大數(shù)的結(jié)果是負(fù)數(shù)，在實(shí)際操作中十分不便，所以我們另外聲明一個(gè)cmp函數(shù)來(lái)比較二者大小，如果被減數(shù)比較小，那我們就可以用減數(shù)減去被減數(shù)，輸出結(jié)果前先輸出一個(gè)負(fù)號(hào)，達(dá)到同樣的效果。
數(shù)據(jù)的讀入上，高精度加減乘除基本一模一樣，所以我們直接跳到第一個(gè)關(guān)鍵部分,大小比較函數(shù)：
int cmp(int a[], int b[], int len1, int len2)
{//大小比較函數(shù)
if (len1 > len2)//先對(duì)比長(zhǎng)度
return 0;
else if (len1 < len2)//長(zhǎng)度不一樣直接返回結(jié)果
return 1;
else//長(zhǎng)度一致則依次比較每一位大小
{
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，避免減法函數(shù)中調(diào)用導(dǎo)致無(wú)限遞歸
}
在數(shù)據(jù)的讀入中，我們已經(jīng)知道了兩數(shù)的位數(shù)，那就可以通過(guò)比較位數(shù)來(lái)判斷二者大小誰(shuí)長(zhǎng)誰(shuí)大。
倘若二者長(zhǎng)度一致，那就依次比較每一位的大小，也就是比較二者的字典序。
倘若二者完全一致，那我們返回0，原因后面說(shuō)。
有了大小比較函數(shù)，我們就可以保證計(jì)算時(shí)是大數(shù)減去小數(shù)了，這樣，我們就規(guī)避了負(fù)數(shù)的困擾，可以更輕松地實(shí)現(xiàn)高精度減法的函數(shù)：
int minus(int a[], int b[], int c[], int len1, int len2)
{//高精度減法函數(shù)
if (cmp(a, b, len1, len2))//減法函數(shù)只計(jì)算大減小，小減大則反過(guò)來(lái)，然后輸出時(shí)加負(fù)號(hào)
return minus(b, a, c, len2, len1);
int t = 0;//t標(biāo)識(shí)是否借位
for (int i = 0; i < len1; i++)
{
c[i] = (a[i] - b[i] + t + 10) % 10;//c[i]表示這一位運(yùn)算結(jié)果
if (a[i] - b[i] + t < 0) t = -1;//計(jì)算是否借位
else t = 0;
}
int len3 = len1;
while (c[len3 - 1] == 0)//去除前導(dǎo)0，返回結(jié)果的位數(shù)
{
if (len3 == 1) return len3;
len3--;
}
return len3;
}
如你所見(jiàn)，第一步就是對(duì)二者大小的判斷，如果被減數(shù)比減數(shù)小，我們直接改變?nèi)雲(yún)⒌捻樞騺?lái)改變二者位置。
倘若二者完全一致時(shí)cmp返回1，那么再調(diào)換位置后，minus函數(shù)將繼續(xù)調(diào)用cmp函數(shù)來(lái)判斷二者大小，每次都會(huì)返回1，導(dǎo)致無(wú)限遞歸，這就是我們規(guī)定完全一致時(shí)返回0的原因。
其中我們用c[i] = (a[i] - b[i] + t + 10) % 10;來(lái)計(jì)算結(jié)果的第i位，之所以要+10，是模擬結(jié)果為負(fù)時(shí)向前一位借10的過(guò)程，而如果(a[i] - b[i] + t)不為負(fù)數(shù)，那因?yàn)?code>%10的存在，也不會(huì)產(chǎn)生影響。
下一行if (a[i] - b[i] + t < 0)也很好理解，若是(a[i] - b[i] + t)為負(fù)數(shù)，那就需要向前一位借位，那我們就標(biāo)記t=-1，來(lái)影響下一位的結(jié)果計(jì)算即可。
最后我們需要去除前導(dǎo)0，首先因?yàn)檫\(yùn)算數(shù)都是正整數(shù)，所以結(jié)果最大位數(shù)也就和被減數(shù)一樣，所以我們從被減數(shù)的最高位數(shù)開(kāi)始判斷結(jié)果c，如果為0，那就把返回的長(zhǎng)度len3減去1，而值得注意的是，若是結(jié)果只有1位了那就不能減了，因?yàn)檫@意味著結(jié)果為0。
那此時(shí)我們就已經(jīng)完成了高精度減法的運(yùn)算，將結(jié)果存入了數(shù)組c，但別忘了結(jié)果正負(fù)的判斷：
if (cmp(a, b, len1, len2))//大小比較函數(shù)
printf("-");//結(jié)果為負(fù)數(shù)則打個(gè)負(fù)號(hào)先
如果被減數(shù)比減數(shù)小，我們需要提前把負(fù)號(hào)補(bǔ)上。
那就此，大功告成。
到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)高精度減法的文章就介紹到這了,更多相關(guān)C語(yǔ)言高精度減法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之堆排序源代碼
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之堆排序源代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
詳解C++ 動(dòng)態(tài)內(nèi)存分配與命名空間
這篇文章主要介紹了詳解C++ 動(dòng)態(tài)內(nèi)存分配與命名空間，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-08-08
個(gè)人覺(jué)得漢諾塔這個(gè)遞歸算法比電子老鼠的難了一些，不過(guò)一旦理解了也還是可以的，其實(shí)網(wǎng)上也有很多代碼，可以直接參考。記得大一開(kāi)始時(shí)就做過(guò)漢諾塔的習(xí)題，但是那時(shí)代碼寫(xiě)得很長(zhǎng)很長(zhǎng)，也是不理解遞歸的結(jié)果。今天重新來(lái)實(shí)現(xiàn)一下2015-03-03
C語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)串（堆分配存儲(chǔ)表示法）實(shí)例詳解
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)串（堆分配存儲(chǔ)表示法）實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-07-07
C++抽象基類(lèi)cap_ops定義設(shè)備操作接口,支持多態(tài),統(tǒng)一管理攝像頭、傳感器等設(shè)備,包含線程控制與資源管理方法,建議使用智能指針和日志,便于擴(kuò)展和維護(hù),本文給大家介紹C++ 虛函數(shù)實(shí)戰(zhàn),感興趣的朋友一起看看吧2025-07-07
Visual Studio Code 從簡(jiǎn)介、安裝到配置所需插件詳細(xì)介紹
這篇文章給大家介紹到vs與vs code的區(qū)別，并且會(huì)詳細(xì)介紹vscode的安裝步驟，和我所了解過(guò)的插件配置，感興趣的朋友跟隨小編一起看看吧2020-03-03
C語(yǔ)言qsort函數(shù)用冒泡排序?qū)崿F(xiàn)過(guò)程詳解
qsort函數(shù)是由C語(yǔ)言提供的標(biāo)準(zhǔn)庫(kù)函數(shù), 它的實(shí)現(xiàn)思想是快速排序。這篇文章主要介紹了C語(yǔ)言中qsort函數(shù)用法及用冒泡排序?qū)崿F(xiàn)qsort函數(shù)功能，需要的可以參考一下2023-02-02
這篇文章主要為大家詳細(xì)介紹了OpenCV識(shí)別圖像上的線條軌跡，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-07-07
本篇文章是對(duì)memset函數(shù)的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C語(yǔ)言運(yùn)用函數(shù)的遞歸實(shí)現(xiàn)漢諾塔
遞歸（recursive）函數(shù)是“自己調(diào)用自己”的函數(shù)，無(wú)論是采用直接或間接調(diào)用方式。間接遞歸意味著函數(shù)調(diào)用另一個(gè)函數(shù)（然后可能又調(diào)用第三個(gè)函數(shù)等），最后又調(diào)用第一個(gè)函數(shù)。因?yàn)楹瘮?shù)不可以一直不停地調(diào)用自己，所以遞歸函數(shù)一定具備結(jié)束條件2022-07-07