时间戳

首页 > 解决方案 > 被间接乘法算法困住了

c++ - 被间接乘法算法困住了

问题描述

当我准备考试时，我发现了一个问题，要求使用间接乘法算法。

问题 ：

两个整数p和q可以通过以下方法间接相乘。

如果预期乘积为 r（最初为 0），则如果 q 为奇数，则将 p 添加到 r 并且 q 减 1，如果 q 为偶数，则 p 加倍且 q 减半（即 q 变为 q/2） 如果q为甚至p加倍并添加到r并且q减半（即q变为q /2）

进一步指出，间接乘法用于直接乘法昂贵的数字计算机

通过尝试几个小时，我设法找到了一种迭代和递归算法，但它们并不完美。

迭代

int multiply(int p, int q){
    int r=0;
    while(q!=0){
        if(q%2==1){
            r += p;
            q--;
        }
        else{
            r += 2*p;
            q = q/2;
        }
    }
    return r;
}

递归的

int multiplyRec(int p, int q){
    if(q==1)
        return p;
    if(q%2==1){
        return (p + multiplyRec(p, q-1));
    }
    else{
        return (2*p + multiplyRec(p, q/2));
    }
}

例如，当我将 6 乘以 5 时，两种算法的答案都是 36，而它必须是 30。但是如果我以某种方式更改它以获得 30，那么乘以 1 就会失败。

我在网上冲浪，但找不到匹配项。有人可以解释一下上述算法有什么问题，或者是否有错误，或者是否有更好的方法来做这些。

标签： c++crecursioniteration

解决方案

您报价框中的算法是错误的。它应该是：

如果预期乘积是 r（最初为 0），则如果 q 为奇数，则将 p 添加到 r 并且 q 减 1，如果 q 是偶数，则 p 加倍并且 q 减半（即 q 变为 q/2）

也就是说，当 q 是偶数时，你只需将 p 加倍，你不要将它添加到 r。

它也缺少 q == 0 的隐式终止条件

这对应于简单的二进制长乘法——对于 q 中的每个 1 位，您添加 p 左移 1 位的位置；对于 q 中的每个 0 位，您什么都不做。

这通常写成

while (q != 0) {
    if (q & 1)  // q is odd
        r += p;
    p *= 2;
    q /= 2;
}

那是因为当 q 为奇数时，减去 1 会使其成为偶数，因此您可以立即进行下一步，将 p 加倍并将 q 减半。由于整数除法向下舍入，奇数除以 2 也隐含地执行 -1。

推荐阅读