C語(yǔ)言實(shí)現(xiàn)高精度加法的示例代碼

更新時(shí)間：2023年11月05日 09:35:43 作者：涼茶coltea

高精度的本質(zhì)是將數(shù)字以字符串的形式讀入,然后將每一位分別存放入int數(shù)組中,通過(guò)模擬每一位的運(yùn)算過(guò)程,來(lái)實(shí)現(xiàn)最終的運(yùn)算效果,下面我們就來(lái)看看如何通過(guò)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)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: