반복적 인 방법으로 N/2에서 N까지 1을 N/2에서 N을 계산하여 계산합니다.

Question

1,2,3에서 N까지의 합계를 계산하는 재귀 적 방법을 만드는 데 문제가 있습니다. (N/2 + 1 ... N)으로 (1,2,3 ... N/2)를 더한다.

나는 이것이 잘못된 생각

public static void main(String[] args) { 

    System.out.println(sum(10, 1)); 
} 

public static int sum(int n, int start) { 

    if (start == n){ 
     return n; 
    } 

    if (start > n/2){ 
     return start + sum(n, start + 1); 
    } 

    return start + sum(n, start + 1); 

} 

, 그것은 우리가 부분에 재귀를 분할하는 것은 더/덜 어떻게 동기를 부여해야 할 학교에서 과제는 다음과 같습니다

내가 지금까지 관리 코드는 다음입니다 합계를 계산하는 효율적인 방법. (1부터 N까지 직접 N/2에서 N으로 1에서 N/2까지의 숫자 추가).

그는 우리에게이 방법을 사용하여 우리를 더욱 어렵게 만들었지 만,이 방법에 대한 아이디어는 전혀 파악할 수 없습니다. 맞습니까?

감사합니다.

Answer 1

경우에 따라 재귀 깊이를 줄이는 것이 도움이 될 수 있습니다. 내부 단계는 N/2를 계산할 때

당신은 계정으로 시작 취할 필요, 코드가 아마이 유사하게 나타납니다

public static int sum(int n, int start) { 
    if (start > n) { 
    return 0; 
    } 

    if (start == n){ 
     return n; 
    } 

    int n2 = (start + n)/2; 
    return sum(n2, start) + sum(n, n2 + 1); 
} 

시작은> N 확인 단지의 끝에 추가 검사를 피할 수 시작과 n이 2보다 작은 경우.

Answer 2

int를 n으로 선언했는지 확인하십시오. n/2가 항상 기대치를 제공하지는 않습니다. 선생님이 관찰하기를 바라는 속임수라고 생각합니다.

Answer 3

나는이 코드 조각이 가능한 한 간단하다고 믿는다. 루프에서 성능을 확인할 수있다. 나는 복잡성에 어떤 차이도 보이지 않는다.

class Sums { 

    public static int sumHelp(int n, int start){ 
     if (n == start) return; 
     else return (n + sumHelp(n - 1, start)); 
    } 

    public static int sumByHalf(int n){ 
     return sumHelp(n/2, 0) + sumHelp(n, n/2); 
    } 

    public static int sum(int n){ 
     return sumHelp(n, 0); 
    } 

    public static void main(String[] args) { 
     System.out.println(sumByHalf(100)); 
     System.out.println(sum(100)); 
    } 
}