Дерево Штерна — Броко
Дерево Штерна — Броко — способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева.
В каждом узле дерева Штерна — Броко (иногда также называемого деревом Фарея) стоит медианта [math]\displaystyle{ \frac{m+m'}{n+n'} }[/math] дробей [math]\displaystyle{ \frac{m}{n} }[/math] и [math]\displaystyle{ \frac{m'}{n'} }[/math], стоящих в ближайших к этому узлу левом и правом верхних узлах. Начальный кусок дерева Штерна — Броко в этом случае выглядит так:
Близким по построению к дереву Штерна — Броко является дерево Калкина — Уилфа, в котором дробь [math]\displaystyle{ \frac{1}{1} }[/math] является корнем, а все прочие узлы заполняются по следующему алгоритму: каждая вершина [math]\displaystyle{ \frac{m}{n} }[/math] имеет двух потомков: левого [math]\displaystyle{ \frac{m}{m+n} }[/math] и правого [math]\displaystyle{ \frac{m+n}{n} }[/math].
История
В книге Р. Грэма, Д. Кнута, О. Паташника «Конкретная математика» открытие «дерева Штерна — Броко» связывается с именами Морица Штерна (1858) и Ахилла Броко (1860). Однако аналогичное построение в форме «дерева Калкина-Уилфа» было известно ещё древнегреческим математикам. Оно описано под именем «порождения всех отношений из отношения равенства как из матери и корня» в двух математических обзорах II в. н. э., принадлежащих Никомаху Герасскому и Теону Смирнскому. Теон сообщает, что эта конструкция была известна Эратосфену Киренскому — знаменитому учёному, жившему в III в. до н. э.
Свойства
- Все дроби в деревьях Калкина — Уилфа и Штерна — Броко несократимы.
- Каждая несократимая дробь появляется в дереве ровно один раз.
Для дерева Калкина — Уилфа эти свойства легко доказываются, если заметить, что каждому шагу по дереву в направлении к корню соответствует элементарный шаг вычитания меньшего числа из большего в алгоритме Евклида для поиска наибольшего общего делителя.
Для дерева Штерна — Броко доказательство основано на следующей лемме: если [math]\displaystyle{ p_1/q_1\lt p_2/q_2 }[/math] — дроби в двух соседних узлах дерева, то [math]\displaystyle{ q_1p_2-q_2p_1=1 }[/math].
Система счисления Штерна — Броко
Можно воспользоваться символами L и R для идентификации левой и правой ветви при продвижении вниз по дереву от корня, дроби 1/1, к некоторой определённой дроби. Тогда каждая положительная дробь получает единственное представление в виде строки состоящей из символов «R» и «L» (дроби 1/1 соответствует пустая строка). Такое представление положительных рациональных чисел назовём системой счисления Штерна — Броко. К примеру, обозначение LRRL соответствует дроби 5/7.
См. также
- Ряд Фарея
- Цепная дробь
- Подходящая дробь
- Система счисления
- Алгоритм Евклида
- Дерево Калкина — Уилфа
- Окружность Форда
Литература
- Айгнер М., Циглер Г. Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней. — М.: Мир, 2006. — С. 105—109. — 256 с. — ISBN 5-03-003690-3..
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. — М.: Мир, 1998. — 704 с. — ISBN 5-03-001793-3..
- Щетников А. И. Алгоритм разворачивания всех числовых отношений из отношения равенства и идеальные числа Платона // ΣΧΟΛΗ. — 2008. — Т. 2. — С. 55—74. — ISSN 1995-4328.
- Brocot A. Calcul des rouages par approximation, nouvelle méthode // Revue Chonométrique. — 1861. — Т. 3. — С. 186—194.
- Stern M. Über eine zahlentheoretische Funktion // Journal für die reine und angewandte Mathematik. — 1858. — Т. 55. — С. 193—220.
Ссылки
- The Stern — Brocot or Farey Tree (англ.)
- Кноп К. Недвоичная система // Домашний компьютер. — 2001. — № 8. Архивировано 12 марта 2007 года.
- Онлайн-демонстратор приближения рациональных чисел при помощи дерева Штерна — Броко