#include <iostream>
#include <string>
#include <list>
using namespace std;
//三个数相加求低位
char add_gw(char a,char b,char c)
{
return ((a-'0')+(b-'0')+(c-'0'))%10+'0';
}
//三个数相加求高位
char add_sw(char a,char b,char c)
{
return ((a-'0')+(b-'0')+(c-'0'))/10+'0';
}
//这里实现多位数相加,后向前遍历string
string add(string a,string b)
{
list<char> sum;
if(a.length()<b.length())
a.swap(b);
string::reverse_iterator a_i = a.rbegin();
//进位数字
char temp='0';
for(string::reverse_iterator b_i=b.rbegin();b_i<b.rend();b_i++)
{
//插入到前面
sum.push_front(add_gw(*a_i,*b_i,temp));
temp = add_sw(*a_i,*b_i,temp);
a_i++;
} //b的位数比较短,先遍历完了,之后把进位和a的剩余位数加完。
for(;a_i<a.rend();a_i++)
{
sum.push_front(add_gw(*a_i,'0',temp));
temp = add_sw(*a_i,'0',temp);
} //看看进位是不是非零。
if(temp != '0')
sum.push_front(temp); //将list 转化为string
string str_sum;
for(list<char>::iterator i=sum.begin();i!=sum.end();i++)
{
str_sum.push_back(*i);
}
return str_sum;
}
//两位数乘法得到个位
char mul_gw(char a,char b)
{
return ((a-'0')*(b-'0'))%10+'0';
}
//两位数乘法得到十位
char mul_sw(char a,char b)
{
return ((a-'0')*(b-'0'))/10+'0';
}
//向左移位操作操作
string & yiwei(string &a,int weishu)
{
if(a.length()>0 && a.at(0) != '0')
{
for(int i=0;i<weishu;i++)
{
a.push_back('0');
}
}
return a;
}
//乘法
string multiply(string a,string b)
{
string sum;
if(a.length()<b.length())
a.swap(b);
if(b.length() == 0)
{
sum = "0";
return sum;
}
if(a.length()==1)
{
char temp = mul_sw(a[0],b[0]);
if(temp != '0')
sum.push_back(temp);
sum.push_back(mul_gw(a[0],b[0]));
return sum;
} //a的长度超过1就折半分别求
if(a.length()>1)
{
string a1 = a.substr(0,a.length()/2);
string a2 = a.substr(a.length()/2,-1);
string b2;
string b1;
if((a.length()+1)/2>b.length())
{
b2 = b;
b1.clear();
}
else
{
b2 = b.substr(b.length()-(a.length()+1)/2,-1);
b1 = b.substr(0,b.length()-(a.length()+1)/2);
} //这里为了调试才这么写,其实可以一次性写完的。
string x1 = yiwei(multiply(a1,b1),a2.length()*2);
string x2 = yiwei(multiply(a1,b2),a2.length());
string x3 = yiwei(multiply(a2,b1),a2.length());
string x4 = multiply(a2,b2);
string x5 = add(x1,x2);
string x6 = add(x3,x4);
string x7 = add(x5,x6);
return x7;
}
}
int main()
{
string a,b;
cin>>a>>b;
cout<<multiply(a,b)<<endl;
getchar();
getchar();
return 0;
}
由于string是由数组实现的,因此push_front的时间复杂度O(n),n歌就是O(n^2),改用list,只要最后转成string只用O(n)。
这里简介里面的递归算法,
将大数A,B分成两段,后面段的长度为x。如图:
好了,一切明了。
原文链接: https://www.cnblogs.com/chengzheqiao/archive/2013/05/06/3063096.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/87308
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!