-1

此代码取自一本通用算法书籍。这本书使用了一个从 1 开始的数组，而不是 0 form但从 0 开始 for p。我该如何解决？

这些是错误：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
at MMC_Test.MemoizedMatrixChain(MMC_Test.java:8)
at MMC_Test.main(MMC_Test.java:36)

和代码在这里

public class MMC_Test {

public static int MemoizedMatrixChain(int[] p) {
    int n = p.length - 1;
    int[][] m = new int[n][n];
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            m[i][j] = Integer.MAX_VALUE;
        }
    }
    return lookUpChain(m, p, 1, n);
}// MemoizedMatrixChain

public static int lookUpChain(int[][] m, int[] p, int i, int j) {
    if (m[i][j] > Integer.MAX_VALUE) {
        return m[i][j];
    }
    if (i == j) {
        m[i][j] = 0;
    } else {
        for (int k = i; k <= j - 1; k++) {
            int q = lookUpChain(m, p, i, k) 
                    + lookUpChain(m, p, k + 1, j)
                    + p[i - 1] * p[k] * p[j];
            if (q < m[i][j]) {
                m[i][j] = q;
            }
        }
    }
    return m[i][j];
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] arr = { 30, 35, 15, 5, 10, 20, 25 };
    int result = MemoizedMatrixChain(arr);
    System.out.println(result);

}// main

}

4

4 回答 4

3

改变 

for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j++) {

到

for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {

而且我还没有正确分析您的代码，但猜测是 

return lookUpChain(m, p, 1, n);

应该 

return lookUpChain(m, p, 1, n - 1);
于 2013-04-07T17:49:13.207 回答
0

通过创建此数组：

 int[][] m = new int[n][n];

您创建了一个多维数组，其范围为：

m[0][0] => m[n-1][n-1]

数组中还有n空格，但是我们从0开始。

您的代码的问题是您<=在 for 循环中使用了一个运算符，而它应该是一个<运算符。

于 2013-04-07T17:49:27.530 回答
0

索引应该一直到 n-1。

public static int MemoizedMatrixChain(int[] p) {
    int n = p.length - 1;
    int[][] m = new int[n][n];
    for (int i = 1; i < n; i++) { //change here
        for (int j = i; j < n; j++) { //change here
            m[i][j] = Integer.MAX_VALUE;
        }
    }
    return lookUpChain(m, p, 1, n);
}// MemoizedMatrixChain
于 2013-04-07T17:50:53.117 回答
0

您有一个从 0 到 (n - 1) 的数组，但您使用从 1 到 n 的索引来访问它。因此，您不使用第一个元素，而是尝试在最后一个元素之后访问不存在的元素。

您可以在错误消息（第 8 行）中看到它首先发生的位置。后面的代码可能会出现更多错误。

根据经验，始终使用从 0 到 (n - 1) 的索引，其中 n 是数组的长度。然后你的循环从 i = 0 开始并在 i < n 时运行。一旦您开始从任一边界添加或减去某些内容，就会感觉不对（除非您不想访问整个数组）。

于 2013-04-07T17:58:13.533 回答