当一个或两个因素为负时,如何进行递归乘法?

问题描述 投票:8回答:8
public static int multiply2(int num1, int num2) {
    if (num1 == 0 || num2 == 0) {
        return 0;
    }

    else {
        return num1 + multiply2(num1, num2 - 1);
    }

}

我刚刚意识到制作一个可以确定两个数字的乘积的程序会很有趣,其中一个或两个都是负数。我想用递归乘法(基本上重复加法)来做。有人可以帮帮我吗?谢谢!

java
8个回答
3
投票
if (num1 == 0 || num2 == 0) {
        return 0;
}

else if( num2 < 0 ) {
    return - num1 + multiply2(num1, num2 + 1);
}

else {
    return num1 + multiply2(num1, num2 - 1);
}

3
投票
else if (num1 < 0 || num2 < 0) {
    int signum1 = num1 < 0 ? -1 : 1;
    int signum2 = num2 < 0 ? -1 : 1;
    return signum1 * signum2 * multiply(signum1 * num1, signum2 * num2);
} else {

这样的事情

注意:有一个signum函数和Math.abs可以用于signum * num


1
投票

您将测试它是否为负数并减去而不是添加:

public static int multiply2(int num1, int num2) {
    if (num1 == 0 || num2 == 0) {
        return 0;
    }
    else if(num2 > 0){
        return num1 + multiply2(num1, num2 - 1);
    }
    else{
        return -num1 + multiply2(num1, num2 + 1);
    }
}

1
投票

如果数字是-ve,则需要添加。如果你看到我们只添加第一个数字,那么我们必须达到的第二个数字条件是0。因此,如果负面do+1,如果积极做-1

        else if (num2 < 0)
            return -num1 + multiply2(num1, num2 + 1);
         else
            return num1 + multiply2(num1, num2 - 1);

    System.out.println(multiply2(5, -6));-->-30
    System.out.println(multiply2(5, 6));-->30

1
投票

不是在主递归部分中多次处理它,更好的想法是将它作为边缘情况处理并将其转换为常规情况,因为在数学运算完成之前,分配和返回都不会发生。为此,我将y转换为正数,然后在结果返回到负数情况后将整个函数的结果否定。

这是我的解决方案:

private static int product(int x, int y) {
    // Negative start edge case
    if (y < 0) {
        return -1 * product(x, y * -1);
    }

    // Edge case (only for speed)
    if (y == 0 || x == 0) {return 0;}

    // Base case
    if (y == 1) {
        return x;
    }

    // Recursion
    return x + product(x, y-1);
}

值得注意的是,即使没有0边缘情况,该方法仍然可以工作。在这种情况下,该方法只需要做一些不必要的结果。

测试已经得出结论,该方法适用于0和/或负的参数。


0
投票
public static int multiply2(int num1, int num2) {
    if (num1 == 0 || num2 == 0) {
        return 0;
    }

    else {
        int sign2=(int)(Math.abs(num2)/num2);
        return sign2*num1 + multiply2(num1,num2-sign2);
    }

}

0
投票

大卫华莱士的答案是好的,但如果输入是(1,124)或(-1,124),递归的深度(方法调用自身的次数)将是123,效率不高。我建议添加几行来测试1或-1。这是一个完整的例子:

public class Multiply {

    public static void main(String[] args) {

        System.out.print("product = " + multiply(1, 124) );
    }

    public static int multiply(int x, int y) {
        System.out.println("Multiply called: x = " + x + ", y = " + y);

        if (x == 0 || y == 0) {
            System.out.println("Zero case: x = " + x + ", y = " + y);
            return 0;
        }

        else if (x == 1 && y > 0) {
            return y;
        }

        else if (y == 1 && x > 0) {
            return x;
        }

        else if ( x == -1 && y > 0) {
            return -y;
        }

        else if ( y == -1 && x > 0) {
            return -x;
        }

        else if( y == -1 ) {
            System.out.println("y is == -1");
            return -x;
        }

        else if( x == -1 ) {
            System.out.println("x is == -1");
            return -y;
        }

        else if( y < 0 ) {
            System.out.println("y is < 0");
            return -x + multiply(x, y + 1);
        }

        else { 
            System.out.println("Last case: x = " + x + ", y = " + y);
            return x + multiply(x, y - 1);
        }
    }
}

输出:

Multiply called: x = 1, y = 124
product = 124

0
投票

好的,所以我实际上是在做这个作业。递归解决方案实现 - 或使用 - 确定需要继续的基本案例。现在,你可能会说,“这对地球意味着什么?”好吧,用外行人的话来说,这意味着我们可以简化我们的代码(在现实世界中,节省我们的软件一些开销) - 稍后我会解释。现在,问题的一部分是理解一些基本的数学,即负数加负数是负数或减去正数(-1 + -1 = -2),这取决于你所说的数学老师(我们会看看在下面的代码中发挥作用。

现在,这里有一些争论。我将在后面写些关于它的内容。

这是我的代码:

public static int multiply(int a, int b)
{
    if (a == 0) 
    {
        return result;
    } 
    else if (a < 0) // Here, we only test to see whether the first param.  
                    // is a negative
    {
        return -b + multiply(a + 1, b); // Here, remember, neg. + neg. is a neg.
    }                                   // so we force b to be negative.
    else 
    {
        result = result + b;
        return multiply(Math.abs(a - 1), b);
    }
}

请注意,有两种不同的方式,这里:

  1. 由于第一段中的数学原理,上面的代码不测试第二个参数以查看第二个参数是否为负(a < 0)(参见第一段中的粗体文本)。基本上,如果我知道我乘以(y)乘以负数(-n),我知道我正在接受-n并将它们加在一起y次;因此,如果multiplicand or multiplier是负数,我知道我可以取任何一个数字,使数字为负,并将数字反复添加到自身,例如-3 * 7可以写成(-3)+( - 3)+( - 3)+( - 3)......等或(-7)+( - 7)+( - 7)
  2. 现在这是什么辩论:上面的代码没有测试看第二个数字(int b)是否是0,即乘以0。为什么?嗯,这是个人选择(有点)。这里的争论必须权衡某事物的相对重要性:每种选择的开销(或者是否运行等于零的测试)。如果我们测试一边是否为零,每次进行multiply的递归调用时,代码必须计算表达式;但是,如果我们不测试等于零,那么代码会多次添加一堆零。实际上,这两种方法“权衡”相同 - 因此,为了节省内存,我省略了代码。
© www.soinside.com 2019 - 2024. All rights reserved.