java - 递归和金字塔

Question

我正在做一项实现递归的作业，但很难理解如何通过递归来实现这一点。

我需要能够检测数组是否具有多个列/行，然后计算每个列/行的权重..

这里是这样说的:

The weight supported at each object is the weight of the object itself, plus 
half of the supported weight of the objects above it.

The weight supported by A is the weight of A itself.

The weight supported by B is the weight of B plus 1/2 the weight of A.

The weight supported by C is the weight of C plus 1/2 the weight of A.

The weight supported by E is the weight of E itself, plus 1/2 of the weight         
supported by B and 1/2 of the weight supported by C.

这是我到目前为止所拥有的，我测试了是否只有一个元素并返回它:

public static double computePyramidWeights(double [][] weights, int row, int col){
    if (row == 0 && col == 0) {
        return weights[0][0];
    }

    return 1.0; //I know this should be where the recursive goes
}

鉴于前。像:

    A
  B    C
D    E    D

Answer 1

这依赖于我的假设，即金字塔在二维数组中的结构为 {{A},{B,C},{D,E,F}}，但您没有指定。

public static double computePyramidWeights(double [][] weights, int row, int col){
    if (row < 0 || col < 0 || col >= weights[row].length) {
        return 0.0;
    }
    return weights[row][col]
            + 0.5 * computePyramidWeights(weights, row-1, col)
            + 0.5 * computePyramidWeights(weights, row-1, col-1);
}

请注意，此函数专注于计算，而不是验证输入。例如，如果该算法的调用者请求不存在的行的权重，则可能会引发异常。然而，抛出异常是一个完全合理的结果!为什么？因为它表明存在需要修复的编码错误，并且您不应掩盖不必要的程序员错误。

但是，如果您需要验证用户输入(例如，用户正在输入列和行)，则可以(并且应该)使用单独的函数来完成:

// demonstrate how to do a separate input validity check
public static boolean validRowCol(double [][] weights, int row, int col) {
    // return false if there is no such weights[row][col]
    return row >= 0 && col >= 0 && row < weights.length && col < weights[row].length;
}