使用递归调用而不使用循环和乘法来查找数值。

huangapple go评论73阅读模式
英文:

Using recursive calls without loops and multiplication to find values

问题

考虑这个问题:

我们有一个由方块组成的三角形。最顶行有1个方块,下一行有2个方块,再下一行有3个方块,依此类推。请递归地计算(不使用循环或乘法)在给定行数的情况下,这样一个三角形中总共的方块数。

我对这个问题的方法是这样的:

public int triangle(int rows) {
  if(rows == 0 || rows == 1 ) {
    return rows;
  } else {
    return triangle(rows-1) +2;
  }
}

这个程序对于数值最多为3的情况工作得很好,但是当数值超过3时,输出的结果是错误的(计算错误/递归调用错误)。我错过了什么?

非常感谢!

英文:

Consider this problem:

>We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

My approach to this problem was this

public int triangle(int rows) {
  if(rows == 0 || rows == 1 ) {
    return rows;
  } else {
    return triangle(rows-1) +2;
  }
}

The program works fine for values up to the number 3 but then the values that should come out are wrong (the calculation is wrong/recursive call). What am I missing?

Thank you in advance!

答案1

得分: 1

你正在对递归调用添加了2,尝试添加 rows

示例:

public int triangle(int rows) {
  if (rows < 2)
    return rows;
  else
    return triangle(rows - 1) + rows;
}
英文:

You're adding 2 to your recursive invocation, try to add rows.

Example:

public int triangle(int rows) {
  if (rows &lt; 2)
    return rows;
  else
    return triangle(rows - 1) + rows;
}

答案2

得分: 1

你的想法是对的。你从“底部”行开始,在每个递归调用中,你都会移动到上面的一行,直到达到仅包含一个块的顶行。你唯一的问题是,你需要加的不是2,而是行数。

(在代码后的解释。)

public int triangle(int rows) {
    if (rows < 1) {
        throw new IllegalArgumentException("行数必须是正数。");
    }
    if (rows == 1) {
        return 1;
    } else {
        return rows + triangle(rows - 1);
    }
}

让我们以一个简单的例子来说明,初始调用方法triangle()的值为4。这意味着底部一行包含四个块,上面一行包含三个块。因此上述代码中的最后一个返回语句意味着:
返回我所在行的块数以及三角形中在我行上方的所有块数。

因此,方法triangle()使用值3调用自身。同样的操作,返回我所在行的块数以及三角形中在我行上方的所有块数。

最终,你会到达顶行,那里只有一个块,上面没有行。因此你不想再进行递归调用,所以你只需返回行中的块数,即为1。

因此,1被返回给调用它的方法,后者又返回它的行数,即2,再加上被调用方法返回的1,总共为3,依此类推,直到返回到最初的调用。

英文:

You have the right idea. You start from the "bottom" row and in each recursive call you move to the row above until you reach the top row, which contains only one block. Your only problem is that instead of adding 2, you need to add the number of rows.
(Explanations after the code.)

public int triangle(int rows) {
    if (rows &lt; 1) {
        throw new IllegalArgumentException(&quot;&#39;rows&#39; must be positive.&quot;);
    }
    if (rows == 1) {
        return 1;
    }
    else {
        return rows + triangle(rows - 1);
    }
}

Let's take a simple example where you initially call the method triangle() with a value of 4. That means that the bottom row contains four blocks and the row above that contains three blocks. So the last return statement in the above code means:
Return the number of blocks in my row plus all the blocks that are above my row in the triangle.

So the method triangle() calls itself with the value 3. Again the same thing, return the number of blocks in my row plus all the blocks that are above my row in the triangle.

Eventually you get to the top row where there is only one block and no rows above it. Hence you don't want to make another recursive call, so you just return the number of blocks in the row, which is one.

So 1 is returned to the method that called it which, in turn returns its number of rows, i.e. 2, plus the 1 that the invoked method returned for a total of three and so on, until you return to the initial invocation.

答案3

得分: 0

以下是翻译好的内容:

我会将其写成:

public int triangle(int rows) {
    return (rows <= 0) ? 0 : rows + triangle(rows-1);
}
英文:

I'd write it as:

public int triangle(int rows) {
    return (rows &lt;= 0) ? 0 : rows + triangle(rows-1);
}

huangapple
  • 本文由 发表于 2020年9月24日 01:03:03
  • 转载请务必保留本文链接:https://go.coder-hub.com/64032913.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定