使用分而治之的整数序列的平均值

Question

给定一个整数序列，我如何使用分而治之的方法求出它的平均值？我必须编写一个方法 "double avg(int[] a, int l, int r)" 来查找数组 A 中的平均值，从 'l' 到 'r' 作为作业，但是我在第一次递归调用时得到了 WhosebugError - 而不是在第二，虽然！ - 我的代码，我似乎不明白为什么。此外，我很确定它不会给我一个真正的平均值，但我发现没有办法使用分而治之来检查序列的平均值。这是我的代码：

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 并且在第二次递归调用中，mid+2 将大于 r。在函数的开头添加：

if(l > r)
       return 0;

例如，假设 l == 5 和 r == 6，那么 mid 的值为 5。第二次调用将是 averageCheck(A, 7, 6)，因为 mid+2 是 7 . 在这个调用中，条件 l == r 将是 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;

}
}

使用分而治之的整数序列的平均值

Average of a sequence of integers using divide and conquer

java

algorithm

divide-and-conquer