c - 使用一维数组计算矩阵值

Question

问题是:

给定非负整数 m 和 n，迭代计算 A(m,n):

A(m,n) = A(m, n-1) + A(m-1, n), m, n >= 0
A(m,n) = m - n, if m < 0 or n < 0

问题的第一部分使用二维数组(m+1 乘以 n+1 大小)来填充数组，并且 (m,n) 处的位置包含该值。这是最简单的部分。

但是第二部分指出:

设计一种算法来仅使用大小为 min{m; 的一维数组来实现此目的仅 n} + 1。为这样的算法实现一个 C 程序。

我的想法:为了计算第一行和第一列，我使用以下函数。

int Firsts(int x, int y)
{
    int total, order;

    if (x == 0)
    {
        if (y % 2 == 1)
        {
            order = (y/2) + 2;
            total = y * order;
        }
        else
        {
            total = (y * ((y/2) + 1)) + (y/2);
        }
        return -total;
    }
    else
    {
        if (x % 2 == 1)
        {
            order = (x/2) + 2;
            total = x * order;
        }
        else
        {
            total = (x * ((x/2) + 1)) + (x/2);
        }

        return total;
    }
}

现在我需要向下和向右移动(使用上面的一个和左边的一个)。但是，我不知道如何迭代地执行此操作。我使用了 min 函数来初始化数组大小，但这就是我到目前为止所拥有的。

Answer 1

您应该通过在纸上手动执行算法来“跟踪”2D 程序。如果您不知道发生了什么，或者无法手动完成，则无法更改算法。

一旦您手动完成此操作，可能至少使用不同的数字几次，您应该能够观察到您只需要一些“旧”(以前的)数字即可找到新值。您很可能会发现您只需要前一行和/或当前行的一些内容(这是因为 -1 的原因)。一旦您了解发生了什么，您就可以对其进行编码。