当我准备考试时,我发现了一个问题,要求使用间接乘法的算法。
问题:
两个整数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就失败了。
我在网上冲浪,但找不到匹配的。有没有人可以解释一下上面的算法有什么问题,或者是否有错误,或者有没有更好的方法来做它们。
发布于 2018-12-19 14:33:01
您报价框中的算法是错误的。它应该是:
如果期望乘积是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。
发布于 2018-12-19 15:09:21
如果你遵循下面的规则,而不是你所说的规则,算法将会工作得很好:
如果期望乘积是r(最初是0),那么如果q是奇数,则p被加到r,如果q是偶数,p被加倍,q被减半(即q变成q/2)
示例代码:
int mult(int p,int q){
int r=0;
if(q%2==1)
{
if(q!=1)
{
r+=p;
//q--;
return r*q;
}
r+=p;
return r*q;
}
else if(q%2==0)
{
if(q!=0)
{
p=p*2;
r+=p;
q=q/2;
return r*q;
}
return 0;
}}
https://stackoverflow.com/questions/53843647
复制相似问题