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)算效果。
今天,我們先講解高精度加法的C語(yǔ)言實(shí)現(xiàn):
聲明
但其實(shí)我這版C語(yǔ)言的高精度算法封裝是很有問(wèn)題的,沒(méi)有stl,字符串的操作是比較繁瑣的,以后熟悉C++后我會(huì)再寫(xiě)一版簡(jiǎn)易的,標(biāo)準(zhǔn)的高精度算法解析,但通過(guò)本文了解高精度的思路也是沒(méi)有問(wèn)題的。
代碼實(shí)現(xiàn)
#include<stdio.h> const int N = 100001; int add(int a[], int b[], int c[], int len1, int len2) { int t = 0, i = 0, max = len1 > len2 ? len1 : len2; //max指兩加數(shù)中較大者的位數(shù),兩數(shù)之和c位數(shù)至少是max //標(biāo)識(shí)變量t值為0或1,代表是否進(jìn)位,初始為0 for (; i <= max; i++)//運(yùn)算到較大者位數(shù)后一位停止 { c[i] = (a[i] + b[i] +t) % 10;//c的每一位為兩數(shù)該位之和加上t再模去10 t = (a[i] + b[i] + t) / 10;//若和>10,則c[i]取其個(gè)位,t取其十位 }//i遍歷至max+1 if (c[i - 1] == 1) return i;//若最高位為1,則返回c長(zhǎng)度為max+1,即i else return i - 1;//否則返回max,即i-1 } int main() { char str1[N], str2[N];//兩個(gè)數(shù)的字符串形式 int a[N] = { 0 }, b[N] = { 0 }, c[N] = { 0 };//ab為加數(shù),c為和 char x; int len1 = 0, len2 = 0;//兩數(shù)位數(shù) do { scanf("%c", &x); str1[len1++] = x; }while (x != '\n'); do{ scanf("%c", &x); str2[len2++] = x; } while (x != '\n'); len1--; len2--;//將數(shù)據(jù)讀入str1和str2,同時(shí)記錄位數(shù) 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';//將ab的每一位轉(zhuǎn)換為整形存入數(shù)組 int len3 = add(a, b, c, len1, len2);//執(zhí)行高精度加法函數(shù) for (int i = len3 - 1; i >= 0; i--) printf("%d", c[i]);//輸出 return 0; }
思路分析
對(duì)大數(shù)來(lái)說(shuō),輸入便已經(jīng)是一個(gè)有些麻煩的問(wèn)題,無(wú)法讀取整形,只能以字符串形式,而且連有幾位數(shù)字都不知道。
char str1[N], str2[N];//兩個(gè)數(shù)的字符串形式 int a[N] = { 0 }, b[N] = { 0 }, c[N] = { 0 };//ab為加數(shù),c為和 char x; int len1 = 0, len2 = 0;//兩數(shù)位數(shù) do { scanf("%c", &x); str1[len1++] = x; }while (x != '\n'); do{ scanf("%c", &x); str2[len2++] = x; } while (x != '\n'); len1--; len2--;//將數(shù)據(jù)讀入str1和str2,同時(shí)記錄位數(shù)
這里是主函數(shù)的變量聲明和輸入部分,若是程序只運(yùn)行一次高精度運(yùn)算,我們可以把變量的聲明放在主函數(shù)以外,來(lái)能減少函數(shù)的參數(shù)個(gè)數(shù)。
我們將讀取的字符賦值給x
,然后再放入字符串?dāng)?shù)組,最后對(duì)x
進(jìn)行判斷,若x
為換行符、空格或其他標(biāo)識(shí)著數(shù)據(jù)輸入結(jié)束的字符,則終止循環(huán)。
同時(shí),循環(huán)中變化的數(shù)組下標(biāo)我們直接記為len1
和len2
,代表兩個(gè)數(shù)字的長(zhǎng)度。
顯然,字符形式的數(shù)字并不好運(yùn)算,所以,我們需要將每一位轉(zhuǎn)換為整形存入數(shù)組,方便后續(xù)的計(jì)算。
那此時(shí)我們就會(huì)遇到一個(gè)問(wèn)題,數(shù)組的第0位應(yīng)該存放最高位還是存放個(gè)位呢?先看代碼實(shí)現(xiàn):
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';//將ab的每一位轉(zhuǎn)換為整形存入數(shù)組
在這段函數(shù)中,我們從高位向低位,將每一位的字符-'0'
,得到他的整形,然后存入數(shù)組,最終得到從低位到高位的新數(shù)組。
為什么要反過(guò)來(lái)存放呢,這就要考慮到一個(gè)最高位進(jìn)位的問(wèn)題。
數(shù)組后面存放最高位,在最高位進(jìn)位時(shí)顯然比最高位放在第0位操作起來(lái)更方便,前者只需要在下一位+1
,而后者想要進(jìn)位,可能只能依靠于額外的標(biāo)記變量了。
這種問(wèn)題在后面的高精度乘法中更是明顯,所以,在高精度運(yùn)算中,為了使高位靈活變動(dòng),我們一般都采用倒序的存放順序,即數(shù)組前面存低位,后面存高位。
到這里,我們就將準(zhǔn)備工作做完了,數(shù)字已經(jīng)放入數(shù)組,長(zhǎng)度也已得知,這時(shí)我們就需要寫(xiě)一個(gè)函數(shù)來(lái)運(yùn)行高精度加法,代碼如下:
int add(int a[], int b[], int c[], int len1, int len2) { int t = 0, i = 0, max = len1 > len2 ? len1 : len2; //max指兩加數(shù)中較大者的位數(shù),兩數(shù)之和c位數(shù)至少是max //標(biāo)識(shí)變量t值為0或1,代表是否進(jìn)位,初始為0 for (; i <= max; i++)//運(yùn)算到較大者位數(shù)后一位停止 { c[i] = (a[i] + b[i] +t) % 10;//c的每一位為兩數(shù)該位之和加上t再模去10 t = (a[i] + b[i] + t) / 10;//若和>10,則c[i]取其個(gè)位,t取其十位 }//i遍歷至max+1 if (c[i - 1] == 1) return i;//若最高位為1,則返回c長(zhǎng)度為max+1,即i else return i - 1;//否則返回max,即i-1 }
雖然圖中解析已經(jīng)非常到位了,但我還是簡(jiǎn)單講解一下吧。
首先從i=0
位開(kāi)始,將a[i]
與b[i]
和t
相加,其個(gè)位便是c
在該位的值,所以我們對(duì)他模上10
,其大于10
時(shí)需要進(jìn)位,那我們就將其除以10
,整形除法下取整,得到1
或0
,作為t
的值,來(lái)參與下一位的運(yùn)算。
最后,我們通過(guò)對(duì)最高位的0
或1
判斷,來(lái)決定返回max
還是max+1
。
這時(shí),我們已經(jīng)將結(jié)果存入c
了,只差輸出了,但想要輸出我們?cè)趺粗?code>c有幾位呢?最高位到底有沒(méi)有進(jìn)位呢?那其實(shí)我們的函數(shù)返回值就是c
的長(zhǎng)度了。
int len3 = add(a, b, c, len1, len2);//執(zhí)行高精度加法函數(shù) for (int i = len3 - 1; i >= 0; i--) printf("%d", c[i]);//輸出
這樣,我們從后往前一位位輸出,就得出了最終結(jié)果了。
總結(jié)
總而言之言而總之,高精度算法就是單獨(dú)將每一位數(shù)字存入數(shù)組,分別計(jì)算,模擬我們手動(dòng)計(jì)算的過(guò)程,接下來(lái)的減法和乘法除法的核心思想都是這個(gè),那么以上便是對(duì)高精度加法算法的介紹,本文由涼茶coltea撰寫(xiě),思路來(lái)自AcWing,大佬yxc的課程。
到此這篇關(guān)于C語(yǔ)言實(shí)現(xiàn)高精度加法的示例代碼的文章就介紹到這了,更多相關(guān)C語(yǔ)言高精度加法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)LeetCode(112.二叉樹(shù)的路徑和)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(112.二叉樹(shù)的路徑和),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C語(yǔ)言中建立和刪除文件連接的相關(guān)函數(shù)講解
這篇文章主要介紹了C語(yǔ)言中建立和刪除文件連接的相關(guān)函數(shù)講解,分別為link和unlink函數(shù)的使用,需要的朋友可以參考下2015-09-09實(shí)現(xiàn)posix消息隊(duì)列示例分享
這篇文章主要介紹了實(shí)現(xiàn)posix消息隊(duì)列示例,學(xué)習(xí)記錄鎖,線(xiàn)程互斥量,線(xiàn)程條件變量,內(nèi)存映射,信號(hào),線(xiàn)程的綜合應(yīng)用,需要的朋友可以參考下2014-02-02C++詳解使用floor&ceil&round實(shí)現(xiàn)保留小數(shù)點(diǎn)后兩位
這篇文章主要介紹了C++使用floor&ceil&round實(shí)現(xiàn)保留小數(shù)點(diǎn)后兩位的方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07C++實(shí)現(xiàn)LeetCode(131.拆分回文串)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(131.拆分回文串),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C語(yǔ)言計(jì)算器的3種實(shí)現(xiàn)方法代碼
這篇文章主要給大家介紹了關(guān)于C語(yǔ)言計(jì)算器的3種實(shí)現(xiàn)方法,文中通過(guò)代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一的參考借鑒價(jià)值,需要的朋友可以參考下2007-01-01動(dòng)態(tài)數(shù)組C++實(shí)現(xiàn)方法(分享)
下面小編就為大家?guī)?lái)一篇?jiǎng)討B(tài)數(shù)組C++實(shí)現(xiàn)方法(分享)。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-05-05