大数乘法

    xiaoxiao2021-03-26  4

    这次是接着上次的大数加减写的大数乘法。

    乘法的判断有些复杂。有以下几种情况。 1. a或者b为0 2. a或者b是负数 3. a和b都是负数

    因此在做乘法之前先对他们的符号做一个判断,我这里采取的是截取子串的以及标志的方法来处理。

    if(a[0]=='0' || b[0]=='0'){ sum.push_back('0'); return sum; } //判断符号 if(a[0]=='-'||b[0]=='-'){ flag=1; if(a[0]=='-'&&b[0]=='-') flag=0; if(a[0]=='-') a=a.substr(1,a.size()-1); if(b[0]=='-') b=b.substr(1,b.size()-1); }

    然后来说说大数乘法的思路。

    以1234*56为例 翻转数字后是 4 3 2 1 6 5

    6和每一位数相乘得到(24,18,12,6) 5和每一位数相乘得到( ,20,15,10,5) 我这样分开写的原因是模拟竖式乘法。 按相同位上的数相加可以得到(24,38,27,16,5) 现在就是一个取余进位的处理了。 (4,0,1,9,6)

    所以最后的结果应该是69104。

    根据以上思路写出如下代码。

    int num1,num2; for(int i=0;i<a.size();i++){ for(int j=0;j<b.size();j++){ num1=a[i]-'0'; num2=b[j]-'0'; result[i+j]+=num1*num2; } }

    这里当然还可以改进一下。。至于为什么是存进[i+j]里呢,这里是为了符合对应位的相加。。 我这里用了一个vector来存放数字。

    接着就是将数字转化为字符处理。以及进位。

    for(int i=0;i<result.size();i++){ if(result[i]>=10){ result[i+1]+=result[i]/10; result[i]%=10; } sum.push_back(result[i]+'0');

    接着就是要处理前导0的问题。。反转之后,用我上次在大数加减法所提到的截取子串去掉前导0的方法即可。

    完整的代码如下:

    #include<cstdio> #include<iostream> #include<string> #include<algorithm> #include<vector> using namespace std; string multiply(string a,string b){ string sum; int flag=0; vector <int> result(a.size()+b.size(),0); //判断0 if(a[0]=='0' || b[0]=='0'){ sum.push_back('0'); return sum; } //判断符号 if(a[0]=='-'||b[0]=='-'){ flag=1; if(a[0]=='-'&&b[0]=='-') flag=0; if(a[0]=='-') a=a.substr(1,a.size()-1); if(b[0]=='-') b=b.substr(1,b.size()-1); } reverse(a.begin(),a.end()); reverse(b.begin(),b.end()); int num1,num2; for(int i=0;i<a.size();i++){ for(int j=0;j<b.size();j++){ num1=a[i]-'0'; num2=b[j]-'0'; result[i+j]+=num1*num2; } } for(int i=0;i<result.size();i++){ if(result[i]>=10){ result[i+1]+=result[i]/10; result[i]%=10; } sum.push_back(result[i]+'0'); } reverse(sum.begin(),sum.end()); int ind=-1; while(sum[++ind]=='0'); if(ind!=-1) sum=sum.substr(ind); if(flag){ cout<<'-'; } return sum; } int main(){ string a,b; while(cin>>a>>b){ cout<<multiply(a,b)<<endl; } return 0; }

    当然还有更优化的办法。这里也是为了巩固才学的vector所以试着这样去写一写啦。。。如果有错或者什么更棒的方法,也希望大家指出啊。QWQ

    转载请注明原文地址: https://ju.6miu.com/read-500416.html

    最新回复(0)