자바에서 나누기 및 정복 알고리즘

Question

분할 및 정복 기술을 사용하는 Java 알고리즘을 작성해야합니다. n 개의 int 요소가있는 배열 V가 주어진 경우 알고리즘은 두 개의 연속적인 숫자이 나타나는 횟수를 계산해야합니다.

예 : 알고리즘이 V = [3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2] 인 경우 알고리즘은 3을 반환해야합니다. 0, 0, 0은 2 쌍의 연속 0을 갖는 것에 해당합니다.

아래 프로그램을 작성했지만 실행하면 ArrayIndexOutOfBoundsException이됩니다. 내가 뭘 잘못하고 있니? 이상 현상에서 별도로

public class Test { 
    public static void main(String[] args){ 
     int[] v = {3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2}; 
     System.out.println(Conta_Zeri_Main(v)); 
    } 

    public static int Conta_Zeri_Main(int[] v){ 
     if (v.length == 0 || v.length == 1) 
      return 0; 
     else 
      return Conta_Zeri(v, 1, v.length); 
    } 

    public static int Conta_Zeri(int[] v, int i, int f){ 
     int m,result,sx,dx; 
     if (i >= f) 
      return 0; 
     else{ 
      m = (i + f)/2; 
      sx = Conta_Zeri(v, i, m); 
      dx = Conta_Zeri(v, m+1, f); 
      result = sx + dx; 
      if ((v[m] == v[m+1]) && (v[m] == 0)) 
       result++; 

      return result; 
     } 

    } 

} 

Answer 1

은 이미 v[m] = v[m+1] = 0 여부를 확인하지 않는 당신의 코드에서

을 지적했다. 이것은 배열이 2 개의 연속적인 0 사이에 분할 될 때 몇 가지 가능성을 놓칠 것이다.

변경 문 귀하의 경우 :

if ((m < v.length - 1) && (v[m] == v[m+1]) && (v[m] == 0))