加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

大数相加相乘

发布时间:2020-12-14 05:15:41 所属栏目:大数据 来源:网络整理
导读:用乘法行列式多次相乘多次相加,时间复杂度为O(nm),n,m分别为两个数字长度。 #includestdio.h #include iostream #include string #include sstream using namespace std; string a,b,ans,zero,product; /// 输入a,b,ans是最终答案,zero是乘法行列式补零

用乘法行列式多次相乘多次相加,时间复杂度为O(nm),n,m分别为两个数字长度。

#include<stdio.h>
#include<iostream>
#include<string>
#include<sstream>
using namespace std;

string a,b,ans,zero,product;///输入a,b,ans是最终答案,zero是乘法行列式补零用的,product暂时存储单位数乘积
int len1,len2,cha,maxx;
int s,r;///s是本位,r是进位

string add(string a,string b)///字符串大数相加
{
    string res="";
    s=0;r=0;
    len1=a.size();
    len2=b.size();

    if(len1>=len2)
    {
        cha=len1-len2;
        for(int i=0;i<cha;i++)
            b="0"+b;
    }
    else
    {
        cha=len2-len1;
        for(int i=0;i<cha;i++)
            a="0"+a;
    }
    maxx=max(len1,len2);
    for(int i=maxx-1;i>=0;i--)
    {
        s=(a[i]-0+b[i]-0+r)%10;///先加上上次的进位
        r=(a[i]-0+b[i]-0+r)/10;///本次进不进位,进位则是1,不进位则是0
        res=(char)(s+0)+res;
    }
    if(r)
        res="1"+res;    ///最左边需不需要进位
    return res;
}

string trans(int a)  ///整型转化为string型,需要头文件sstream
{
    stringstream ss;///中转站
    string res;
    ss<<a;
    ss>>res;
    return res;
}

string multiplication(string a,char b)///字符串数字*单个字符
{
    s=r=0;
    string res="";
    int x,y=b-0;
    int len=a.size();
    for(int i=len-1;i>=0;i--)
    {
        x=a[i]-0;
        s=(x*y+r)%10;
        r=(x*y+r)/10;
        res=(char)(s+0)+res;
    }
    if(r)
        res=char(r+0)+res;
    return res;
}

int main()
{
    int t;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        cin>>a>>b;
        ans="";
        zero="";
        len2=b.size();
        for(int j=len2-1;j>=0;j--)
        {
            product=multiplication(a,b[j])+zero;
            ans=add(ans,product);
            zero=zero+0;  ///每往左进一位,乘法多补一个0
        }
        cout<<ans<<endl;
    }
    return 0;
}

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读