c - 在不多次添加角的情况下对矩阵的周长求和

Question

我正在尝试使用递归对大小为 n 的矩阵的周长求和。 (没有多次添加角)

我写的是无限循环，不排除角点。如何停止无限循环并排除角落？

int
sumPerimeter(int** matrix, int i, int j, int height, int width)
{
    if (i == 0 && j == 0)
      return matrix[i][j] + sumPerimeter(matrix, i + 1, j, height, width);

   if (i == height && j == 0)
      return matrix[i][j] + sumPerimeter(matrix, i, j + 1, height, width);

   if (i==height&& j == width)
      return matrix[i][j] + sumPerimeter(matrix, i - 1, j, height, width);

   if (i == 0 && j == width)
      return matrix[i][j] + sumPerimeter(matrix, i, j - 1, height, width);
}

我决定将其分成几个阶段以使其更容易，下面的代码是我目前的尝试。当我使用 visual studio 单步执行它时，它起作用了，但它总是返回矩阵中的第一个数字。

   int
   sumRight(int** matrix, int i, int j, int height, int width,int count)
   {


   if (0 > width)
      return 0;

   if (j > width - 1)
      return count;

      int sum = matrix[i][j];
       count = sum + count;

   sumRight(matrix, i, j + 1, height, width,count);



   return count;

}

我弄清楚了为什么它没有返回正确的值。但我不知道如何让它不多次计算角点。对此有任何建议，我们将不胜感激。

Answer 1

如果您必须为此使用递归(这可能是个坏主意，因为您得到的很少，但出于教育目的可能没问题¹)，您可以选择一个简单的方法。

假设基本情况是高度为零的矩阵，重复情况是将第一行的总和与矩阵其余部分的总和相加。换句话说，类似于以下伪代码:

def sumOfMatrix (matrix m, int row, int height, int width):
    # No rows left, return zero.

    if row == height:
        return 0

    # Get sum of first row.

    sum = 0
    for col in 0..width-1 inclusive:
        sum = sum + m[row][col]

    # Return that plus sum of rest of matrix.

    return sum + sumOfMatrix (m, row+1, height, width)

---

如果你真的想变得聪明，对于“聪明”这个词的一些奇怪的定义:-)，你可以做两种完全不同类型的递归，一种用于一行，另一种用于矩阵:

def sumOfRow (matrix m, int row, int col, int width):
    # No columns left, return zero.

    if col == width:
        return 0

    # Get value plus sum of rest of row.

    return m[row][col] + sumOfRow (m, row, col+1, width)

def sumOfMatrix (matrix m, int row, int height, int width):
    # No rows left, return zero.

    if row == height:
        return 0

    # Get sum of this row plus sum of all other rows.

    return sumOfRow (m, row, 0, width) + sumOf (m, row+1, height, width)

---

¹ 如前所述，这可能是递归的错误用例，因为您可以简单地执行紧凑的迭代解决方案:

def sumOfMatrix (matrix m, int height, int width):
    sum = 0
    for row = 0..height-1 inclusive:
        for col = 0..width-1 inclusive:
            sum = sum + m[row][col]
    return sum

但是，如果您需要一个递归解决方案(因为您是自学递归，或者您的教育者没有能力思考更好的现实世界问题)，上面的递归代码应该足够了来帮助你。