递归Karatsuba乘法算法实现调试求助：中间值不符合预期

看起来你在Karatsuba算法的实现上卡了壳，我帮你梳理下代码里的几个关键问题，这些就是导致中间值（ac、bd等）不符合预期的核心原因：

1. 递归时传入的位数参数与实际数字位数不匹配 #

这是最致命的问题！你的multiply函数依赖传入的n来拆分数字，但递归调用时，比如计算(a+b)*(c+d)，这个结果的位数可能比odd2(n)多一位（比如99+99=198，原本的odd2(4)=2，但198是3位数）。这时候你仍然用odd2(n)作为位数传入multiply，会导致num_split错误地拆分数字，直接丢弃高位，计算自然出错。

解决方法：不要手动传入位数，而是在每次调用multiply时，自动计算当前数字的实际位数。比如新增一个函数获取数字的位数，然后在multiply内部调用这个函数获取x和y的位数，取最大值作为拆分基准（因为x和y的位数可能不同）。

2. num_split函数的拆分逻辑错误 #

你的num_split假设传入的数字正好是d位，但实际情况中，数字可能比d长或短。比如数字是198（3位），传入d=2时，你的代码会把它拆成a=9，b=8，完全丢失了高位的1；如果数字是12（2位），传入d=3，会拆成a=1，b=2，而正确的补0后应该是a=0，b=12。

修复思路：直接用除法和取模拆分更简单可靠——计算拆分的分界点k（低位的位数），然后用10^k作为除数，高位a = num / 10^k，低位b = num % 10^k。这样不管数字位数是否等于预期，都能正确拆分（位数不够时高位自动补0，位数过多时取高位部分）。

3. 数据类型溢出问题 #

你用int存储ac、bd、total、sum这些中间值，但Karatsuba算法的中间结果很容易超过32位int的范围（比如稍大一点的数相乘，中间值就会溢出）。应该把这些变量改成long long类型，避免溢出导致的错误值。

4. 语法错误 #

返回语句里多了一个右括号：

return power(10, odd1(n))*ac + power(10, n/2))*sum + bd;
// 这里多了一个）---------------------------^

这个错误会导致编译失败，必须修正为：

return power(10, odd1(n))*ac + power(10, n/2)*sum + bd;

修复后的完整代码 #

我把这些问题都修复了，你可以直接运行测试：

#include <iostream>
#include <algorithm> // 用于max函数
using namespace std;

// 计算数字的实际位数
int getDigitCount(int num) {
    if (num == 0) return 1;
    int count = 0;
    while (num > 0) {
        count++;
        num /= 10;
    }
    return count;
}

// 迭代实现幂运算，避免递归栈溢出
long long power(int b, int e) {
    long long result = 1;
    for (int i = 0; i < e; i++) {
        result *= b;
    }
    return result;
}

// 拆分数字：num = a * 10^k + b，k是低位的位数
void num_split(int num, int k, long long *a, long long *b) {
    long long divisor = power(10, k);
    *a = num / divisor;
    *b = num % divisor;
}

long long multiply(int x, int y) {
    // 递归终止条件：单个数字直接相乘
    if (x < 10 || y < 10) {
        return (long long)x * y;
    }

    // 获取x和y的位数，取最大值作为基准
    int n = max(getDigitCount(x), getDigitCount(y));
    int k = n / 2; // 低位的位数

    long long a, b, c, d;
    num_split(x, k, &a, &b);
    num_split(y, k, &c, &d);

    // 递归计算三个子问题
    long long ac = multiply((int)a, (int)c);
    long long bd = multiply((int)b, (int)d);
    long long total = multiply((int)(a + b), (int)(c + d));
    long long sum = total - ac - bd;

    // Karatsuba核心公式
    return ac * power(10, 2 * k) + sum * power(10, k) + bd;
}

int main() {
    int x = 1234, y = 1234;
    long long product = multiply(x, y);
    cout << product << endl; // 应该输出1522756
    return 0;
}

关键改进点说明 #

• 去掉了手动传入位数的参数，改用getDigitCount自动计算实际位数，彻底避免了位数不匹配的问题。
• 简化了num_split函数，用除法和取模直接拆分，逻辑更清晰且不易出错。
• 所有中间结果和power函数的返回值都改用long long，防止数值溢出。
• 递归终止条件更简洁，直接判断是否为个位数。

你可以运行这段代码测试，比如输入1234*1234会得到正确的1522756，中间的ac、bd等值也会符合预期。

内容的提问来源于stack exchange，提问作者Jithakrishna Prakash