간단한 나누기 및 정복 예

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

내가 배열을 복용하는 간단한 예제를 찾고 있어요 getSum.sumArray (getSum.java:16)에서 "주"스레드에서 오류 예외 java.lang.StackOverflowError의

입니다 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]) 
} 

당신은 너무에 문제가 두 개의 작은 문제로 분할하는 방법을 참조 할 수 있습니다 (번호 X를 배열 A,) 찾기 , 그것이 정지 조건 'n == 1'에 도달 할 때까지 호출 트리 위로 결과를 반환하기 시작합니다. 이것은 의사 코드이므로 사용하는 프로그래밍 언어에 개념을 적용해야합니다.

Answer 2

배열을 침투하는 방법을 완전히 이해하지 못한 다음 다시 분할하십시오.

재귀를 사용하면 그렇게 할 수 있습니다.