近日參加一個(gè)筆試，遇到大數(shù)乘法問(wèn)題舒裤，這是一個(gè)經(jīng)典的算法題队塘。所謂大數(shù)乘法問(wèn)題其實(shí)就是這樣的：輸入兩個(gè)整數(shù)，要求輸出這兩個(gè)數(shù)的乘積宜鸯。輸入的數(shù)字可能超過(guò)計(jì)算機(jī)內(nèi)任何數(shù)據(jù)的存儲(chǔ)范圍憔古。這里主要需要注意的點(diǎn)就是需要使用字符串或者字符數(shù)組來(lái)存儲(chǔ)這兩個(gè)大數(shù)以及他們的結(jié)果，還有乘法計(jì)算過(guò)程中存在乘法進(jìn)位和加法進(jìn)位淋袖。
我先自己嘗試寫了一個(gè)答案鸿市，思路就是模擬手寫豎式乘法。
static string MYMULTIPLY(const string &number1, const string &number2)
{
int length1 = number1.size();
int length2 = number2.size();
string result = "";
if (length1 == 0 || length2 == 0)
{
result = "error";
return result;
}
int *iresult;
iresult = (int*)malloc(sizeof(int) * (length1 + length2 + 1));
memset(iresult, 0, sizeof(int) * (length1 + length2 + 1));
for(int i = length1 - 1, x = 0; i >= 0; i--, x++)
{
int numA = number1[i] - 48;
int value1 = 0;
int value2 = 0;
int multiFlag = 0;//乘法進(jìn)位數(shù)
int addFlag = 0;//加法進(jìn)位數(shù)
for(int j = length2 - 1, y = 0; j >= 0; j--, y++)
{
int numB = number2[j] - 48;
value1 = numA * numB + multiFlag;
multiFlag = value1 / 10;
value1 = value1 % 10;
value2 = (iresult[x+y]) + value1 + addFlag;
addFlag = value2 / 10;
iresult[x+y] = (value2 % 10);
}
iresult[x + length2] += (multiFlag + addFlag);
}
//逆序
int i = 0;
for(i = length1 + length2 - 1; i >= 0; i--)
{
if(iresult[i] != 0)
break;
}
for(; i >= 0; i--)
{
result = result + (char)(iresult[i]+48);
}
free(iresult);
return result;
}
這個(gè)方法雖然能得出結(jié)果即碗，但是太難看了焰情，特別是計(jì)算每一位相乘的結(jié)果和進(jìn)位的那一段代碼。之后剥懒，我就把這段代碼改進(jìn)了一下内舟，將每一位之間的乘法和進(jìn)位計(jì)算分開(kāi)來(lái)。
static string MULTIPLY(string number1, string number2)
{
int i, j;
int *iresult;
int length1 = number1.size();
int length2 = number2.size();
string result = "";
reverse(number1.begin(), number1.end());
reverse(number2.begin(), number2.end());
if (length1 == 0 || length2 == 0)
{
result = "error";
return result;
}
iresult = (int*)malloc(sizeof(int) * (length1 + length2 + 1));
memset(iresult, 0, sizeof(int) * (length1 + length2 + 1));
//每一位相乘
for(i = 0; i < length1; i++)
{
for(j = 0; j < length2; j++)
{
iresult[i+j] += ((number1[i] - 48) * (number2[j] - 48));
}
}
//進(jìn)位運(yùn)算
int carry = 0;
for(i = 0; i < length1 + length2; i++)
{
int value = iresult[i] + carry;
iresult[i] = value % 10;
carry = value / 10;
}
for(i = length1 + length2 - 1; i >= 0; i--)
{
if(iresult[i] != 0)
break;
}
for(; i >= 0; i--)
{
result = result + (char)(iresult[i]+48);
}
free(iresult);
if(result == "") result = "0";
return result;
}
當(dāng)然這個(gè)問(wèn)題還有分治乘法初橘，快速傅里葉等算法验游，這個(gè)就不是在筆試或者面試的時(shí)候能快速寫出來(lái)的了。有興趣大家可以繼續(xù)深入了解下保檐。
