分割と征服を使用する整数のシーケンスの平均

Question

整数のシーケンスが与えられている場合、分割と征服のアプローチを使用してその平均を見つけるにはどうすればよいですか？私は宿題として 'l'から 'r'にわたる、配列Aの平均を見つける方法 "double avg（int [] a、int l、int r）を書く必要がありますが、私はStackOverflowErrorを最初の再帰呼び出し - 2番目の呼び出しではありません！ - 私のコードの、私はなぜ理解できないようです。また、私はそれが私に本当の平均を与えないと確信していますが、分割と征服を使ってシーケンスの平均をチェックする方法は見つけられませんでした。ここに私のコードです：

public class Average { 
public static void main(String[] args) { 

    int[] A = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; 
    int l = 0; 
    int r = A.length-1; 
    System.out.println("Average of the array: "+averageCheck(A, l, r)); 

} 

public static double averageCheck(int[] A, int l, int r) { 
    if (l==r) { 
     return A[l]; 
    } 
    // Base Case: if there's just a single element it is the average of the array itself 

    int mid = (l+r)/2; 
    double avLeft = 0; 
    double avRight = 0; 

    avLeft = A[l]/r + averageCheck(A, l, mid); 
    avRight = A[mid+1]/r + averageCheck(A, mid+2, r); 

    double average = ((avLeft*mid) + (avRight * (r-mid))) /r; 

    return average; 

    } 
} 

Answer 1

r == l + 1あなたの再帰は終了しません。この場合、mid == lとなり、2回目の再帰呼び出しではmid+2はrより大きくなります。関数の先頭にこれを追加します。

if(l > r) 
     return 0; 

例、l == 5とr == 6を想像し、その後、midが2回目の呼び出し5.値はこの呼び出し7.、条件l == r意志であるaverageCheck(A, 7, 6)mid+2ようになりますがありますfalseとなります。同じロジックで続行すると、再帰が終了しないことがわかります。

また、合計を再帰的に計算し、最後の長さで除算する方がよいと思います。

私はこのソリューションを提案：

public class Average { 
public static void main(String[] args) { 

    int[] A = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}; 
    System.out.println("Average of the array: "+average(A)); 

} 

public static double average (int[] A) { 
     return averageCheck(A, 0, A.length - 1)/A.length; 
} 

public static double averageCheck(int[] A, int l, int r) { 

if (l > r) 
    return 0; 

if (l==r) { 
    return A[l]; 
} 
// Base Case: if there's just a single element it is the average of the array itself 

int mid = (l+r)/2; 
double avLeft = 0; 
double avRight = 0; 

avLeft = averageCheck(A, l, mid); 
avRight = averageCheck(A, mid+1, r); 

double average = avLeft + avRight; 

return average; 

} 
}