Ошибка переполнения стека алгоритма Java «разделяй и властвуй» - PullRequest
0 голосов
/ 28 августа 2018

Я пытаюсь найти индекс наименьшего числа в массиве int, используя разделяй и властвуй, и у меня есть эта ошибка переполнения стека:

Exception in thread "main" java.lang.StackOverflowError
    at java.lang.StrictMath.floor(Unknown Source)
    at java.lang.Math.floor(Unknown Source)

Это мой метод «разделяй и властвуй»:

private static int dC(int[] a, int f, int l) {
        if(f == 1)
            return f;
        if(a[dC(a, f, (int)(Math.floor((double)(f+l)/2)))] > a[dC(a, (int)(Math.floor((double)(f+l)/2)+1), l)])
            return dC(a, (int)(Math.floor((double)(f+l)/2)+1), l);
        else
            return dC(a, f, (int)(Math.floor((double)(f+l)/2)));
    }

Вот что я добавил в свой основной метод:

int[] a = {35,30,40,50};

System.out.println(dC(a, 0, 3));

Ответы [ 3 ]

0 голосов
/ 28 августа 2018

Это просто классическая проблема бинарного поиска. Из того, что я могу почерпнуть, посмотрев на ваш код, вы, похоже, увязли в логике, используемой для выполнения каждого рекурсивного вызова левого и правого подмассивов текущего массива. Логика, которую я использовал ниже, состоит в том, чтобы взять все от начала до (начало + конец) / 2 для левой рекурсии, и все от ((начало + конец) / 2) + 1 до конца для правой рекурсии. Это гарантирует, что никогда не будет перекрытия.

Базовый случай возникает, когда алгоритм оказывается на одной записи в массиве. В этом случае мы просто возвращаем это значение и больше не рекурсивно.

private static int dC(int[] a, int start, int end) {
    if (start == end) return a[start];

    int left = dC(a, start, (start+end)/2);
    int right = dC(a, ((start+end)/2) + 1, end);

    return left < right ? left : right;
}

public static void main(String args[])
{
    int[] a = {10, 3, 74, 0, 99, 9, 13};
    System.out.println(dC(a, 0, 6));   // prints 0
}

Демо

Примечание: я понятия не имею, какую роль здесь сыграет Math.floor, поскольку вы используете массивы целых чисел, а не двойных или плавающих. Я удалил это, потому что не видел в этом необходимости.

0 голосов
/ 28 августа 2018

Это типичная проблема при поиске индекса на min/max, вы можете попробовать его как:

public static void main(String... args) {
    int[] arr = generateArrays(100, 1000, 0, 10000, true);
    int minIndex = findMinIndex(arr, 1, arr.length - 1);
    int theMin = arr[minIndex];
    Arrays.sort(arr);
    System.out.println(String.format("The min located correctly: %s", arr[0] == theMin));
}

private static int findMinIndex(int[] a, int l, int r) {
    if (r - l < 1) return l;
    int mid = l + (r - l) / 2;
    int lIndex = findMinIndex(a, l + 1, mid);
    int rIndex = findMinIndex(a, mid + 1, r);
    int theMinIndex = l;
    if (a[lIndex] < a[theMinIndex]) theMinIndex = lIndex;
    if (a[rIndex] < a[theMinIndex]) theMinIndex = rIndex;
    return theMinIndex;
}

И помощник для генерации случайного массива.

public static int[] generateArrays(int minSize, int maxSize, int low, int high, boolean isUnique) {
    Random random = new Random(System.currentTimeMillis());
    int N = random.nextInt(maxSize - minSize + 1) + minSize;
    if (isUnique) {
        Set<Integer> intSet = new HashSet<>();
        while (intSet.size() < N) {
            intSet.add(random.nextInt(high - low) + low);
        }
        return intSet.stream().mapToInt(Integer::intValue).toArray();
    } else {
        int[] arr = new int[N];
        for (int i = 0; i < N; ++i) {
            arr[i] = random.nextInt(high - low) + low;
        }
        return arr;
    }
}
0 голосов
/ 28 августа 2018

У вас есть проблема с вашим "правилом"

private static int dC(int[] a, int f, int l) {
        if(l == f) // <-- This mean you have one item, so you want to return it.
            return f;
        if(a[dC(a, f, (int)(Math.floor((double)(f+l)/2)))] > a[dC(a, (int)(Math.floor((double)(f+l)/2)+1), l)])
            return dC(a, (int)(Math.floor((double)(f+l)/2)+1), l);
        else
            return dC(a, f, (int)(Math.floor((double)(f+l)/2)));
    }

Кроме того, я бы попытался выполнить вычисление только один раз, что-то вроде этого (также то, что сказал Joop Eggen об арифметике целых чисел):

private static int dC(int[] a, int f, int l) {
        if(l == f)
            return f;
        int m = (f+l) / 2;
        int left = dC(a, f, m);
        int right = dC(a, m+1, l);
        if(a[left] > a[right])
            return left;
        else
            return right;
    }
...