Как алгоритмы Divide и Conquer работают с данным вводом?

Question

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

public static int FindMin(int[] array, int low, int high) 
{ 
int min = 0, min1 = 0, min2 = 0; 
int mid = 0; 
if (low == high) 
    { 
    min = array[low]; 
    } 
else if (low == (high - 1)) 
    { 
    if (array[low] < array[high]) 
     { 
     min = array[low]; 
     } 
    else if (array[low] > array[high]); 
     { 
     min = array[high]; 
     } 
    } 
else 
    { 
    mid = (low + high)/2; 
    min1 = FindMin(array, low, mid); 
    min2 = FindMin(array, mid+1, high); 
    if (min1 < min2) 
     { 
     min = min1; 
     } 
    else 
     { 
     min = min2; 
     } 
    } 
return min; 
} 

В основном то, что я хочу знать: как алгоритм будет работать, если он был дан вход: 3,6,1,5,7,2,1. Как то, что он возвращает, и тому подобное.

Прошу прощения, если вопрос несколько неоднозначен, но я знаю, как его кодировать, я просто не могу понять, как он возвращает все, независимо от всех страниц Google и pdf-файлов, с которых я начал.

Спасибо за помощь! : D

Answer 1

Итак, теперь я понял, что он делает и как это работает.

Это довольно просто. Для данного массива вы делите его на две части дальше и дальше. Теперь каждый рекурсивный код должен остановиться в какой-то момент, ваша остановка в двух ситуациях.

A) When the part this recursive needs to process is sized one. 
B) When the part this recursive needs to process is sized two. 

Так что, когда условие A выполнено, ваша функция просто возвращает низкую, что равно высокой.

Когда выполняется условие B, ваша функция сравнивает array[low] и array[high] и возвращает индекс нижнего значения.

Если рекурсивная функция должна обрабатывать диапазон более 2, она делит на две части и передает эти две части двум рекурсивным частям.

Например, для данного массива, подобного этому.

array[] = {1, 2, 3, 4, 5} 

You will first split it to two parts of {1, 2} [0...1] and {3, 4, 5} [2...4]. 

    And now since the first part is of size 2, the index 0 gets returned because 1 is smaller than 2, obviously. 

    And then the other part {3, 4, 5} gets divided again, to two parts, {3} [2...2], and {4, 5} [3...4]. 

     The first subpart of sized one, gets returned immediately, because it's of size one, return value = 2. 

     And then the second part which is sized two, get compared and returned, return value = 3. 

    Now these two return values (2 and 3) gets processed, comparing array[2] and array[3], array[2] is definitely smaller, so it returns 2. 

Now those two return values (0 and 2) gets processed, comparing the two, we can see the minima is at index 0, of value 1. 

Там есть ошибка в вашем коде, в последней части, вы должны сравнить array[min1] и array[min2] и вернуть min1 или min2.

Это довольно беспорядок, надеюсь, что вы можете понять. Еще одна вещь - мой синтаксис, {data}

Answer 2

Хотя отладчик полезен, иногда правильный вид вывода журнала может обеспечить более глубокое понимание. Я добавил вызов следующей функции в конце вашей FindMin() функции, как раз перед return min; заявлением:

public static void pr (int[] array, int low, int high, int min) { 
    System.out.print("low = "); 
    System.out.print(low); 
    System.out.print(", high = "); 
    System.out.print(high); 
    System.out.print(", array = "); 
    for (int i = low; i <= high; i++) { 
     System.out.print(array[i]); 
     if (i < high) { 
      System.out.print(","); 
     } 
    } 
    System.out.print(" min = "); 
    System.out.print(min); 
    System.out.print("\n"); 
} 

Выхода я получаю:

low = 0, high = 1, array = 3,6 min = 6 
low = 2, high = 3, array = 1,5 min = 5 
low = 0, high = 3, array = 3,6,1,5 min = 5 
low = 4, high = 5, array = 7,2 min = 2 
low = 6, high = 6, array = 1 min = 1 
low = 4, high = 6, array = 7,2,1 min = 1 
low = 0, high = 6, array = 3,6,1,5,7,2,1 min = 1 

Это говорит мне, что, хотя FindMin() является вернув правильный ответ для этого тестового примера, он делает это несколько случайно. Я сейчас смотрел, почему ...

(EDIT)

Одна проблема в том, что код:

if (array[low] < array[high]) 
{ 
    min = array[low]; 
} 
else if (array[low] > array[high]); // <- stray semi-colon here 
{ 
    min = array[high]; 
} 

... не рассматривается случай, когда array[low] == array[high]. Либо первое сравнение должно быть <=, либо второе должно быть >=, иначе будут случаи, когда возвращаемое значение min будет его инициализированным значением 0, так как ни одна из ветвей if не применима.

(ДАЛЕЕ EDIT)

У вас есть шальная запятой, которая вызывает вашу ошибку. Полуколона после теста, отмеченного выше, завершает утверждение. Затем досрочно прекращается else if, а затем другое заявление, которое всегда устанавливает min равным array[high] независимо от предыдущих тестов.

Изменение этого кода:

if (array[low] < array[high]) 
    { 
    min = array[low]; 
    } 
else 
    { 
    min = array[high]; 
    } 

... дает следующий вывод:

low = 0, high = 1, array = 3,6 min = 3 
low = 2, high = 3, array = 1,5 min = 1 
low = 0, high = 3, array = 3,6,1,5 min = 1 
low = 4, high = 5, array = 7,2 min = 2 
low = 6, high = 6, array = 1 min = 1 
low = 4, high = 6, array = 7,2,1 min = 1 
low = 0, high = 6, array = 3,6,1,5,7,2,1 min = 1 

... который вы можете увидеть производит правильный результат от каждого рекурсивного вызова.