1

这是过去考试（编程基础）中的一个问题，我不知道如何解决（经过 2 个多小时的尝试）：

编写一个方法void fillingSumOfNeighbours(int[][]m)，假设 m 是一个矩阵，其中最后一列和最后一行已经被填充（非零），用 sum 填充剩余的值m[i][j]=m[i][j+1]+m[i+1][j]+m[i+1][j+1]。这个方法一定是递归的！

到目前为止，我可以以正确的方式填充矩阵，但不能在不使用字段计数器的情况下使递归有限（对我来说似乎不正确，因为使用字段计数器来停止递归需要定义的类）。有没有办法定义直接递归方法只能在该方法内运行的次数？

基本上它应该这样做：

_ _ 1
_ _ 1
1 1 1 

_ _ 1
_ 3 1
1 1 1

_ 5 1
_ 3 1
1 1 1

_ 5 1
5 3 1 
1 1 1

13 5 1
5  3 1
1  1 1
4

3 回答 3

2

通过查看您的示例和问题陈述，很明显，您需要运行 3 次递归：-

  • 一种用于垂直向上移动
  • 一种用于水平左移
  • 一个用于对角线左侧。

因此，要管理该运动，您还必须将索引传递给您的方法。我希望你被允许修改方法。

所以，基本上你的递归调用将是这样的： -

fill(arr, row - 1, col);
fill(arr, row, col - 1);
fill(arr, row - 1, col - 1);

假设fill您的方法采用 3 个参数：-

  • int[][] arr
  • int row
  • int col

现在，如您所见，第一个调用正在减少行值，从而向上移动索引。第二个电话向左移动。最后一次调用将需要覆盖top-left最多的索引。

在您的方法中，您只需使用公式编写逻辑来填充您传递的当前索引。是的，不要忘记基本条件，即当任一索引小于 0 时，立即返回。

所以，这就是你的方法的样子： -

public static void fill(int[][] arr, int row, int col) {
    arr[row][col] = arr[row][col + 1] + arr[row + 1][col] + arr[row + 1][col + 1];
    if (row <= 0 || col <= 0) {
        return;
    }
    fill(arr, row - 1, col);
    fill(arr, row, col - 1);
    fill(arr, row - 1, col - 1);
}

初始调用如下： -

fill(arr, row - 2, col - 2);

哪里row是最大行大小和col最大列大小。

于 2013-01-05T21:10:00.347 回答
1 
preencheComSomaVizinhos (int[][]m){
    get(m,0,0)
}
get(int[][]m, int i, int j){
    if(!(i == m.length-1 || j==m.length-1)){
        m[i][j] = get(m, i, j+1) + get(m,i+1,j)+get(m,i+1,j+1);

    }
    return m[i][j]; 
}
于 2013-01-05T20:57:32.607 回答
0

我会把它写成在行号和列号上递归，当你在最后一行时有一个基本情况。如果数组是方形的，你只需要一个递归参数（我假设是这种情况）。

在递归的过程中，你会遇到这样的情况：

0 0 0 0 0 *
0 x + + + *  <- currently working on row k
0 - & & & *
0 - & & & *
0 - & & & *
* * * * * *

在你开始之前，*s 已经被填满了。然后调用带有参数的递归函数k+1，它会填充所有标记的单元格&。然后，您必须手动填写标有 s 的行、标有+s 的列-以及标有 的角上的单个单元格x。然后您将控制权传回给调用您的函数，该函数将填充标记为 的其余单元格0。

我已经有一年没有真正写过 Java了，请原谅我草率的语法！

void fillNeighbours(int[][] m) {

  int size = m.length;

  run(m, size, 0);  

}

void run(int[][] m, size, row) {

  if (row < size) {

    // fill the rest of the rows and cols
    run(m, size, row+1)

    // fill the column and row for this iteration
    for (int i = 1; size-i > row; i++) {
      m[row][size-i] = m[row+1][size-i] + m[row][size-i+1];
      m[size-i][row] = m[size-i+1][row] + m[size-i][row+1];
    }

    // fill the corner cell
    m[row][row] = m[row+1][row] + m[row][row+1];

  } else {
    // Base case, do nothing
  } 

}
于 2013-01-05T21:24:28.720 回答