java - 学习分而治之算法

Question

我一直在尝试学习分而治之的算法，并且我已经想出了我认为可以使用 java 实现的算法。该算法应该采用大小为 n 且以 2 为基数的数组。它应该将数组划分为以 4 为基数的情况，然后将索引的值相加。然后它将所有这些加在一起以找到整个数组的总和。这是我迄今为止在 java 中所做的以及我的错误。我至少走在分而治之算法的正确轨道上吗？

引发异常:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 8
at getSum.sumArray(getSum.java:17)
at getSum.sumArray(getSum.java:21)
at getSum.main(getSum.java:7)

这是代码:

public class getSum {
    static int sum = 0;
    public static void main(String[] args) {
            int[] numbers = {2,2,2,2,2,2,2,2};
            int amount = 0;
           amount = sumArray(0,numbers.length,numbers);
           System.out.print(amount);
    }

    public static int sumArray(int first, int last, int[] A){
        int index = last - first;
        if(index == 1){
            return sum;
        }else if(index <= 4 && index > 1){
            for(int i = first; first < last; i++){
                sum += A[i];
            }
            return sum;
        }
        return (sumArray(first, last / 2, A) + sumArray(last / 2, A.length, A));
    }
}

Answer 1

您需要更改:

for(int i = first; first < last; i++){

至:

for(int i = first; i < last; i++){

当您仅递增 i 时，您会不断比较 first 和 last

正如@Some1.Kill.The.DJ 指出的，

sum 应该是方法 sumArray

的一部分