e-maxx_algo
.pdf
между ними, т.е.:
при условии, что
Доказывается это просто приведением трёх дробей к общему знаменателю.
Поскольку на нулевой итерации упорядоченность имела место, то она будет сохраняться и на каждой новой итерации.
Несократимость. Для этого покажем, что на любой итерации для любых двух соседних в списке дробей и 
выполняется:
|
|
|
|
Действительно, вспоминая Диофантовы уравнения с двумя неизвестными ( |
|
), получаем из |
|
|
|||
этого утверждения, что |
, что нам и требуется. |
|
|
Итак, нам надо доказать истинность утверждения |
на любой итерации. Докажем его также по индукции. |
||
На нулевой итерации это свойство выполнялось (в чём нетрудно убедиться). Теперь пусть оно было выполнено на предыдущей итерации, покажем, что оно выполнено на текущей итерации. Для этого надо рассмотреть тройку дробей-соседей в новом списке:
Для них условия принимают вид:
|
|
Однако истинность этих условий очевидна, при условии истинности |
. Таким образом, действительно, |
это свойство выполнено и на текущей итерации, что и требовалось доказать. |
|
Наличие всех дробей. Доказательство этого свойства тесно связано с алгоритмом нахождения дроби в дереве Штерна-Броко. Учитывая, что в дереве Штерна-Броко все дроби упорядочены, получаем, что для любой вершины дерева в её левом поддереве находятся дроби, меньшие её, а в правом — большие её. Отсюда получаем и очевидный алгоритм поиска какой-либо дроби в дереве Штерна-Броко: вначале мы находимся в корне; сравниваем нашу дробь с дробью, записанной в текущей вершине: если наша дробь меньше, то переходим в левое поддерево, если наша дробь больше — переходим в правое, а если совпадает — нашли дробь, поиск завершён.
Чтобы доказать, что бесконечное дерево Штерна-Броко содержит все дроби, достаточно показать, что этот алгоритм поиска дроби завершится за конечное число шагов для любой заданной дроби. Этот алгоритм можно
понимать так: у нас есть текущий отрезок |
, в котором мы ищем нашу дробь . Изначально |
, |
. |
|
На каждом шаге дробь сравнивается с медиантой концов отрезка, т.е. с |
, и в зависимости от этого мы |
|
||
либо останавливаем поиск, либо переходим в левую или правую часть отрезка. Если бы алгоритм поиска дроби работал бесконечно долго, то следующие условия были бы выполнены на каждой итерации:
Но их можно переписать в таком виде:
(здесь использовалось то, что они целочисленны, поэтому из 
следует 
) Тогда, умножая первое на 
, а второе — на 
, и складывая их, получаем:
|
|
|
Раскрывая скобки слева и учитывая, что |
(см. доказательство предыдущего свойства), |
|
окончательно получаем: |
|
|
|
|
|
|
|
|
А поскольку на каждой итерации хотя бы одна из переменных |
строго возрастает, то процесс поиска дроби |
|
будет содержать не более 
итераций, что и требовалось доказать.
Алгоритм построения дерева
Чтобы построить любое поддерево дерева Штерна-Броко, достаточно знать только левого и правого предков. Изначально, на первом уровне, левым предком является , а правым — . По ним можно вычислить дробь в
текущей вершине, а затем запуститься от левого и правого сыновей (левому сыну передав себя в качестве правого предка, а правому сыну — в качестве левого предка).
Псевдокод этой процедуры, пытающийся построить всё бесконечное дерево:
void build (int a |
= 0, int b = 1, int c = 1, int d = 0, int level = 1) { |
int x = a+c, y = b+d; |
|
... вывод |
текущей дроби x/y на уровне дерева level |
build (a, |
b, x, y, level + 1); |
build (x, |
y, c, d, level + 1); |
} |
|
Алгоритм поиска дроби
Алгоритм поиска дроби был уже описан при доказательства того, что дерево Штерна-Броко содержит все дроби, повторим его здесь. Этот алгоритм — фактически алгоритм бинарного поиска, или алгоритм поиска заданного значения в бинарном дереве поиска. Изначально мы стоим в корне дерева. Стоя в текущей вершине, мы сравниваем нашу дробь с дробью в текущей вершине. Если они совпадают, то процесс останавливаем — мы нашли дробь в дереве. Иначе, если наша дробь меньше дроби в текущей вершине, то переходим в левого сына, иначе — в правого.
Как было доказано в свойстве о том, что дерево Штерна-Броко содержит все неотрицательные дроби, при поиске дроби
алгоритм совершит не более 
итераций.
Приведём реализацию, которая возвращает путь до вершины, содержащей заданную дробь , возвращая его в
виде последовательности символов 'L'/'R': если текущий символ равен 'L', то это обозначает переход в дереве в левого сына, а иначе — в правого (изначально мы стоим в корне дерева, т.е. в вершине с дробью ). На самом деле,
такая последовательность символов, существующая и однозначно определяющая любую неотрицательную дробь, называется системой счисления Штерна-Броко.
string find (int x, int y, int a = 0, int b = 1, int c = 1, int d = 0) { int m = a+c, n = b+d;
if (x == m && y == n) return "";
if (x * n < y * m)
return 'L' + find (x, y, a, b, m, n);
else
return 'R' + find (x, y, m, n, c, d);
}
Иррациональным числам в системе счисления Штерна-Броко будут соответствовать бесконечные последовательности символов; если известна какая-то наперёд заданная точность, то можно ограничиться некоторым префиксом этой бесконечной последовательности. В процессе этого бесконечного поиска иррациональной дроби в дереве Штерна-Броко алгоритм будет каждый раз находить простую дробь (с постепенно возрастающими знаменателями), обеспечивающую лучшее приближение этого иррационального числа (это применение как раз важно в часовой технике, и в связи с этим Ахилл Броко и открыл это дерево).
Последовательность Фарея
Последовательностью Фарея порядка 
называется множество всех несократимых дробей между 0 и 1, знаменатели которых не превосходят 
, причём дроби упорядочены в порядке возрастания.
Эта последовательность названа в честь английского геолога Джона Фарея (John Farey), который попытался в 1816 г. доказать, что в ряде Фарея любая дробь является медиантой двух соседних. Насколько известно, его
доказательство было неверным, а правильное доказательство предложил несколько позже Коши (Cauchy). Впрочем, ещё в 1802 г. математик Харос (Haros) в одной из своих работ пришёл практически к тем же результатам.
Последовательности Фарея обладают и множеством собственных интересных свойств, однако наиболее очевидна их связь с деревом Штерна-Броко: фактически, последовательность Фарея получается удалением некоторых ветвей из дерева. Или можно говорить, что для получения последовательности Фарея нужно
взять множество дробей, получаемое при построении дерева Штерна-Броко на бесконечной итерации, и оставить в этом множестве только дроби со знаменателями, не превосходящими 
и числителями, не превосходящими знаменатели.
Из алгоритма построения дерева Штерна-Броко следует и аналогичный алгоритм для последовательностей Фарея.
На нулевой итерации включим в множество только дроби и . На каждой следующей итерации мы между каждыми
двумя соседним дробями вставляем их медианту, если её знаменатель не превосходит 
. Рано или поздно в множестве перестанут происходить какие-либо изменения, и процесс можно останавливать — мы нашли искомую последовательность Фарея.
Вычислим длину последовательности Фарея. Последовательность Фарея порядка 
содержит все
элементы последовательности Фарея порядка |
, а также все несократимые дроби со знаменателями, равными |
|
, но это количество, как известно, равно |
. Таким образом, длина |
последовательности Фарея порядка |
выражается по формуле:
или, раскрывая рекурсию:
Литература
●Роналд Грэхем, Дональд Кнут, Орен Паташник. Конкретная математика. Основание информатики [1998]
Поиск подотрезка массива с максимальной/минимальной суммой
Здесь мы рассмотрим задачу о поиске подотрезка массива с максимальной суммой ("maximum subarray problem"
на английском), а также некоторые её вариации (в том числе алгоритм решения варианта этой задачи в режиме онлайн
— описанный автором алгоритма — KADR (Ярослав Твердохлеб)).
Постановка задачи
Дан массив чисел 
. Требуется найти такой его подотрезок 
, что сумма на нём максимальна:
|
|
Например, если бы все числа массива |
были бы неотрицательными, то в качестве ответа можно было бы взять |
весь массив. Решение нетривиально, когда массив может содержать как положительные, так и отрицательные числа.
Понятно, что задача о поиске минимального подотрезка — по сути та же самая, достаточно лишь изменить знаки всех чисел на противоположные.
Алгоритм 1
Здесь мы рассмотрим практически очевидный алгоритм. (Дальше мы рассмотрим другой алгоритм, который чуть сложнее придумать, однако его реализация получается ещё короче.)
Описание алгоритма
Алгоритм весьма прост.
Введём для удобства обозначение: |
. Т.е. массив |
— это массив частичных сумм |
массива 
. Также положим значение 
.
Будем теперь перебирать индекс 
, и научимся для каждого текущего значения 
быстро находить оптимальное 
, при котором достигается максимальная сумма на подотрезке 
.
Формально это означает, что нам надо для текущего 
найти такое (не превосходящее 
), чтобы величина была максимальной. После тривиального преобразования мы получаем, что нам надо
найти минимальное значение в массиве |
минимум на отрезке |
. |
|
Отсюда мы сразу получаем алгоритм решения: мы просто будем хранить, где в массиве |
находится текущий |
||
минимум. Используя этот минимум, мы за |
находим текущий оптимальный индекс , а при переходе от |
||
текущего индекса к следующему мы просто обновляем этот минимум. |
|
|
|
Очевидно, этот алгоритм работает за |
и асимптотически оптимален. |
|
|
Реализация
Для реализации нам даже не понадобится явно хранить массив частичных сумм |
— от него нам будет |
требоваться только текущий элемент. |
|
Реализация приводится в 0-индексированных массивах, а не в 1-нумерации, как было описано выше. Приведём сначала решение, которое находит просто численный ответ, не находя индексы искомого отрезка:
int ans = a[0], sum = 0,
min_sum = 0;
for (int r=0; r<n; ++r) { sum += a[r];
ans = max (ans, sum - min_sum); min_sum = min (min_sum, sum);
}
Теперь приведём полный вариант решения, который параллельно с числовым решением находит границы искомого отрезка:
int ans = a[0], ans_l = 0, ans_r = 0, sum = 0, min_sum = 0, min_pos = -1;
for (int r=0; r<n; ++r) { sum += a[r];
int cur = sum - min_sum; if (cur > ans) {
ans = cur;
ans_l = min_pos + 1; ans_r = r;
}
if (sum < min_sum) { min_sum = sum; min_pos = r;
}
}
Алгоритм 2
Здесь мы рассмотрим другой алгоритм. Его чуть сложнее понять, но зато он более элегантен, чем приведённый выше, и реализуется чуть-чуть короче. Этот алгоритм был предложен Джеем Каданом (Jay Kadane) в 1984 г.
Описание алгоритма
Сам алгоритм выглядит следующим образом. Будем идти по массиву и накапливать в некоторой переменной
текущую частичную сумму. Если в какой-то момент 
окажется отрицательной, то мы просто присвоим
. Утверждается, что максимум из всех значений переменной 
, случившихся за время работы, и будет ответом на задачу.
Докажем этот алгоритм.
В самом деле, рассмотрим первый момент времени, когда сумма 
стала отрицательной. Это означает, что, стартовав с нулевой частичной суммы, мы в итоге пришли к отрицательной частичной сумме — значит, и весь этот префикс массива, равно как и любой его суффикс имеют отрицательную сумму. Следовательно, от всего этого префикса массива в дальнейшем не может быть никакой пользы: он может дать только отрицательную прибавку к ответу.
Однако этого недостаточно для доказательства алгоритма. В алгоритме мы, фактически, ограничиваемся в поиске ответа только такими отрезками, которые начинаются непосредственно после мест, когда случалось 
.
Но, в самом деле, рассмотрим произвольный отрезок |
, причём |
не находится в такой "критической" позиции (т. |
|||
е. |
, где — последняя такая позиция, в которой |
). Поскольку последняя критическая |
|||
позиция находится строго раньше, чем в |
, то получается, что сумма |
неотрицательна. |
|||
Это означает, что, сдвинув 
в позицию 
, мы увеличим ответ или, в крайнем случае, не изменим его.
Так или иначе, но получается, что действительно при поиске ответа можно ограничиться только отрезками, начинающимися сразу после позиций, в которых оказывалось 
. Это доказывает правильность алгоритма.
Реализация
Как и в алгоритме 1, приведём сначала упрощённую реализацию, которая ищет только числовой ответ, не находя границ искомого отрезка:
int ans = a[0], sum = 0;
for (int r=0; r<n; ++r) { sum += a[r];
ans = max (ans, sum); sum = max (sum, 0);
}
Полный вариант решения, с поддержанием индексов-границ искомого отрезка:
int ans = a[0], ans_l = 0, ans_r = 0, sum = 0,
minus_pos = -1; for (int r=0; r<n; ++r) {
sum += a[r];
if (sum > ans) { ans = sum;
ans_l = minus_pos + 1; ans_r = r;
}
if (sum < 0) { sum = 0;
minus_pos = r;
}
}
Смежные задачи
Поиск максимального/минимального подотрезка с ограничениями
Если в условии задачи на искомый отрезок |
накладываются дополнительные ограничения (например, что |
|
длина |
отрезка должна находиться в заданных пределах), то описанный алгоритм скорее всего |
|
легко обобщается на эти случаи — так или иначе, задача будет по-прежнему заключаться в поиске минимума в массиве 
при заданных дополнительных ограничениях.
Двумерный случай задачи: поиск максимальной/ минимальной подматрицы
Описанная в данной статье задача естественно обобщается на большие размерности. Например, в двумерном случае
она превращается в поиск такой подматрицы |
заданной матрицы, которая имеет |
|
|
максимальную сумму чисел в ней. |
|
|
|
Из описанного выше решения для одномерного случая легко получить решение за |
: переберём |
и , |
|
и посчитаем массив сумм с по в каждой строке матрицы; мы пришли к одномерной задаче поиска индексов |
и |
||
в этом массиве, которую уже можно решать за линейное время. |
|
|
|
Более быстрые алгоритмы решения этой задачи хотя и известны, однако они не сильно быстрее |
, и |
||
при этом весьма сложны (настолько сложны, что по скрытой константе многие из них уступают тривиальному алгоритму при всех разумных ограничениях). По всей видимости, лучший из известных алгоритмов работает
за 
(T. Chan 2007 "More algorithms for all-pairs shortest paths in weighted graphs").
Этот алгоритм Chan, а также многие другие результаты в данной области на самом деле описывают быстрое умножение матриц (где под умножением матриц подразумевается модифицированное умножение: вместо сложения используется минимум, а вместо умножения — сложение). Дело в том, что задача о
поиске подматрицы с наибольшей суммой сводится к задаче о поиске кратчайших путей между всеми парами вершин, а эта задача, в свою очередь — сводится к такому умножению матриц.
Поиск подотрезка с максимальной/минимальной средней суммой
Эта задача заключается в том, что надо найти такой отрезок 
, чтобы среднее значение на нём было максимальным:
|
|
Конечно, если на искомый отрезок |
по условию не наложено других условий, то решением всегда будет |
являться отрезок длины 
в точке-максимуме массива. Задача имеет смысл, только если имеются дополнительные ограничения (например, длина искомого отрезка ограничена снизу).
В таком случае применим стандартный приём при работе с задачами о среднем значении: будем
подбирать искомую максимальную среднюю величину двоичным поиском.
Для этого нам надо научиться решать такую подзадачу: дано число 
, и надо проверить, есть ли подотрезок массива 
(конечно, удовлетворяющий всем дополнительным ограничениям задачи), на котором среднее значение больше 
.
Чтобы решить эту подзадачу, отнимем от каждого элемента массива |
. Тогда наша подзадача |
фактически превращается в такую: есть или нет в данном массиве подотрезок положительной суммы. А эту задачу мы уже умеем решать.
Таким образом, мы получили решение за асимпотику , где — требуемая точность, —
время решения подзадачи для массива длины 
(которое может варьироваться в зависимости от конкретных накладываемых дополнительных ограничений).
Решение задачи в режиме онлайн
Условие задачи таково: дан массив из 
чисел, а также дано число 
. Поступают запросы вида , и в ответ на запрос требуется найти подотрезок отрезка 
длины не менее 
с максимально возможным средним арифметическим.
Алгоритм решения этой задачи достаточно сложен. Автор данного алгоритма — KADR (Ярослав Твердохлеб) — описал данный алгоритм в своём сообщении на форуме.
● Харари. Перечисление графов (DJVU, 4.1 МБ)
Теория сложности
● Гэри, Джонсон. Вычислительные машины и труднорешаемые задачи (DJVU, 11.5 МБ)
Математика
● Aitken. Determinants and Matrices (PDF, 10.2 МБ)
Структуры данных
●Tarjan. Efficiency of a Good But Not Linear Set Union Algorithm (PDF, 0.63 МБ)
●Tarjan, Leeuwen. Worst-Case Analysis of Set Union Algorithms (PDF, 1.55 МБ)
Оптимизация
●Kaspersky. Code Optimization: Effective Memory Usage (CHM, 10.4 МБ)
●Kaspersky. Code Optimization: Effective Memory Usage (CD к книге) (ZIP, 4.6 МБ)
●Fog. Optimization Manuals (Optimizing software in C++, in assembly, processors microarchitecture) (last edited - 2008) (PDF[in ZIP], 2.9 МБ)
●Intel. Intel Architecture Optimization Manual (1997) (PDF, 0.49 МБ)
Java
Java
●Эккель. Философия Java (4-е изд.) (DJVU, 5.4 МБ)
●Хорстманн, Корнелл. Java 2. Библиотека профессионала. Том 1 (Основы) (7-е изд.)
(DJVU, 10.5 МБ)
●Хорстманн, Корнелл. Java 2. Библиотека профессионала. Том 2 (Тонкости программирования) (7-е изд.) (DJVU, 13.2 МБ)
●Хорстманн, Корнелл. Java 2. Библиотека профессионала (7-е изд.) (CD к книге) (ZIP, 0.66 МБ)
TeX
TeX
●Кнут. Всё про TeX (DJVU, 17.1 МБ)
●Abrahams, Hargreaves, Berry. TeX for the Impatient (PDF, 1.36 МБ)
LaTeX
●Gratzer. Math into LaTeX. An Introduction to LaTeX and AMS-LaTeX (DJVU, 0.34 МБ)
●Oetiker. The Not So Short Introduction to LaTeX (version 4.26, 2008-Sep-25) (PDF, 2.3 МБ)