Об одной изящной конструкции

в 20:00, , рубрики: Алгоритмы, деревья, математика, структуры данных, метки: , ,

Введение

Начну статью с того, что расскажу, как я познакомился с этой изящной конструкцией. Занимаясь олимпиадным программированием, мы с моим преподавателем решали много интересных задач. И вот однажды мне попалась следующая задача:

Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит n, n<=100.

Прочитав условие задачи до конца, она не показалась мне сложной (она таковой и не является). Первое, что пришло мне в голову это просто перебрать все знаменатели от 2 до n и для каждого знаменателя перебрать числители от 1 до знаменателя, при условии, что числитель и знаменатель взаимно просты. Ну, а за тем отсортировать их по возрастанию.

Такое решение верно и задача прошла все назначенные ей тесты. Однако, мой преподаватель сказал, что задачу можно решить намного красивее (он уже сталкивался с этой конструкцией). Так я и познакомился с этой замечательной конструкцией — деревом Штерна-Броко.

Дерево Штерна-Броко

Дерево Штерна-Броко было открыто независимо друг от друга немецким математиком Мерицем Штерном и французским часовщиком Ахиллом Броко. Данное дерево позволяет построить множество всех несократимых, неотрицательных дробей.

Для начала введем следующий термин: Пусть даны две дроби Об одной изящной конструкции. Тогда дробь Об одной изящной конструкции — называется их медиантой.
Построение дерева начнем с двух фиктивных дробей:
Об одной изящной конструкции — обозначающее 0;
Об одной изящной конструкции — обозначающее бесконечность «в несократимом виде».

На каждой последующей итерации между дробями вставляется их медианта, и эта же операция повторяется для каждой из получившихся пар дробей:
Об одной изящной конструкции

Продолжая данный процесс до бесконечности, мы можем построить все множество несократимых, неотрицательных дробей.

Дерево Штерна-Броко не было б столь интересным, если бы не его замечательные особенности, а их у него не мало:

  1. несократимость дробей;
  2. упорядоченность дробей;
  3. наличие абсолютно всех дробей.

Можно задаться вопросами: почему все дроби несократимы? Почему упорядочены? Почему ни одна дробь не может встретиться более чем один раз? Ответы на эти вопросы достаточно просты. Нужно лишь немного подробнее рассмотреть структуру этого дерева.

Пусть Об одной изящной конструкции — две последовательные дроби дерева Штерна-Броко. Можно заметить, что для них выполняется равенство 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 случая:

  1. она равна медианте, поиск завершен;
  2. медианта больше дроби, тогда рекурсивно отправляемся искать в левое поддерево;
  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

Источник

Поделиться

* - обязательные к заполнению поля