博客地址：https://imwjc.xyz/2020/04/add-two-big-numbers/

大數(shù)加法即能夠?qū)ΤL位數(shù)的數(shù)字進(jìn)行相加，比如一個100位數(shù)和一個80位數(shù)的數(shù)字相加。

在這種情況下，數(shù)的大小已經(jīng)超出了基本類型（int,long,double,float）能夠表示的范圍，直接加減只能得到錯誤的結(jié)果，想要得到正確的結(jié)果就需要使用其他數(shù)據(jù)結(jié)構(gòu)存儲這些數(shù)字，同時(shí)構(gòu)建相應(yīng)的相加函數(shù)，這里應(yīng)該想到可以使用占用空間可選的字符串類型。

問題抽象

輸入為(M,N):

• M: 字符串string存儲的10進(jìn)制整數(shù)

• N: 字符串string存儲的10進(jìn)制整數(shù)

輸出為S:

• S: 字符串string存儲的10進(jìn)制大數(shù)

數(shù)學(xué)原理

寫出計(jì)算一般數(shù)加法的步驟，如上圖?？梢钥吹剑恳淮窝h(huán)涉及到兩個加數(shù)當(dāng)前位a,b、進(jìn)位carry和結(jié)果位result，關(guān)系如下：

carry = (a + b) // 10
result = (a + b) % 10

循環(huán)至兩個數(shù)結(jié)束，若其中一個數(shù)長度小于另外一個數(shù)，則該數(shù)當(dāng)前位使用0進(jìn)行計(jì)算。

代碼實(shí)現(xiàn)

這里給出C++的算法實(shí)現(xiàn)，使用了大量內(nèi)置的STL，如不能使用STL庫可自行實(shí)現(xiàn)相關(guān)類型。

/**
* Created by Leslie
* 2020-03-28
*/

#include "string"
#include "algorithm"

using namespace std;

/**
* Add two big decimal numbers
* @param a string of a big number
* @param b string of a big number
* @return string of the result
*/
string AddTwoNumbers(string a, string b) {
? ?int x, y, sum, carry = 0;
? ?string result;
? ?auto iter_a = a.rbegin(), iter_b = b.rbegin();

? ?while (iter_a != a.rend() || iter_b != b.rend()) {
? ? ? ?// 其中一個數(shù)長度小于另外一個數(shù)，則遍歷該數(shù)不存在的高位時(shí)，用0替代
? ? ? ?x = iter_a != a.rend() ? *iter_a - '0' : 0;
? ? ? ?y = iter_b != b.rend() ? *iter_b - '0' : 0;
? ? ? ?
? ? ? ?sum = x + y + carry;
? ? ? ?carry = sum / 10;
? ? ? ?result += char(sum % 10 + '0');
?
? ? ? ?// 遍歷到最后一位時(shí)，迭代器不再移動
? ? ? ?if (iter_a != a.rend()) {
? ? ? ? ? ?iter_a++;
? ? ? ?}
? ? ? ?if (iter_b != b.rend()) {
? ? ? ? ? ?iter_b++;
? ? ? ?}
? ?}

? ?// 最高位存在進(jìn)位
? ?if (carry == 1) {
? ? ? ?result += char(carry + '0');
? ?}

? ?reverse(result.begin(), result.end());
? ?return result;
}

這里的string類型完全可以使用char*替代，可以嘗試使用C進(jìn)行實(shí)現(xiàn)。