0

这是我的测试分治程序，但它给了我一个错误。我正朝着正确的方向前进？

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));
    }
}

这是 getSum.sumArray(getSum.java:16) 线程“main”java.lang.StackOverflowError 中的错误异常

我正在寻找一个简单的例子，将 16 个数组分解为基本情况 4。我无法完全理解如何吐出数组，然后再次拆分它。然后最后合并所有的拆分。

4

2 回答 2

1

您可以使用递归进行分而治之。你一直在较小的数组上递归，直到找到匹配项，然后爬上递归树。

例如：使用递归函数 isIn(Number x, Array a) 查找一个数字是否在数组中

Boolean isIn(Number x, Array a) {

   n = a.size
   if n==1 then return a[0]==x
   else
      return isIn(x, a[0:n/2]) or isIn(x,a[n/2:n])
}

您可以看到问题是如何分成两个较小的问题，依此类推，直到它达到停止条件“n==1”，然后它开始在调用树上返回结果。这是伪代码，您必须使概念适应您使用的编程语言

于 2013-02-19T04:57:20.200 回答
1

无法完全理解如何吐出数组，然后再次拆分。

使用递归你可以做到这一点。

于 2013-02-19T04:50:54.797 回答