2

我正在用 C++ 编写一个十进制乘法器。乘法器是通过将两个整数表示为数字向量来实现的。每个向量以相反的顺序存储其数字，以便更容易地用十的幂表示。例如，3497 = 3 * 10^3 + 4 * 10^2 + 9 * 10^1 + 7 *10^0 并以 {7, 9, 4, 3} 的形式存储在向量中。因此，向量的每个索引表示该数字在整数中的相应十的幂。

但是，我的乘法中有一些错误。1 位 x 1 位和 2 位 x 1 位乘法完美运行，但它在 2 位 x 2 位时分解。我相当确定修复此错误将修复所有其他带有 n 位 x m 位的错误。我的乘法和加法方法的代码如下。

vector<int> multiply(vector<int> &a, vector<int> &b) {
    // check for emptiness
    if(a.size() == 0)
        return b;
    else if(b.size() == 0)
        return a;

    unsigned int i; // increment counter

    // compensate for size differences
    if(a.size() > b.size())
        for(i = 0; i < a.size()-b.size(); ++i)
            b.push_back(0);
    else
        for(i = 0; i < b.size()-a.size(); ++i)
            a.push_back(0);

    int c = 0; // carry value
    int temp; // temporary integer
    vector<int> p; // product vector
    vector<int> s; // sum vector
    s.push_back(0); // initialize to 0

    // multiply each digit of a by an index of b
    for(i = 0; i < b.size(); ++i) {
        // skip digits of 0
        if(b[i] == 0)
            continue;

        p.resize(i,0); // resize p and add 0s

        // multiply b[i] by each digit of a
        for(unsigned int j = 0; j < a.size(); ++j) {
            temp = c + b[i] * a[j]; // calculate temporary value

            // two cases
            if(temp > 9) {
                c = temp / 10; // new carry
                p.push_back(temp % 10);
            }
            else {
                c = 0;
                p.push_back(temp);
            }
        }

        // append carry if relevant
        if(c != 0)
            p.push_back(c);

        // sum p and s
        s = add(p, s);
        p.clear(); // empty p
    }

    return s; // return summed vector (total product)
}

vector<int> add(vector<int> &a, vector<int> &b) {
    // check for emptiness
    if(a.size() == 0)
        return b;
    else if(b.size() == 0)
        return a;

    unsigned int i; // increment counter

    // compensate size differences
    if(a.size() > b.size())
        for(i = 0; i < a.size()-b.size(); ++i)
            b.push_back(0);
    else
        for(i = 0; i < b.size()-a.size(); ++i)
            a.push_back(0);

    int c = 0; // carry value
    vector<int> s; // sum vector
    int temp; // temporary value

    // iterate through decimal vectors
    for(i = 0; i < a.size(); ++i) {
        temp = c + a[i] + b[i]; // sum three terms

        // two cases
        if(temp > 9) {
            c = temp / 10; // new carry
            s.push_back(temp % 10); // push back remainder
        }
        else {
            c = 0;
            s.push_back(temp);
        }
    }

    // append carry if relevant
    if(c != 0)
        s.push_back(c);

    return s; // return sum
}

几个测试用例：

45 * 16 返回 740（应为 720） 34 * 18 返回 542（应为 532） 67 * 29 返回 2003（应为 1943） 28 * 12 返回 336（正确）

我能想到的唯一问题是进位的问题，但是当我浏览代码时，一切似乎都检查出来了。任何人都可以看到错误吗？还是我完全采取了错误的方法？

4

2 回答 2

4

您没有清除内部循环之前（或之后）的进位。

    // iterate through decimal vectors
    for(i = 0; i < a.size(); ++i) {
        ...
    }

    // append carry if relevant
    if(c != 0) {
        p.push_back(c);
        // add this line
        c=0;
    }

此外，add您可能想要：

// compensate size differences
while (a.size() > b.size())
    b.push_back(0);
while (b.size() > a.size())
    a.push_back(0);

按原样，您只会推动等于（我相信）数组之间初始差异的一半的零数量。尝试一个交互式调试器（正如 James 建议的那样），您可能会发现其他错误（尽管手动运行如此短的代码也有一些话要说）。

于 2011-01-30T20:52:57.223 回答
1

一些额外的风格评论：

  1. 不要测试空向量然后返回您返回的内容，因为空向量的存在表明其他地方存在编程错误 - 要么引发异常，要么（可能更好）使用断言。当然，除非您使用空向量来表示 0 - 在这种情况下，逻辑仍然是错误的；0 * 某物 = 0，不是某物。

  2. 当您测试向量是否为空时，请使用.empty().

  3. 应该不需要用零将向量填充到相同的长度。您没有成对考虑元素；你把每一个相乘。您是否注意到目前您可能会b用零填充，但是您有逻辑在循环内完全跳过这些零？

  4. 但无论如何，填充可以做得更整齐：

    size_t len = std::max(a.size(), b.size());
a.resize(len); b.resize(len); // Note that 0 is the default "fill"

  5. 特殊情况还不够特殊。您处理这种情况的逻辑temp > 9 也可以很好地temp <= 9工作。不要过早优化。保持代码简单。（通过在现代处理器上添加分支很容易失去通过避免 div/mod 工作而获得的性能。）

  6. 不要通过反复清除和调整矢量来“重用”矢量。相反，在该范围内构建它（同样，不要过早优化）。一般来说，尽可能限制变量范围。类似的评论适用于其他变量。特别是对于循环计数器（ugh）。

  7. 但是要缓存一些东西，比如迭代的向量的大小（当这个大小是常数时）。这对编译器来说更难优化。

  8. 更好的是，当不需要索引时，使用迭代器对向量进行迭代。

  9. 输入向量不会改变，所以宣传一下。

  10. 在有合理的全长名称的地方使用全名。

  11. 你真的不需要评论那么多。很清楚发生了什么。

  12. 您正在做的那种运行总计（“累积”）是使用非常量引用的一个很好的候选者（少数几个好的理由之一）。

我会写（不考虑对算法进行重大更改）（警告，未经测试！）：

// I give the function a noun-type name because it returns a value. Just a convention.
vector<int> product(const vector<int> &a, const vector<int> &b) {
    assert !a.empty();
    assert !b.empty();

    vector<int> result(1); // initialized to hold 1 digit with value 0.

    vector<int>::const_iterator a_begin = b.begin(), a_end = b.end();
    size_t b_len = b.size();

    for (unsigned int i = 0; i < b_len; ++i) {
        vector<int> row(i);
        int carry = 0; // notice that proper scoping auto-fixes the bug.

        for (vector<int>::const_iterator it = a_begin; it != a_end; ++it) {
            int value = carry + b[i] * *it;
            carry = value / 10;
            row.push_back(value % 10);
        }
        if (carry != 0) value.push_back(carry);
        add(result, row);
    }
    return result;
}

// Similarly, if I were to return the sum, I would call this 'sum'.
void add(vector<int> &target, const vector<int> &to_add) {
    assert !target.empty();
    assert !to_add.empty();

    int count = to_add.size();

    // Make sure 'target' is long enough
    target.resize(std::max(target.size(), count));
    int size = target.size(); // after resizing.

    int carry = 0;

    // iterate through decimal vectors
    for (int i = 0; i < size; ++i) {
        int value = carry + target[i];
        if (i < count) { value += to_add[i]; }
        carry = value / 10;
        target[i] = value % 10;
    }

    if (carry != 0) { target.push_back(carry); }
}
于 2011-01-30T22:44:46.100 回答