我做了一个递归函数来计算x * y,其中x和y都是整数(x和y> = 0)。我的公式是:
x * y =
“<<”和“>>”是左移和右移按位运算符。这是我的代码:
int multiply(int x, int y) {
int y1 = 0;
if (x == 0) return 0;
else if (x % 3 == 0) {
y1 = y;
x = x >> 1;
y = y << 1;
return (multiply(x, y) + y1);
}
else if (x % 2 == 0) {
x = x >> 1;
y = y << 1;
return multiply(x, y);
}
}
上面的递归函数应该返回(x * y)值,但是当我测试时它们都是错误的,我也不知道为什么。我做错什么了?我怎样才能解决这个问题?
最佳答案
您的问题是x % 3
,如果x = 5
会怎样?你跳过它。这是代码的改进版本。
int multiply(int x, int y) {
if (x == 0)
return 0;
else if (x % 2 == 1)
return (multiply(x >> 1, y << 1) + y);
return multiply(x >> 1, y << 1);
}
甚至这个:int multiply(int x, int y) {
if (x == 0)
return 0;
int m = multiply(x >> 1, y << 1);
if (x % 2 == 1)
m += y;
return m;
}
这是安迪建议的超快速版本:int multiply(int x, int y) {
if (x == 0)
return 0;
int m = multiply(x >> 1, y << 1);
if (x & 1)
m += y;
return m;
}
作为速度的挑战,这是非递归版本:int multiply (int x, int y) {
int y1 = 0;
for (; x > 0; x = (x >> 1), y = (y << 1))
if (x&1)
y1 += y;
return y1;
}
注意:我知道这个问题与递归方法有关,但正如我编写非递归算法的挑战一样。
关于c++ - 使用递归函数C++进行乘法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63206258/