学习分而治之算法

我一直在努力学习分而治之的算法，并且我想出了我认为使用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)); 
    } 
}

来源

2013-02-19 shinjuo

你是新来的？至少标出抛出异常的线。 – SJuan76 2013-02-19 07:25:49

'sum'应该是方法'sumArray'的一部分.. – Anirudha 2013-02-19 07:31:24

你需要改变：

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

到：

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

你一直比较first和last，当你仅增加i

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

sum应该是方法的一部分sumArray

来源

2013-02-19 07:31:25 BobTheBuilder

我不能相信我错过了那个。我一直在这方面工作太久 – shinjuo 2013-02-19 07:32:36

不错的观察结果。也'sum'应该是'sumArray'方法的一部分，否则它会加倍.. – Anirudha 2013-02-19 07:32:56

很高兴我可以帮助:) – BobTheBuilder 2013-02-19 07:33:33

学习分而治之算法

回答

相关问题