Simple Divide and Conquer Example

问题:

Here is my test divide and conquer program, but it gives me an error. I am heading in the right direction?

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

Here is the error Exception in thread "main" java.lang.StackOverflowError at getSum.sumArray(getSum.java:16)

I am looking for a simple example of taking an array of 16 and breaking it down to base case 4. I am having trouble completely understanding how to spit the array, then split it again. then combine all the splits in the end.

回答1:

You can use recursion for divide and conquer. You keep recursing on smaller arrays until you find a match, then climb up the recusion tree.

For example: find if a number is in the array using the recursive function 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])
}

You can see how the problem is split into two smaller problems, and so on, until it reaches the stop condition 'n==1' then it starts returning results up the call tree. This is pseudo code, you will have to adapt the concept to the programming language you are using

回答2:

Having trouble completely understanding how to spit the array, then split it again.

Using Recursion you can do that.