java - 使用数组计算斐波那契数

Question

//我正在学习 Java 中的递归。 /** 我试图通过使用数组来计算第 45 个斐波那契数以缩短所用的时间，但效果不佳...... 错误信息: 线程“main”中的异常 java.lang.ArrayIndexOutOfBoundsException: 45 在 Auf1.fib2(Auf1.java:25) 在 Auf1.main(Auf1.java:49) **/

public class Auf1 {

    public static long[] feld;

        public static long fib2(long n) { 
            if ((n == 1) || (n == 2)) {
                return 1;
            } else {
                if (feld[(int) n] != -1) {
                    return feld[(int) n];
                } else {
                    long result = fibo(n - 1) + fibo(n - 2);
                    feld[(int) n] = result;
                    return result;
                }
            }
        }

public static void main(String[] args) {
     long n = 45;
     feld = new long[(int) n];
        for (int i = 0; i < n; i++) {
            feld[i] = -1;
        }
        long result = fib2(n);
        System.out.println("Result: " + result);
    }
}

Answer 1

数组索引从 0 开始。 您创建一个大小为 45 的数组。有效的数组索引为 0,1...44。在第一次调用 fib2 时，检查 array[45] 是否等于 -1。 array[45] 不是有效索引，将导致 IndexOutOfBoundException。

更改以下行:

(feld[(int) n] != -1)

到

(feld[(int) n - 1] != -1)

和行

feld[(int) n] = result 

到

feld[(int) n - 1] = result;

顺便说一句，存在语法错误。递归调用应该是 fib2(n-1) + fib2(n-2) 而不是 fibo(n-1) + fibo(n-2)