传统竖式乘法实现错误求助：代码修复与算法原理解惑

问题分析 #

你的代码存在两个核心问题：

• 结果数组未初始化：fill函数调用被注释，导致result数组存储随机值，完全无法得到正确结果。
• 进位处理逻辑错误：每计算一个部分积就立即处理当前位的进位，遗漏了进位连锁传递的情况（比如低位进位到高位后，高位可能再次需要进位）。

修复后的C++代码 #

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main() 
{ 
    int A[] = {5, 2, 3, 0, 1}; 
    int B[] = {3, 0, 8}; 
    int size_A = sizeof(A) / sizeof(A[0]);
    int size_B = sizeof(B) / sizeof(B[0]); 
    int size_result = size_A + size_B; // n位×m位的结果最多n+m位
    int* result = new int[size_result]; 
    fill(result, result + size_result, 0); // 必须初始化数组为0

    // 累加所有部分积的对应位
    for (int i = size_A - 1; i >= 0; i--)
    { 
        for (int j = size_B - 1; j >= 0; j--) 
        { 
            int partial = A[i] * B[j]; 
            int pos_low = i + j + 1; // 部分积个位的位置
            int pos_high = i + j;    // 部分积十位的位置

            result[pos_low] += partial % 10;
            result[pos_high] += partial / 10;
        }
    }

    // 统一处理进位：从低位到高位传递
    for (int k = size_result - 1; k > 0; k--)
    {
        if (result[k] >= 10)
        {
            result[k-1] += result[k] / 10;
            result[k] %= 10;
        }
    }

    // 跳过前导零
    int startPos = 0; 
    while (result[startPos] == 0 && startPos < size_result - 1) {
        startPos++;
    }

    // 输出结果
    for (int i = startPos; i < size_result; i++) {
        cout << result[i];
    }
    cout << endl;
            
    delete[] result;
    return 0; 
}

算法核心解析 #

传统竖式乘法的本质是分位累加+统一进位：

• 分位累加：对于A的第i位（从右数，对应个位到最高位）和B的第j位，乘积的个位对应结果数组的i+j+1位置，十位对应i+j位置，将所有部分积的对应位直接累加，暂不处理进位。
• 统一进位：所有部分积累加完成后，从结果数组的最低位到最高位依次处理：如果当前位数值≥10，将十位部分进位到前一位，当前位保留个位数值。这种方式能完整处理所有连锁进位情况。

Java版本实现 #

public class TraditionalMultiplication {
    public static void main(String[] args) {
        int[] A = {5, 2, 3, 0, 1};
        int[] B = {3, 0, 8};
        int sizeA = A.length;
        int sizeB = B.length;
        int resultSize = sizeA + sizeB;
        int[] result = new int[resultSize];

        // 累加所有部分积
        for (int i = sizeA - 1; i >= 0; i--) {
            for (int j = sizeB - 1; j >= 0; j--) {
                int partial = A[i] * B[j];
                int posLow = i + j + 1;
                int posHigh = i + j;

                result[posLow] += partial % 10;
                result[posHigh] += partial / 10;
            }
        }

        // 处理进位
        for (int k = resultSize - 1; k > 0; k--) {
            if (result[k] >= 10) {
                result[k-1] += result[k] / 10;
                result[k] %= 10;
            }
        }

        // 跳过前导零
        int startPos = 0;
        while (startPos < resultSize - 1 && result[startPos] == 0) {
            startPos++;
        }

        // 输出结果
        for (int i = startPos; i < resultSize; i++) {
            System.out.print(result[i]);
        }
        System.out.println();
    }
}

内容的提问来源于stack exchange，提问作者Nr.Frahwhdakmrzmn