MAXimal | |
добавлено: 17 Jul 2009 23:00 Содержание [скрыть] Дерево Штерна-Броко. Ряд ФареяДерево Штерна-БрокоДерево Штерна-Броко — это изящная конструкция, позволяющая построить множество всех неотрицательных дробей. Она была независимо открыта немецким математиком Морицем Штерном (Moritz Stern) в 1858 г. и французским часовщиком Ахиллом Броко (Achille Brocot) в 1861 г. Впрочем, по некоторым данным, эта конструкция была открыта ещё древнегреческим учёным Эратосфеном (Eratosthenes). На нулевой итерации у нас есть две дроби: Дальше, на каждом последующей итерации берётся этот список дробей и между каждыми двумя соседними дробями Так, на первой итерации текущее множество будет таким: На второй: На третьей: Продолжая этот процесс до бесконечности, утверждается, можно получить множество всех неотрицательных дробей. Более того, все получаемые дроби будут различными (т.е. в текущем множестве каждая дробь встречается не более одного раза), несократимыми (числители и знаменатели будут получаться взаимно простыми). Наконец, все дроби будут автоматически упорядоченными по возрастанию. Доказательство всех этих замечательных свойств дерева Штерна-Броко будет приведено чуть ниже. Осталось только привести изображение самого дерева Штерна-Броко (пока мы описывали его с помощью меняющегося множества). В корне этого бесконечного дерева находится дробь ДоказательствоУпорядоченность. Она доказывается очень просто: заметим, что медианта двух дробей всегда находится между ними, т.е.: Поскольку на нулевой итерации упорядоченность имела место, то она будет сохраняться и на каждой новой итерации. Несократимость. Для этого покажем, что на любой итерации для любых двух соседних в списке дробей ![]() ![]() Итак, нам надо доказать истинность утверждения ![]() Наличие всех дробей. Доказательство этого свойства тесно связано с алгоритмом нахождения дроби в дереве Штерна-Броко. Учитывая, что в дереве Штерна-Броко все дроби упорядочены, получаем, что для любой вершины дерева в её левом поддереве находятся дроби, меньшие её, а в правом — большие её. Отсюда получаем и очевидный алгоритм поиска какой-либо дроби в дереве Штерна-Броко: вначале мы находимся в корне; сравниваем нашу дробь с дробью, записанной в текущей вершине: если наша дробь меньше, то переходим в левое поддерево, если наша дробь больше — переходим в правое, а если совпадает — нашли дробь, поиск завершён. Чтобы доказать, что бесконечное дерево Штерна-Броко содержит все дроби, достаточно показать, что этот алгоритм поиска дроби завершится за конечное число шагов для любой заданной дроби. Этот алгоритм можно понимать так: у нас есть текущий отрезок ![]() ![]() Тогда, умножая первое на ![]() ![]() ![]() ![]() Алгоритм построения дереваЧтобы построить любое поддерево дерева Штерна-Броко, достаточно знать только левого и правого предков. Изначально, на первом уровне, левым предком является Псевдокод этой процедуры, пытающийся построить всё бесконечное дерево: 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); } Алгоритм поиска дробиАлгоритм поиска дроби был уже описан при доказательства того, что дерево Штерна-Броко содержит все дроби, повторим его здесь. Этот алгоритм — фактически алгоритм бинарного поиска, или алгоритм поиска заданного значения в бинарном дереве поиска. Изначально мы стоим в корне дерева. Стоя в текущей вершине, мы сравниваем нашу дробь с дробью в текущей вершине. Если они совпадают, то процесс останавливаем — мы нашли дробь в дереве. Иначе, если наша дробь меньше дроби в текущей вершине, то переходим в левого сына, иначе — в правого. Как было доказано в свойстве о том, что дерево Штерна-Броко содержит все неотрицательные дроби, при поиске дроби Приведём реализацию, которая возвращает путь до вершины, содержащей заданную дробь 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); } Иррациональным числам в системе счисления Штерна-Броко будут соответствовать бесконечные последовательности символов; если известна какая-то наперёд заданная точность, то можно ограничиться некоторым префиксом этой бесконечной последовательности. В процессе этого бесконечного поиска иррациональной дроби в дереве Штерна-Броко алгоритм будет каждый раз находить простую дробь (с постепенно возрастающими знаменателями), обеспечивающую лучшее приближение этого иррационального числа (это применение как раз важно в часовой технике, и в связи с этим Ахилл Броко и открыл это дерево). Последовательность ФареяПоследовательностью Фарея порядка Эта последовательность названа в честь английского геолога Джона Фарея (John Farey), который попытался в 1816 г. доказать, что в ряде Фарея любая дробь является медиантой двух соседних. Насколько известно, его доказательство было неверным, а правильное доказательство предложил несколько позже Коши (Cauchy). Впрочем, ещё в 1802 г. математик Харос (Haros) в одной из своих работ пришёл практически к тем же результатам. Последовательности Фарея обладают и множеством собственных интересных свойств, однако наиболее очевидна их связь с деревом Штерна-Броко: фактически, последовательность Фарея получается удалением некоторых ветвей из дерева. Или можно говорить, что для получения последовательности Фарея нужно взять множество дробей, получаемое при построении дерева Штерна-Броко на бесконечной итерации, и оставить в этом множестве только дроби со знаменателями, не превосходящими Из алгоритма построения дерева Штерна-Броко следует и аналогичный алгоритм для последовательностей Фарея. На нулевой итерации включим в множество только дроби Вычислим длину последовательности Фарея. Последовательность Фарея порядка Литература
|