编写两个任意位数的大数相乘的程序，给出计算结果。
该题相继被ACM、华为、腾讯等选作笔试、面试题，笔者2014年替师兄去腾讯笔试就遇到此题，当然若无准备要写出这种程序，还是要花一定的时间的。故，觉得有必要深入研究一下。搜索了网上的大多数该类程序和算法，发现，大数乘法主要有模拟手工计算的普通大数乘法，分治算法和FFT算法。其中普通大数乘法占据了90%以上，其优点是空间复杂度低，实现简单，时间复杂度为O（N²），分治算法虽然时间复杂度降低为,
但其实现需要配 合字符串模拟加减法操作，实现较为复杂，
参考博客1http://cnn237111.blog.51cto.com/2359144/1201901
FFT算法则更为复杂，较少适用，有兴趣
参考博客2 http://blog.csdn.net/hondely/article/details/6938497
和博客3http://blog.csdn.net/jackyguo1992/article/details/12613287。
参考博客4的思路
乘积是逐位相乘，也就是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);//将计算结果转换为字符串并反转（1）转换并反转，字符串转换为数字并将字序反转；
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'); } }（2）逐位相乘，结果存放在result_num[i+j]中；
（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]; } if (c!=0) { result_num.push_back(c); } }（4）转换并反转，将计算结果转换为字符串并反转。
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 <iostream> #include <string> #include <vector> #include <stdlib.h> #include <assert.h> using namespace std; struct bigcheng2 { string a; string b; string result_str; }; 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); int c=0; 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)+'0';//将结果转换为字符 c=c/10; } while(c) { temp[i+j++]+=c;//temp里已存字符 c=c/10; } } for (int i=temp.size()-1;i>=0;i--) { if (temp[i]!='0') break; else temp.pop_back(); } reverse_data(temp);//结果?字Á?符¤?串ä?反¤¡ä转Áa tempcheng2.result_str=temp; }主函数：
int main() { 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; }移位进位法也是普通的大数相乘算法，其时间复杂度也为O（N²）其基本思路参考博客5，简述如下：
按照乘法的计算过程来模拟计算：
1 2
× 3 6
---------- ---- 其中，上标数字为进位数值。
71 2 --- 在这个计算过程中，2×6=12。本位保留2，进位为1.这里是一个简单的计算过程，如果在高位也需要进位的情况下，如何处理？
3 6
-----------
413 2
其代码优化如下：
#include <iostream> #include <string> #include <vector> #include <stdlib.h> #include <assert.h> using namespace std; void reverse_data( string &data);//字符串反转 void compute_value( string lhs,string rhs,string &result ); 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 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'); carry /= 10; } } for (int i=result.size()-1;i>=0;i--) { if (result[i]!='0') break; else result.pop_back(); } reverse_data(result); } int main() { string a,b; cin>>a>>b; string result(a.size()+b.size(),'0'); compute_value(a,b,result); cout<<result<<endl; system("pause"); return 0; }
3.3运行结果
运行结果如图1、图2所示
图1
图2
转载于:https://www.cnblogs.com/zhangliqiang/p/3944657.html
相关资源：JAVA上百实例源码以及开源项目