Введение
Начну статью с того, что расскажу, как я познакомился с этой изящной конструкцией. Занимаясь олимпиадным программированием, мы с моим преподавателем решали много интересных задач. И вот однажды мне попалась следующая задача:
Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит n, n<=100.
Прочитав условие задачи до конца, она не показалась мне сложной (она таковой и не является). Первое, что пришло мне в голову это просто перебрать все знаменатели от 2 до n и для каждого знаменателя перебрать числители от 1 до знаменателя, при условии, что числитель и знаменатель взаимно просты. Ну, а за тем отсортировать их по возрастанию.
Такое решение верно и задача прошла все назначенные ей тесты. Однако, мой преподаватель сказал, что задачу можно решить намного красивее (он уже сталкивался с этой конструкцией). Так я и познакомился с этой замечательной конструкцией — деревом Штерна-Броко.
Дерево Штерна-Броко
Дерево Штерна-Броко было открыто независимо друг от друга немецким математиком Мерицем Штерном и французским часовщиком Ахиллом Броко. Данное дерево позволяет построить множество всех несократимых, неотрицательных дробей.
Для начала введем следующий термин: Пусть даны две дроби 
. Тогда дробь 
— называется их медиантой.
Построение дерева начнем с двух фиктивных дробей:
— обозначающее 0;
— обозначающее бесконечность «в несократимом виде».
На каждой последующей итерации между дробями вставляется их медианта, и эта же операция повторяется для каждой из получившихся пар дробей:
Продолжая данный процесс до бесконечности, мы можем построить все множество несократимых, неотрицательных дробей.
Дерево Штерна-Броко не было б столь интересным, если бы не его замечательные особенности, а их у него не мало:
- несократимость дробей;
- упорядоченность дробей;
- наличие абсолютно всех дробей.
Можно задаться вопросами: почему все дроби несократимы? Почему упорядочены? Почему ни одна дробь не может встретиться более чем один раз? Ответы на эти вопросы достаточно просты. Нужно лишь немного подробнее рассмотреть структуру этого дерева.
Пусть 
— две последовательные дроби дерева Штерна-Броко. Можно заметить, что для них выполняется равенство yz — xt = 1 (проверьте это сами для нескольких пар дробей). Докажем данное утверждение по индукции для всех дробей в дереве. За базу индукции примем дроби 
и 
, для которых равенство 1*1 — 0*0 = 1 — верно.
Теперь покажем, что при вставке медианты между дробями 
, для которых равенство yz — xt = 1 верно, оно так же будет выполняться и для дробей 
.
Имеем:
Как видите оба этих уравнения эквивалентны исходному, поэтому условие yz — xt = 1 — является инвариантом для всех последовательных дробей в дереве. Ну, а что означает условие yz — xt = 1? Оно означает, что НОД(x, y) = НОД(z, t) = 1. Фактически числа x, y и z, t взаимно просты (Если бы НОД(x, y) ≠ 1, то левая часть делилась бы на НОД, но правая часть делится только на 1, аналогично для НОД(z, t)).
Вот почему дроби несократимы, числитель и знаменатель всегда взаимно просты. На первый вопрос ответили! Переходим ко второму!
Почему дроби будут упорядочены? Для ответа на этот вопрос достаточно показать, что медианта двух дробей всегда лежит между ними.
Пусть 
— две последовательные дроби в дереве и 
. Покажем, что 
. Приводя дроби к общему знаменателю и учитывая условие 
получаем:
Учитывая, что знаменатели у последних дробей положительные, числители должны быть отрицательными, а это и есть исходное неравенство xt — yz ≤ 0. Отсюда делаем вывод, что медианта двух дробей всегда расположена между ними (но не обязательно по середине). Тем самым мы показали упорядоченность дробей в дереве Штерна-Броко.
Ну и последнее! Почему мы не можем пропустить хотя бы одну дробь, то есть, почему все дроби присутствуют в дереве?
Если бы нам надо было найти определенную дробь в дереве, то, как бы мы это сделали? Процесс поиска фактически является бинарным поиском. Мы сравниваем искомую дробь с медиантой и возможны 3 случая:
- она равна медианте, поиск завершен;
- медианта больше дроби, тогда рекурсивно отправляемся искать в левое поддерево;
- медианта меньше дроби, тогда рекурсивно отправляемся искать в правое поддерево.
Очевидно, этот процесс не может выполняться бесконечно долго. Тем самым когда-нибудь мы найдем нашу дробь (додумайте сами почему это так).
Последовательность Фарея
Ну а что же с исходной задачей? Вроде бы дерево Штерна-Броко нам подходит, но в нем есть дроби большие единицы, которые являются лишними. Однако, что нам мешает взять вместо фиктивных дробей 
и 
дроби 
? Ничего!
Такой частный случай дерева Штерна-Броко является основой для последовательности Фарея.
Последовательность Фарея порядка n является множество всех несократимых дробей между 0 и 1, знаменатель которых не превосходит n, которые расположены в порядке возрастания. Обозначается последовательность буквой Fn.
Строго математически эту последовательность можно записать так:
Так выглядит последовательность Фарея для n = 1,...,5
Последовательность названа в честь Джона Фарея известного геолога.
Фактически исходную задачу можно переформулировать следующим образом: построить последовательность Фарея n-порядка. Код на языке C# для ее построения выглядит очень просто, всего 2 рекурсивных вызова:
public static void FareiSequence(int n)
{
Console.WriteLine("{0} / {1}", 0, 1);
FareiSequence(n, 0, 1, 1, 1);
Console.WriteLine("{0} / {1}", 1, 1);
}
private static void FareiSequence(int n, int x, int y, int z, int t)
{
int a = x + z, b = y + t;
if (b <= n)
{
FareiSequence(n, x, y, a, b);
Console.WriteLine("{0} / {1}", a, b);
FareiSequence(n, a, b, z, t);
}
}
Дроби Фарея можно использовать еще при упрощении математических выражений.
Например, требуется посчитать выражение:
Стандартный способ приведения к общему знаменателю нам не интересен. Представим дроби в виде разности соседних дробей ряда Фарея:
Вот так просто можно посчитать это выражение! На этом покончим с последовательностью Фарея и еще раз вернемся к дереву Штерна-Броко.
Дерево как система счисления
Оказывается дерево Штерна-Броко можно использовать в качестве системы счисления (символического способа) для представления рациональных чисел.
Но как сопоставить с каждой дробью некоторую последовательность символов? Для этого еще раз вспомним алгоритм поиска определенной дроби в дереве.
Пусть нам надо найти дробь 
в дереве. Начинаем поиск с медианты 
. Переход по левому поддереву обозначим буквой L, по правому поддереву буквой R. Таким образом, числу 
соответствует последовательность символов LLRL (см. рисунок).
Таким образом, мы можем каждой рациональной дроби поставить в соответствие последовательность букв L И R (или же вовсе можем заменить их на 0 и 1 для полного соответствия двоичной системе счисления).
Приближение действительных чисел рациональными
Если в процессе поиска дроби в дереве Штерна-Броко вместо дроби передать действительное число, то можно получить его приближение рациональными дробями.
Попробуем приблизить число 
. Получим такой результат RRRLLLLLLLRRRRRRRRRRRRRRRLRRRR…
Исходя из этого представления, можно предположить, что дроби
служат простейшими рациональными приближениями к числу 
сверху и снизу. Таким образом можно заключить, что 
.
На этом мы, пожалуй, и завершим наше знакомство с деревом Штерна-Броко. Надеюсь, статья оказалась интересной для прочтения.
Автор: timyrik20
