Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Об одной грациозной конструкции

Anna | 18.06.2014 | нет комментариев

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

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

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

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

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

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

Для начала введем дальнейший термин: Пускай даны две дроби . Тогда дробь  — именуется ихмедиантой.
Построение дерева начнем с 2-х фальшивых дробей:
 — обозначающее 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) s_rqvmk!
Отчего дроби будут упорядочены? Для результата на данный вопрос довольно показать, что медианта 2-х дробей неизменно лежит между ними.

Пускай  — две последовательные дроби в дереве и . Покажем, что . Приводя дроби к всеобщему знаменателю и рассматривая условие  получаем:

Рассматривая, что знаменатели у последних дробей позитивные, числители обязаны быть негативными, а это и есть начальное неравенство xt — yz ь в качестве системы счисления (символического метода) для представления разумных чисел.

Но как сопоставить с всякой дробью некоторую последовательность символов? Для этого еще раз припомним алгорифм поиска определенной дроби в дереве.

Пускай нам нужно обнаружить дробь  в дереве. Начинаем поиск с медианты . Переход по левому поддереву обозначим буквой L, по правому поддереву буквой R. Таким образом, числу  соответствует последовательность символов LLRL (см. рисунок).

Таким образом, мы можем всякой разумной дроби поставить в соответствие последовательность букв L И R (либо же совсем можем заменить их на 0 и 1 для полного соответствия двоичной системе счисления).

 

Приближение действительных чисел разумными


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

Испробуем приблизить число . Получим такой итог RRRLLLLLLLRRRRRRRRRRRRRRRLRRRR…

Исходя из этого представления, дозволено предположить, что дроби


служат простейшими разумными приближениями к числу  сверху и снизу. Таким образом дозволено заключить, что .

На этом мы, вероятно, и закончим наше знакомство с деревом Штерна-Броко. Верю, статья оказалась увлекательной для прочтения.

 

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB