时间戳

首页 > 解决方案 > 在 C# 中通过递归对矩阵求和子

c# - 在 C# 中通过递归对矩阵求和子

问题描述

我试图在不使用循环的情况下解决问题，但我找不到方法......

让我们以这个数组为例：（假设有随机值）

1, 2, 3, 4, 5
2, 3, 4, 5, 6
3, 4, 5, 6, 7
4, 5, 6, 7, 8
5, 6, 7, 8, 9

通过发送（行：2，列：1），我想获得以下总和：

1, 2
2, 3
3, 4

我写了这个递归函数来解决这个问题：

static int Func(int[,] matrix, int row, int column)
{
    if (row == -1 || column == -1)
        return 0;

    int result = 0;

    for (int i = 0; i <= column; i++)
    {
        result += matrix[row, i];
    }

    return result + Func(matrix, row - 1, column);
}

那行得通，但我想用额外的函数调用替换循环......

标签： c#algorithmrecursionfunc

解决方案

您总是可以尝试通过考虑处理单个条目然后将其余条目留给下一个递归调用处理的函数来简化这样的递归。

可以解决您的情况的基本想法：尝试从矩阵的右下角到左上角的数字求和（这样您可以使用行/列的负索引来验证何时到达矩阵的边界）。

因此，在您的具体情况下，该想法有三个关键点：

  • (A) 该函数应返回位于矩阵给定(row,col)位置的数字，加上求和序列中从下一个数字开始的序列之和：即 sum(row, col) = mat[行，列] + 总和（行，列-1）。
  • (B) 通过重复执行 (A) 递归调用，在某些时候该列将是负数......当这种情况发生时，我们应该转到我们正在处理的当前行上方的行，并将该行上的所有列相加线。
  • (C) 在某个时刻，所有的矩阵将被求和，并且行数将为负数。那是算法需要结束递归的时候，因为程序已经计算了它需要计算的整个输入。

所以你可以这样写：

static int Func(int[,] matrix, int row, int column, int maxColumn)
{
    // (C) All rows have been processed successfully: stop the recursion.
    if (row < 0)
        return 0;

    // (B) All columns in the current line have been processed: go to the next row
    // which you need to sum
    if (column < 0)
        return Func(matrix, row - 1, maxColumn, maxColumn);

    // (A) The basic definition of your recursion
    return matrix[row, column] + Func(matrix, row, column - 1, maxColumn);
}

在您的输入示例中，您可以简单地将其称为：

Func(yourMatrix, 2, 1, 1);

请注意，要使该算法起作用，您需要maxColumn为函数传递一个额外的变量，以了解在转到需要处理的下一行时它应该使用的列数。maxColumn和参数显然需要在你第一次调用函数column时总是相等的。Func()

推荐阅读