java - 递归和乘法

Question

这可能是伙计们吗？这是我的作业，我的老师显然相信它，但在我看来，在短乘法之外不使用加法或乘法是不可能的。

编写（并提供测试器）递归算法：

整数乘法（整数 x，整数 y）

在不使用 * 运算符的情况下将两个正整数相乘。不要只是将 x 添加到自身 y 次！！！

（提示：编写一个递归方法，将一个整数乘以 0 .. 10 范围内的一个值。然后编写第二个递归方法来实现您在小学学习的乘法算法，将多位数字相乘。）

我的问题是，一旦你分解任何多位数字并开始将它们加在一起，你必须使用大于 10 的数字相乘，即 22 * 6 是 2 * 6 + 20 * 6 ......所以我完全错过了什么吗？

编辑 我想我应该添加这是我拥有的代码，

public int mult(int x, int y){
return x == 0 ? 0 : (mult(x-1, y) + y);
}

这是完美的，但据我理解的说明，这是破坏不只是将 x 添加到自身 y 次。我个人认为不是，但我的老师还不是很清楚，我想知道是否有其他我没有想到的方法，抱歉造成混乱。

Answer 1

是的，这是可能的。是的，我认为你错过了一些东西。试着写下你要遵循的步骤来手动将两个数字相乘，就像你在小学时学到的那样。

然后将这些步骤变成代码。

Answer 2

我对作业的解释是老师希望学生实现一个递归算法来执行网格方法乘法（我们在小学学习的那种）。

例如，乘以 34 x 13 可以这样完成......

  34
* 13
====
  12
  90
  40
+300
====
 442

我无法轻松访问 Java 开发环境，所以我用 C# 编写了代码，但算法应该足够简单，可以转换成 Java。

public int Multiply(int x, int y)
{
    if (x < 0) throw new ArgumentException("must be positive integer", "x");
    if (y < 0) throw new ArgumentException("must be positive integer", "y");

    if (x == 0 || y == 0) return 0; // obvious quick-exit condition

    // integer division
    int xDivBy10 = x / 10;
    int yDivBy10 = y / 10;

    bool xIsSingleDigit = xDivBy10 == 0;
    bool yIsSingleDigit = yDivBy10 == 0;

    // base case
    if (xIsSingleDigit && yIsSingleDigit)
    {
        return MultiplySingleDigits(x, y);
    }

    // otherwise, use grid multiplication recursively
    // http://en.wikipedia.org/wiki/Grid_method_multiplication

    if (xIsSingleDigit) // y must not be a single digit
    {
        return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10);
    }

    if (yIsSingleDigit) // x must not be a single digit
    {
        return (Multiply(xDivBy10, y) * 10) + Multiply(x % 10, y);
    }

    // else - x and y are both numbers which are not single digits
    return (Multiply(x, yDivBy10) * 10) + Multiply(x, y % 10); // the same code as the "if (xIsSingleDigit)" case
}

// technically, this algorith can multiply any positive integers
// but I have restricted it to only single digits as per the assignment's requirements/hint
private int MultiplySingleDigits(int x, int y)
{
    if (x < 0 || x > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "x");
    if (y < 0 || y > 9) throw new ArgumentException("must be in range 0 - 9 (inclusive)", "y");

    if (x == 0 || y == 0) return 0; // base case
    return x + MultiplySingleDigits(x, y - 1);
}

笔记：

• 这种方法仍然使用*运算符，但不用于实际乘以xand y，它用于将其他子乘积增加 10 的倍数
• 此代码的许多部分可以简化/重构，但我特别将它们扩展以使步骤更明显

Answer 3

当然你可以做到。

首先，考虑条件。如果某个数字是 0，那么结果是？对……零。

所以..你会有if x is zero or y is zero return 0

现在..说 X * Y 就像说"X, Y times"，就像写：X + .... + X (Y times)。

所以，你会有类似的东西：

x + multiply(x, y - 1);

您必须考虑其中一个数字为负数的情况（但如果您了解基本情况，我相信您可以轻松做到）。

Answer 4

很容易就可以了。

int multiply(int x, int y) {
    if(y == 0) {
        return 0;
    }
    return x + multiply(x, y - 1);
}

以上没有考虑到 y 为负数的情况，但您不希望我为您完成所有工作。. .

Answer 5

此解决方案适用于 y>=0 和 y<0

public int multiply(final int x, final int y) {
    if (y != 0 && x != 0) {
        if (y > 0) {
            return multiply(x, y - 1) + x;
        } else {
            return multiply(x, y + 1) - x;
        }
    }
    return 0;
}

Answer 6

    static int Multiply(int x, int y)
    {
        if (y > 0 && x > 0)
            return (x + Multiply(x, y - 1));
        if (y < 0 && x > 0)
            return -Multiply(x, -y);
        if (x < 0 && y > 0)
            return -Multiply(-x, y);
        if (x < 0 && y < 0)
            return Multiply(-x, -y);

        return 0;
    }