使用Karatsuba乘法將兩個大數相乘時無法得到正確答案（遞回高斯“技巧”）

我一直在嘗試使用字串來實作整數乘法問題。較小數字的乘積總是正確的，但對于較大的數字，結果是錯誤的。
誰能告訴我代碼的哪一部分導致了問題？

一個: 3141592653589793238462643383279502884197169399375105820974944592

b: 2718281828459045235360287471352662497757247093699959574966967627

答案：8539734222646569768352026223696548756537378365658178539814559622482948999279606844390394705148206869490910283679048366582723

正確答案：853973422267356706546355086954657449503488853576511496187960112706774304489320484861787507221624907301337489587184280658273

int getEquallength(string &a,string &b)
{
    int n1=a.length();
    int n2=b.length();
    if(n1>n2)
    {
        for(int i=0;i<n1-n2;i  )
        {
            b='0' b;
        }
    }
    else if(n2>n1)
    {
        for(int i=0;i<n2-n1;i  )
        {
            a='0' a;
        }
    }
    return n1;
}
string addstrings(string a,string b)
{
    int n=getEquallength(a,b);
    n=a.length();
    string result="";
    int carry=0;
    for(int i=n-1;i>=0;i--)
    {
        int f=a[i]-'0';
        int s=b[i]-'0';

        int sum=f s carry;
        carry=sum/10;
        sum=sum%10 '0';
        result=char(sum) result;
    }
    if(carry) result=char(carry '0') result;
    return result;
}
string substract_str(string a,string b)
{
    int n=getEquallength(a,b);
    int carry=0;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    
    string result;
    for(int i=0;i<a.length();i  )
    {
        int f=a[i]-'0';
        int s=b[i]-'0';
        int sub=0;
        sub=f-s-carry;
        if(sub<0)
        {
            sub =10;
            carry=1;
        }
        else
            carry=0;  
        result=char(sub '0') result;

    }

    return result;
}
string karatsuba(string a,string b)
{
    int n=getEquallength(a,b);
    if(n==0) return "0";
    if(n==1)
    {
        return to_string(atoi(a.c_str())*atoi(b.c_str()));
    }
    int fh=n/2;
    int sh=n-n/2;

    string Xl=a.substr(0,fh);
    string Xr=a.substr(fh,sh);
    string Yl=b.substr(0,fh);
    string Yr=b.substr(fh,sh);

    string P1=karatsuba(Xl,Yl);
    string P2=karatsuba(Xr,Yr);

    string res=addstrings(P1,P2);

    string P3=karatsuba(addstrings(Xl,Xr),addstrings(Yl,Yr));// (Xl Xr)*(Yl Yr)

    P3=substract_str(P3,res);//P3=Xl*Yr Xr.Yl

    for(int i=0;i<2*sh;i  )
    {
        P1.push_back('0');
    }
    for(int i=0;i<sh;i  )
    {
        P3.push_back('0');
    }




    P1= addstrings(P1,P2);

    string result=addstrings(P1,P3);
    return result;
}

uj5u.com熱心網友回復：

您在 getEqualLength 中有一個簡單的錯誤。它應該回傳 a.length() 或 b.length()。這是更正后的代碼：

//#include <bits/stdc  .h>
#include <string>
#include <iostream>

using namespace std;
int getEquallength(string& a, string& b)
{
    int n1 = a.length();
    int n2 = b.length();
    if (n1 > n2)
    {
        for (int i = 0; i < n1 - n2; i  )
        {
            b = '0'   b;
        }
    }
    else if (n2 > n1)
    {
        for (int i = 0; i < n2 - n1; i  )
        {
            a = '0'   a;
        }
    }
    return a.length();
}
string addstrings(string a, string b)
{
    int n = getEquallength(a, b);
    n = a.length();
    string result = "";
    int carry = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        int f = a[i] - '0';
        int s = b[i] - '0';

        int sum = f   s   carry;
        carry = sum / 10;
        sum = sum % 10   '0';
        result = char(sum)   result;
    }
    if (carry) result = char(carry   '0')   result;
    return result;
}
string substract_str(string a, string b)
{
    int n = getEquallength(a, b);
    int carry = 0;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());

    string result;
    for (int i = 0; i < a.length(); i  )
    {
        int f = a[i] - '0';
        int s = b[i] - '0';
        int sub = 0;
        sub = f - s - carry;
        if (sub < 0)
        {
            sub  = 10;
            carry = 1;
        }
        else
            carry = 0;
        result = char(sub   '0')   result;

    }

    return result;
}
string karutsuba(string a, string b)
{
    int n = getEquallength(a, b);
    if (n == 0) return "0";
    if (n == 1)
    {
        return to_string(atoi(a.c_str()) * atoi(b.c_str()));
    }
    int fh = n / 2;
    int sh = n - n / 2;

    string Xl = a.substr(0, fh);
    string Xr = a.substr(fh, sh);
    string Yl = b.substr(0, fh);
    string Yr = b.substr(fh, sh);

    string P1 = karutsuba(Xl, Yl);
    string P2 = karutsuba(Xr, Yr);

    string res = addstrings(P1, P2);

    string P3 = karutsuba(addstrings(Xl, Xr), addstrings(Yl, Yr));// (Xl Xr)*(Yl Yr)

    P3 = substract_str(P3, res);//P3=Xl*Yr Xr.Yl

    for (int i = 0; i < 2 * sh; i  )
    {
        P1.push_back('0');
    }
    for (int i = 0; i < sh; i  )
    {
        P3.push_back('0');
    }




    P1 = addstrings(P1, P2);

    string result = addstrings(P1, P3);
    return result;
}
int main()
{
    string a, b;
    cout << "a:" << '\n';
    cin >> a;
    cout << "b:" << '\n';
    cin >> b;
    int n = getEquallength(a, b);
    cout << karutsuba(a, b);

}

標籤：C 细绳 算法 乘法 唐叶

上一篇：在Rust中自動將Ghost新行和空格添加到String

下一篇：試圖在字串的索引中插入字符