【算法】字符串大整数相乘

àì夳堔傛蜴生んèń 2022-05-19 23:36 141阅读 0赞

题目描述：  
给定两个以字符串形式存储的大整数，要求以字符串形式输出相乘后的结果。  
思路：  
模拟计算乘法时列竖式的过程，对于两个字符串s1和s2，让s2的每一位和s1整体相乘，求得一组中间值，然后对中间值做移位操作，最后将移位后的所有中间值相加即可求得最终结果。  
问题的关键在于实现两个函数，用于计算两个字符串相加以及字符串和单个字符相乘的结果。

//计算两个字符串相加
    string myadd(const string &s1, const string &s2);
    //字符串和单个字符相乘
    string mymult(const string &s, const char c);
    //消除结果中多余的‘0’
    string & check_num(string &s);
    
    //计算俩个字符串的乘积
    string mymult(string &s1, string &s2)
    {
        string res;
        string tmp;
        int n = s2.size();
    
        for(int i = n-1; i >= 0; i--){
            tmp = mymult(s1, s2[i]);
    
            //向左移位
            for(int j = 0; j < n-1-i; j++)
                tmp.push_back('0');
            res = myadd(res, tmp);
        }
    
        return check_num(res);
    }
    
    string mymult(const string &s, const char c)
    {
        string res;
        int carry = 0;
        int mult = 0;
    
        for(int i = s.size()-1; i >= 0; i--){
            mult = (s[i] - '0') * (c - '0') + carry;
            carry = mult/10;
            res.insert(res.begin(), char('0' + mult%10));
        }
    
        if(carry > 0)
            res.insert(res.begin(), char('0' + carry));
    
        return res;
    }
    
    string myadd(const string &s1, const string &s2)
    {
        string res;
        int c = 0;
        int sum = 0;
        int i = s1.size() - 1;
        int j = s2.size() - 1;
        int n = min(i,j) + 1;
    
        while(i >= 0 && j >= 0){
            sum = (s1[i]-'0') + (s2[j]-'0') + c;
            c = sum/10;
            res.insert(res.begin(), char('0' + sum%10));
            i--;
            j--;
        }
    
        if(i < 0 && j < 0){
            if(c > 0)
                res.insert(res.begin(), char('0'+c));
            return res;
        }
    
        while(i >= 0){
            int sum = (s1[i]-'0') + c;
            c = sum/10;
            res.insert(res.begin(), char('0' + sum%10));
            i--;
        }
    
        while(j >= 0){
            int sum = (s2[j]-'0') + c;
            c = sum/10;
            res.insert(res.begin(), char('0' + sum%10));
            j--;
        }
    
        return res;
    }
    
    string & check_num(string &s)
    {
        if(s.size() == 0){
            s.push_back('0');
            return s;
        }
    
        while(s[0] == '0' && s.size() > 1){
            s.erase(0, 1);
        }
        return s;
    }