Simple Divide and Conquer Пример

Question

Вот моя тестовая программа деления и покорения, но это дает мне ошибку. Я направляюсь в правильном направлении?

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

Здесь ошибка Исключение в потоке «главный» java.lang.StackOverflowError в getSum.sumArray (getSum.java:16)

Ищу простой пример принимает массив из 16 и разбивая его на базовый футляр 4. У меня возникли проблемы с полным пониманием того, как выплюнуть массив, а затем разделить его снова. затем объедините все расщепления в конце.

Answer 1

Вы можете использовать рекурсию для разделения и завоевания. Вы продолжаете рекурсировать на меньших массивах, пока не найдете совпадение, а затем поднимитесь по дереву рекуперации.

Например: найти ли число в массиве с помощью рекурсивной функции ISIN (число х, массив)

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', тогда он начнет возвращать результаты по дереву вызовов. Это псевдокод, вам нужно будет адаптировать концепцию к используемому вами языку программирования

Answer 2

Неполадка, полностью понимающая, как наплевать на массив, а затем разделить его снова.

Использование Recursion позволяет сделать это.