의사 코드/자바 기본 배열 합산 알고리즘

Question

입문 CS 과정에 대한 최종 시험에서 방금이 질문을했습니다. 나는 그것이 꽤 흥미 롭다라고 생각했다. 그러나 나는 그것을 완전히 이해할 수 없었다. 나는 이클립스에서 잠시 동안 코딩을 시도했지만 어디에도 가지 않았다. 나는 Biochem 시험을 곧 치러야하므로 정말 공부해야한다. 그러나 이것은 나를 괴롭 히고있다 ... 나는 도움을 청할 것이라고 생각했다.

질문 - 다음 알고리즘을 작성하십시오. 입력 배열 A와 2 개의 인덱스 start와 stop이 주어지면이 둘 사이의 합계를 계산하십시오. 배열이 정렬되고 모든 요소가 집합 {1, 2, 3}에 속합니다. 이 알고리즘은 O (log (n))에서 실행해야합니다. 그래서 배열을 지정해, {1, 1, 2, 2, 3, 3, 3, 3} 인덱스 1과 5로 이것은 내가 지금까지 무엇을 가지고 11

반환 :

public static int findSum(int[] a, int start, int stop) { 

    int sum = 0; 

    int temp[] = new int[4]; 
    int mid = (start+stop)/2; 

    while (mid > start || mid < stop) { 

     if (a[mid+1]-a[mid] != 0) { 
      temp[mid+1] = mid+1; 
      temp[mid] = mid; 
      mid++; 
     } 
     else { 
      findSum(a, start, mid); 
      findSum(a, mid+1, stop); 
     } 
    } 
    for (int i = 4; i > 0; i--) { 
     if (temp[i] == 0) { 
      temp[i] = temp[i-1]; 
     } 
    } 
    for (int i = 1; i < 4; i++) { 
     sum += i*(temp[i]-temp[i-1]); 
    } 
    return sum; 
} 

내 논리가 맞다면 모르겠다.하지만 내 생각은 숫자가 바뀌는 배열에서 인덱스를 찾고 배열을 두 부분으로 나누는 재귀 적 방식으로 그렇게하는 것이다. 이 인덱스를 사용하면 숫자가 나타나는 빈도를 결정할 수 있으므로이 빈도로 숫자를 곱하고 합계를 계산하기 위해 이들을 더합니다.

내 알고리즘은 거기에 많은 결함을 가지고 확신 ... 이제 데이터가 만 1, 2, 3있을 것이라는 점을 포함하도록 질문을 업데이트했는지

Answer 1

: 당신은 할 수 단순히 반복적으로 귀하의 범위에서 어떤 번호를 확인하십시오 :

public static int findSum(int[] a, int start, int stop) { 
    if (start < 0 || start >= a.length || stop < 0 || stop >= a.length) { //bounds check 
     return 0; 
    } 
    if (start == stop) { //return the number! 
     return a[start]; 
    } else if (a[start] == a[stop]) { //catch for some quick math, return amount of values * the value 
     return a[start] * (stop - start + 1); 
    } else { 
     int mid = start + ((stop - start) >>> 1); //This is the middle point between start and stop 
     return findSum(a, start, mid) + findSum(a, mid + 1, stop); 
    } 
}