用递归函数C++实现乘法

提问者：小点点

用递归函数C++实现乘法

我做了一个递归函数来计算x*y，其中x和y都是整数（x和y>=0)。我的公式是:x*y=

0，如果x等于0
(x>>1)*(y<<1)，如果x是偶数
(x>>1)*(y<<1)+y，如果x是奇数

“<<<” 和“>>” 是左移位和右移位按位运算符。下面是我的代码:

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)值，但是当我测试时它们都是错误的，我不知道为什么。我做错了什么？我该怎么解决这个问题？

共3个答案

匿名用户

您没有在此处正确检查x是否为奇数:

else if (x % 3 == 0) {  // e.g. fails on x = 1

相反，你需要做的是

else if (x % 2 == 1) {

这是一个演示。

请注意，这使得以下else检查x的偶数值变得多余:

else if (x % 2 == 0) {  // can just be an unconditional else

另外，由于您是从x==0和x%2==1分支返回，因此也可以删除else条件。您还可以将重复的代码剔除，使函数更简单，如下所示:

int multiply(int x, int y) {
    if (x == 0) return 0;
    if (x % 2 == 1) 
        return (multiply(x >> 1, y << 1) + y);
    else 
        return multiply(x >> 1, y << 1); 
}

这是一个演示。

匿名用户

您的问题是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;
}

以下是Andy建议的超快版本:

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;
}

匿名用户

这是我觉得进行递归乘法最简单的方法。如果这对你来说足够有效，一定要让我知道。

#include<iostream>
using namespace std;
 
float multiply(float a, float b) {
 
    //no zeros bro
    if (b == 0)
        return 0;
 
    //let the recursion begin
    if (b > 0)
        return x + multiply(a, b - 1);
 
    //negatives stay away pliz
    if (y < 0)
        return -multiply(a, -b);
}
 
int main() {
    float a, b, result;
    cout << "Enter the two numbers";
    cin >> a >> b;
 
    result = multiply(a, b);
 
    //And the result is.................
    cout << result;
    return 0;
}

用递归函数C++实现乘法

共3个答案

相关问题