- Дерево Штерна — Броко
-
Дерево Штерна — Броко
Дерево Штерна — Броко — способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева.
В первом варианте построения дерева Штерна — Броко дробь является корнем, а все прочие узлы заполняются по следующему алгоритму: каждая вершина имеет двух потомков: левого и правого .
Во втором варианте построения в каждом узле дерева Штерна — Броко (называемого в этом случае также деревом Фарея) стоит медианта дробей и , стоящих в ближайших к этому узлу левом и правом верхних узлах. Начальный кусок дерева Штерна — Броко в этом случае выглядит так:
Содержание
История
В книге Р. Грэхема, Д. Кнута, О. Паташника Конкретная математика открытие «дерева Штерна — Броко» связывается с именами Морица Штерна (1858) и Ахилла Броко (1860). Однако в действительности это построение было известно ещё древнегреческим математикам. Оно описано под именем «порождения всех отношений из отношения равенства как из матери и корня» в двух математических обзорах II в. н. э., принадлежащих Никомаху Геразскому и Теону Смирнскому. Теон сообщает, что эта конструкция была известна Эратосфену Киренскому — знаменитому учёному, жившему в III в. до н. э.
Свойства
- Все дроби в дереве Штерна — Броко несократимы;
- Каждая несократимая дробь появляется в дереве ровно один раз.
Эти свойства легко доказываются, если заметить, что каждому шагу по дереву в направлении к корню соответствует элементарный шаг вычитания меньшего числа из большего в алгоритме Евклида для поиска наибольшего общего делителя.
Система счисления Штерна — Броко
Можно воспользоваться символами L и R для идентификации левой и правой ветви при продвижении вниз по дереву от корня, дроби 1/1, к некоторой определённой дроби. Тогда каждая положительная дробь получает единственное представление в виде строки состоящей из символов «R» и «L» (дроби 1/1 соответствует пустая строка). Такое представление положительных рациональных чисел назовём системой счисления Штерна — Броко. К примеру, обозначение LRRL соответствует дроби 5/7.
Ссылки
- The Stern — Brocot or Farey Tree(англ.)
- Кноп К. Недвоичная система // Домашний компьютер. — 2001. — № 8.
- Онлайн-демонстратор приближения рациональных чисел при помощи дерева Штерна-Броко
Литература
- Айгнер М., Циглер Г. Доказательства из Книги. Лучшие доказательства со времён Евклида до наших дней. М.: Мир, 2006. С. 105—108.
- Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 2006.
- Щетников А. И. Алгоритм разворачивания всех числовых отношений из отношения равенства и идеальные числа Платона. ΣΧΟΛΗ, 2 (2008), 55—74.
- Brocot A. Calcul des rouages par approximation, nouvelle méthode. Revue Chonométrique, 3 (1861), 186—194.
- Stern M. Über eine zahlentheoretische Funktion. Journal für die reine und angewandte Mathematik, 55 (1858), 193—220.
См. также
Wikimedia Foundation. 2010.
Дерево Штерна — Дерево Штерна Броко способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева. В каждом узле дерева Штерна Броко (иногда также называемого деревом Фарея) стоит медианта… … Википедия
Дерево Штерна-Броко — Дерево Штерна Броко способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева. В первом варианте построения дерева Штерна Броко дробь является корнем, а все прочие узлы заполняются по… … Википедия
Бинарное дерево Штерна-Броко — Дерево Штерна Броко способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева. В первом варианте построения дерева Штерна Броко дробь является корнем, а все прочие узлы заполняются по… … Википедия
Дерево Калкина — Уилфа Дерево Калкина Уилфа (англ. Calkin Wilf tree) ориент … Википедия
Функция Минковского — Функция Минковского. Функция «вопросительный знак» Минковского построенная Германом Минковским монотонная с … Википедия
Рациональное число — Четверти Рациональное число (лат. ratio отношение, деление, дробь) число, представляемое обыкновенной дробью , числитель целое число, а знаменатель … Википедия
Медианта (математика) — У этого термина существуют и другие значения, см. Медианта. Медиантой двух дробей и с положительными знаменателями называется дробь, числитель которой равен сумме числителей, а знаменатель сумме знаменателей, двух данных дробей:… … Википедия
Ряд Фарея — Ряды Фарея (также дроби Фарея, последовательность Фарея или таблица Фарея) семейство конечных подмножеств рациональных чисел. Содержание 1 Определение 2 Пример 3 Свойства … Википедия
Дроби Фарея — Ряды Фарея (также дроби Фарея, последовательность Фарея или таблица Фарея) семейство конечных подмножеств рациональных чисел. Содержание 1 Определение 2 Пример 3 Свойства 4 История … Википедия
Дроби Фэйри — Ряды Фарея (также дроби Фарея, последовательность Фарея или таблица Фарея) семейство конечных подмножеств рациональных чисел. Содержание 1 Определение 2 Пример 3 Свойства 4 История … Википедия