2

第一件事：

~ 这是我在 StackOverflow 上的第一个问题。

~ 我是一名大学生。

~ 这不是我的作业问题（我这样做是为了增加我的算法思维）。

这是我的实现，它不断返回错误的答案。我尝试过运行GDB，但经验不足，无法确定算法出错的地方。请帮忙：

#include <iostream>
#include <cmath>

using namespace std;

int equalize(string &num1, string &num2){  
    int len1 = num1.length();
    int len2 = num2.length();
    if (len1 < len2){
        for (int i = 0; i < len2 - len1; i++){
            num1 = '0' + num1;
        }
        return len2;
    } else{
        for (int i = 0; i < len1 - len2; i++){
            num2 = '0' + num2;
        }
        return len1;
    }
}

string add(string num1, string num2){
    string result;
    int length = equalize(num1, num2);
    int carryover = 0;
    for (int i = length - 1; i >= 0; i--){
        int a = num1[i] - '0';
        int b = num2[i] - '0';
        int sum = a + b + carryover;
        carryover = sum / 10;
        sum = sum % 10;
        result = to_string(sum) + result;
    }
    if (carryover)
        result = to_string(carryover) + result;
    return result;
}

long karatsuba(string num1, string num2){
    int n = equalize(num1, num2);
    if (n == 0)
        return 0;
    else if (n == 1){
        return (num1[0] - '0') * (num2[0] - '0');
    } else{
        int primary = n / 2;
        int secondary = n - primary;
        string A = num1.substr(0, primary);
        string B = num1.substr(primary, secondary);
        string C = num2.substr(0, primary);
        string D = num2.substr(primary, secondary);
        long AC = karatsuba(A, C);
        long BD = karatsuba(B, D);
        long ABCD = karatsuba(add(A, B), add(C, D));
        return ((AC * pow(10, 2 * primary)) + ((ABCD - AC - BD) * pow(10, primary)) + (BD));
    }
}

int main() {
    string a = "111", b = "111";
    cout << karatsuba(a, b);
    return 0;
}

返回的答案是441理想情况下应该是12321.

4

0 回答 0