Метод «разделяй и властвуй» в «Алгоритмах Р. Седжвика в Java: части 1–4»

Question

В главе 5 книги в заголовке есть описание метода «разделяй и властвуй» для поиска максимального числа в массиве со следующим приложенным изображением:

Javaиспользуемый код:

static double max(double a[], int l, int r)
{
    if (l == r) return a[l];
    int m = (l+r)/2;
    double u = max(a, l, m);
    double v = max(a, m+1, r);
    if (u > v) return u; else return v;
}

Я думаю, что изображение неверно.Например, вызов метода с (0, 1), т. Е. T max (0,1) должен вернуть I, а не T. Я прав?

Также здесь есть ошибка в следующем изображении в книге:

Пожалуйста, уточните, может быть, что-то не так с моим пониманием рекурсии.

Answer 1

Пример, показанный на первом изображении, возвращает в массиве самую высокую букву, а не цифру. Показанные числа служат для обозначения индекса массива каждой буквы. Поскольку T> I, max(0,1) возвращает T. Общее возвращаемое значение алгоритма - Y, потому что это самая высокая буква из всех.

На втором изображении каждый узел первого дерева является суммой его непосредственных дочерних узлов; каждый узел второго дерева представляет собой пол среднего числа его непосредственных дочерних узлов; а третье дерево в основном показывает то, что показала ваша первая картинка.

Надеюсь, это прояснит для вас!

Answer 2

Я думаю, что изображение неверно.Например, вызов метода с (0, 1), т.е. T max (0,1) должен возвращать I, а не T. Я прав?

Нет.

Вызов max(a, 0, 1) присваивает m = 0, а затем рекурсивно вызывает max(a, 0, 0) и max(a, 1, 1).Значения u и v равны 'T' и 'I' соответственно, и наибольшее из них равно 'T' ..., которое возвращается.

Answer 3

Первый: в коде используется double, в примере, похоже, используется char, поэтому пример и код не полностью выровнены.

Секунда: в max(l, r) l и r индексируются в массив, а не фактические значения. Сравниваемые значения: T и I. В моей таблице ASCII мой алфавит I стоит перед T, поэтому I считается меньше T. Таким образом, максимум обоих составляет T.