Алгоритмы C++
.pdfДалее, пусть |
— номер строки, в которой находится пустой элемент (т.е. в наших |
обозначениях |
. |
Тогда, решение существует тогда и только тогда, когда чётно.
Реализация
Проиллюстрируем указанный выше алгоритм с помощью программного кода:
int a[16];
for (int i=0; i<16; ++i) cin >> a[i];
int inv = 0;
for (int i=0; i<16; ++i) if (a[i])
for (int j=0; j<i; ++j) if (a[j] > a[i])
++inv; for (int i=0; i<16; ++i)
if (a[i] == 0)
inv += 1 + i / 4;
puts ((inv & 1) ? "No Solution" : "Solution Exists");
Доказательство
Джонсон (Johnson) в 1879 г. доказал, что если |
нечётно, то решения не существует, а Стори (Story) в том же |
году доказал, что все позиции, для которых |
чётно, имеют решение. |
Однако оба эти доказательства были достаточно сложны.
В 1999 г. Арчер (Archer) предложил значительно более простое доказательство (скачать его статью можно здесь).
Доказывается это просто приведением трёх дробей к общему знаменателю.
Поскольку на нулевой итерации упорядоченность имела место, то она будет сохраняться и на каждой новой итерации.
Несократимость. Для этого покажем, что на любой итерации для любых двух соседних в списке дробей и выполняется:
|
|
|
Действительно, вспоминая Диофантовы уравнения с двумя неизвестными ( |
|
), получаем из |
|
этого утверждения, что , что нам и требуется.
Итак, нам надо доказать истинность утверждения |
на любой итерации. Докажем его также по индукции. |
На нулевой итерации это свойство выполнялось (в чём нетрудно убедиться). Теперь пусть оно было выполнено на предыдущей итерации, покажем, что оно выполнено на текущей итерации. Для этого надо рассмотреть тройку дробей-соседей в новом списке:
Для них условия принимают вид:
|
|
Однако истинность этих условий очевидна, при условии истинности |
. Таким образом, действительно, |
это свойство выполнено и на текущей итерации, что и требовалось доказать.
Наличие всех дробей. Доказательство этого свойства тесно связано с алгоритмом нахождения дроби в дереве Штерна-Броко. Учитывая, что в дереве Штерна-Броко все дроби упорядочены, получаем, что для любой вершины дерева в её левом поддереве находятся дроби, меньшие её, а в правом — большие её. Отсюда получаем и очевидный алгоритм поиска какой-либо дроби в дереве Штерна-Броко: вначале мы находимся в корне; сравниваем нашу дробь с дробью, записанной в текущей вершине: если наша дробь меньше, то переходим в левое поддерево, если наша дробь больше — переходим в правое, а если совпадает — нашли дробь, поиск завершён.
Чтобы доказать, что бесконечное дерево Штерна-Броко содержит все дроби, достаточно показать, что этот алгоритм поиска дроби завершится за конечное число шагов для любой заданной дроби. Этот алгоритм можно
понимать так: у нас есть текущий отрезок , в котором мы ищем нашу дробь . Изначально , .
На каждом шаге дробь |
сравнивается с медиантой концов отрезка, т.е. с |
, и в зависимости от этого мы |
либо останавливаем поиск, либо переходим в левую или правую часть отрезка. Если бы алгоритм поиска дроби работал бесконечно долго, то следующие условия были бы выполнены на каждой итерации:
Но их можно переписать в таком виде:
(здесь использовалось то, что они целочисленны, поэтому из следует ) Тогда, умножая первое на , а второе — на , и складывая их, получаем:
|
|
Раскрывая скобки слева и учитывая, что |
(см. доказательство предыдущего свойства), |
окончательно получаем: |
|
|
|
|
|
А поскольку на каждой итерации хотя бы одна из переменных строго возрастает, то процесс поиска дроби
будет содержать не более итераций, что и требовалось доказать.
Алгоритм построения дерева
Чтобы построить любое поддерево дерева Штерна-Броко, достаточно знать только левого и правого предков. Изначально, на первом уровне, левым предком является , а правым — . По ним можно вычислить дробь в
текущей вершине, а затем запуститься от левого и правого сыновей (левому сыну передав себя в качестве правого предка, а правому сыну — в качестве левого предка).
Псевдокод этой процедуры, пытающийся построить всё бесконечное дерево:
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]
Литература
С++
Visual C++, MFC
●Круглински, Уингоу, Шеферд. Программирование на Microsoft Visual C++ 6.0 для профессионалов
(PDF[in RAR], 54.4 МБ)
С++
●ANSI. C++ International Standard (second edition, 2003-10-15) (PDF, 2.3 МБ)
●Эккель. Философия C++. Введение в стандартный C++ (2-е изд.) (DJVU, 6.4 МБ)
●Эккель, Эллисон. Философия C++. Практическое программирование (DJVU, 6.5 МБ)
●Саттер. Решение сложных задач на C++. 87 головоломных примеров с решениями (DJVU, 3.8 МБ)
●Саттер. Новые сложные задачи на C++. 40 новых головоломных примеров с решениями
(DJVU, 3.6 МБ)
●Страуструп. Язык программирования C++ (2-е, дополненное изд.) (PDF, 2.9 МБ)
●Stroustrup. The C++ Programming Language (3rd edition) (PDF, 3.4 МБ)
●Abrahams, Gurtovoy. C++ Template Metaprogramming: Concepts, Tools, and Techniques from Boost and Beyond (CHM, 0.62 МБ)
●Джосьютис. C++. Стандартная библиотека. Для профессионалов (DJVU, 4.8 МБ)
●Джосьютис. C++. Стандартная библиотека. Для профессионалов (CD к книге) (ZIP, 0.14 МБ)
●Vandervoorde, Josuttis. C++ Templates: The Complete Guide (CHM, 0.72 МБ)
●Sutter, Alexandrescu. C++ Coding Standards: 101 Rules, Guidelines, and Best Practices (CHM, 0.51 МБ)
●Голуб. Веревка достаточной длины, чтобы выстрелить себе в ногу. Правила программирования на C и C++ (PDF, 1.29 МБ)
●Meyers. Effective C++. More effective C++ (CHM, 2.0 МБ)
●Дьюхэрст. Скользкие места C++. Как избежать проблем при проектировании и
компиляции ваших программ (DJVU, 9.3 МБ)
● Дьюхэрст. C++. Священные знания (DJVU, 6.7 МБ)
Алгоритмы
Фундаментальные пособия
●Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы. Построение и анализ (2-е зд.) (DJVU, 18.3 МБ)
●Knuth. The Art of Computer Programming. Volume 1 (3rd edition) (DJVU, 6.0 МБ)
●Knuth. The Art of Computer Programming. Volume 2 (3rd edition) (DJVU, 7.6 МБ)
●Knuth. The Art of Computer Programming. Volume 3 (2nd edition) (DJVU, 7.7 МБ)
●Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы. Построение и анализ (1-е изд.?) (PDF, 4.5 МБ)
●Cormen, Leiserson, Rivest, Stein. Introduction to algorithms (2nd edition) (PDF, 12.5 МБ)
●Седжвик. Фундаментальные алгоритмы (3-я ред.). Части 1-4 (DJVU, 15.0 МБ)
●Седжвик. Фундаментальные алгоритмы (3-я ред.). Часть 5 (DJVU, 16.7 МБ)
●Кнут. Искусство программирования. Том 1 (DJVU, 5.6 МБ)
●Кнут. Искусство программирования. Том 2 (DJVU, 6.1 МБ)
●Кнут. Искусство программирования. Том 3 (DJVU, 6.4 МБ)
●Грэхэм, Кнут, Паташник. Конкретная математика (DJVU, 8.9 МБ)
●Пападимитриу, Стайглиц. Комбинаторная оптимизация: алгоритмы и сложность (DJVU, 5.6 МБ)
Олимпиадные задачи
●Меньшиков. Олимпиадные задачи по программированию (DJVU, 4.4 МБ)
●Меньшиков. Олимпиадные задачи по программированию (CD к книге) (ZIP, 4.0 МБ)
●Окулов. Программирование в алгоритмах (DJVU, 3.6 МБ)
●Долинский. Решение сложных и олимпиадных задач по программированию (DJVU, 2.9 МБ)
●Скиена, Ревилла. Олимпиадные задачи по программированию (DJVU, 5.3 МБ)
Строки
●Гасфилд. Строки, деревья и последовательности в алгоритмах (DJVU, 12.1 МБ)
●Smyth. Computing patterns in strings (DJVU, 26.4 МБ)