編寫兩個任意位數的大數相乘的程式，給出計算結果。
該題相繼被ACM、華為、騰訊等選作筆試、面試題，筆者2014年替師兄去騰訊筆試就遇到此題，當然若無準備要寫出這種程式，還是要花一定的時間的。故，覺得有必要深入研究一下。搜尋了網上的大多數該類程式和算法，發現，大數乘法主要有模拟手工計算的普通大數乘法，分治算法和FFT算法。其中普通大數乘法占據了90%以上，其優點是空間複雜度低，實作簡單，時間複雜度為O（N²），分治算法雖然時間複雜度降低為,
但其實作需要配 合字元串模拟加減法操作，實作較為複雜，
FFT算法則更為複雜，較少适用，有興趣
乘積是逐位相乘，也就是aibj，結果加入到積C的第i+j位，最後處理進位即可，例如：A =17 = 1*10 + 7 = （7,1）最後是十進制的幂表示法，幂次是從低位到高位，以下同。B=25 = 2*10 + 5 = (5, 2);C = A * B = (7 * 5, 1 * 5 + 2 * 7, 1 * 2) = (35, 19, 2) = (5, 22, 2) = (5, 2. 4)=425。
原部落格的思路為：
（1）轉換并反轉，字元串轉換為數字并将字序反轉；
（2）逐位相乘，結果存放在result_num[i+j]中；
（3）處理進位，消除多餘的0；
（4）轉換并反轉，将計算結果轉換為字元串并反轉。
原部落格中采用指針參數傳遞，字元串長度有限制，改為通過string傳參數，按原思路程式設計如下：
頭檔案和資料結構：
#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
struct bigcheng
{
vector<int> a;
vector<int> b;
string result_str;
};
void chartonum(string a,string b,bigcheng &tempcheng);//字元串轉換為數字并反轉
void multiply(bigcheng &tempchengh,vector<int> &result_num);//逐位相乘,處理進位消除多餘的0
void numtochar(bigcheng &tempcheng,vector<int> &result_num);//将計算結果轉換為字元串并反轉
void chartonum(string a,string b,bigcheng &tempcheng)
int size_a=a.size();
int size_b=b.size();
for (int i=size_a-1;i>=0;i--)
{
tempcheng.a.push_back(a[i]-'0');
}
for (int i=size_b-1;i>=0;i--)
tempcheng.b.push_back(b[i]-'0');
}
（3）處理進位，消除多餘的0；代碼為：
void multiply(bigcheng &tempcheng,vector<int> &result_num)
for (unsigned int i=0;i<tempcheng.a.size();i++)
for (unsigned int j=0;j<tempcheng.b.size();j++)
{
result_num[i+j]+=(tempcheng.a[i])*(tempcheng.b[j]);
}
for (int i=result_num.size()-1;i>=0;i--)
if (result_num[i]!=0)
break;
else
result_num.pop_back();
int c=0;
for (unsigned int i=0;i<result_num.size();i++)//處理進位
result_num[i]+=c;
c=result_num[i]/10;
result_num[i]=result_num[i]%10;
if (c!=0)
result_num.push_back(c);
void numtochar(bigcheng &tempcheng,vector<int> &result_num)
{ int size=result_num.size();
for (unsigned int i=0;i<result_num.size();i++)
tempcheng.result_str.push_back(char(result_num[size-1-i]+'0'));
主函數為：
int main()
bigcheng tempcheng;
string a,b;
cin>>a>>b;
chartonum(a,b,tempcheng);
vector<int> resultnum(a.size()+b.size(),0);
multiply(tempcheng,resultnum);
numtochar(tempcheng,resultnum);
cout<<tempcheng.result_str<<endl;
system("pause");
return 0;
上面的思路還是很清晰的，但代碼有些過長，考慮優化如下：
（1）上述思路是先轉換反轉，其實無需先将全部字元串轉換為數字的，可即用即轉，節約空間；
（2）無需等到逐位相乘都結束，才處理進位，可即乘即進；
（3）無需等到所有結果出來後，将結果轉換為字元，可即乘即轉。
優化後時間複雜度不變，但節省了空間，代碼更簡潔。如下：
#include <assert.h>
struct bigcheng2
string a;
string b;
void reverse_data( string &data)；//字元串反轉
void multiply2(bigcheng2 &tempcheng2);//字元串模拟相乘
字元串反轉：
void reverse_data( string &data)
char temp = '0';
int start=0;
int end=data.size()-1;
assert( data.size()&& start <= end );
while ( start < end )
temp = data[start];
data[start++] = data[end];
data[end--] = temp;
兩數相乘：
void multiply2(bigcheng2 &tempcheng2)
reverse_data(tempcheng2.a);//字元串反轉
reverse_data(tempcheng2.b);
string temp(tempcheng2.a.size()+tempcheng2.b.size(),'0');//将temp全部初始化為0字元
for (unsigned int i=0;i<tempcheng2.a.size();i++)
unsigned int j;
for (j=0;j<tempcheng2.b.size();j++)
c+=temp[i+j]-'0'+(tempcheng2.a[i]-'0')*(tempcheng2.b[j]-'0');//注意temp[i+j]可能儲存有上一次計算的結果
temp[i+j]=(c%10)+'0';//将結果轉換為字元
c=c/10;
while(c)
temp[i+j++]+=c%10;//temp裡已存字元
for (int i=temp.size()-1;i>=0;i--)
if (temp[i]!='0')
temp.pop_back();
reverse_data(temp);//結果?字Á?符¤?串ä?反¤¡ä轉Áa
tempcheng2.result_str=temp;
主函數：
bigcheng2 tempcheng2;
string a,b;
cin>>a>>b;
tempcheng2.a=a;
tempcheng2.b=b;
multiply2(tempcheng2);
cout<<tempcheng2.result_str<<endl;
system("pause");
return 0;
按照乘法的計算過程來模拟計算：
1 2
× 3 6
---------- ---- 其中，上标數字為進位數值。
71 2 --- 在這個計算過程中，2×6=12。本位保留2，進位為1.這裡是一個簡單的計算過程，如果在高位也需要進位的情況下，如何處理？
3 6
-----------
413 2
其代碼優化如下：
void reverse_data( string &data);//字元串反轉
void compute_value( string lhs,string rhs,string &result );
void compute_value( string lhs,string rhs,string &result )
reverse_data(lhs);
reverse_data(rhs);
int i = 0, j = 0, res_i = 0;
int tmp_i = 0;
int carry = 0;
for ( i = 0; i!=lhs.size(); ++i, ++tmp_i )
res_i = tmp_i; //在每次計算時，結果存儲的位需要增加
for ( j = 0; j!= rhs.size(); ++j )
carry += ( result[res_i] - '0' )+(lhs[i] - '0') * (rhs[j] - '0');//此處注意，每次計算并不能保證以前計算結果的進位都消除， 并且以前的計算結果也需考慮。
result[res_i++] = ( carry % 10 + '0' );
carry /= 10;
while (carry)//乘數的一次計算完成，可能存在有的進位沒有處理
result[res_i++] = (carry % 10 + '0');
for (int i=result.size()-1;i>=0;i--)
if (result[i]!='0')
result.pop_back();
reverse_data(result);
string result(a.size()+b.size(),'0');
compute_value(a,b,result);
cout<<result<<endl;
3.3運作結果
運作結果如圖1、圖2所示
圖1
圖2
本文轉自夏雪冬日部落格園部落格，原文連結：http://www.cnblogs.com/heyonggang/p/3599857.html，如需轉載請自行聯系原作者