java - 递归到普通循环转换

Question

我有一个实际上计算 someValues 的方法。该方法如下。

public static double sum(int z, int x, int y)
    {
        double count = 0.0;
        if (x == 0)
        {
            if (z <= 0) return 1.0;
            return 0.0;
        }
        for (int i = 1; i <= y; i++)
        {
            count += sum(z - i, x - 1, y);
        }
        return count;
    }

我只是想将此方法从递归转换为正常迭代。或者如果可能的话，某个线性方程。请帮助我。

Answer 1

所以这并不漂亮，但它无需递归即可工作。另外，由于以下原因，我将返回类型从 double 更改为 int:

public static int sum(int z, int x, int y)
{
    // Compute number of calls
    int[][] calls = new int[x+1][x*y+1];
    calls[0][0] = 1;
    for (int i = 0; i < x; i++) {
        for (int j = 0; j <= x*y; j++) {
            for (int target = j+1; target <= j+y && target <= x*y; target++) {
                calls[i+1][target] += calls[i][j];
            }
        }
    }

    // Return count of last column where z <= 0
    int result = 0;
    for (int j = x*y; z-j <= 0; j--) {
        result += calls[x][j];
    }
    return result;
}

要了解这一点，请查看这张高科技 Excel 工作表:

此图表说明了 sum(3, 3, 3) 的调用。水平方向上你看到的 x 和垂直方向上你看到的 z 都变小了。 y 为 3，未更改。

左上角1表示调用 sum(3, 3, 3) 一次。然后，此调用生成三个子调用(因为 y=3): sum(2, 2, 3) , sum(1, 2, 3)和sum(0, 2, 3) 。这三个调用可在下一列中找到(其中 x=2)。

这三个调用中的每一个都会再次产生三个调用，如 x=1 的行所示。这九个调用在 z 方面有些重叠。然后，这 9 个调用中的每一个都会再次生成 3 个调用，从而在 x=0 列中产生 27 个调用。

要获得结果，您只需计算 x=0 列中的所有调用，其中 z <= 0。在此示例中，这是每次调用，因此您得到的结果为 27。对于较大的 z，结果将是更小。