Введение
Начну статью с того, что расскажу, как я познакомился с этой изящной конструкцией. Занимаясь олимпиадным программированием, мы с моим преподавателем решали много интересных задач. И вот однажды мне попалась следующая задача:
Распечатать в порядке возрастания все несократимые дроби, знаменатель которых не превосходит заданного числа
Когда я прочитал условие задачи до конца, она не показалась мне сложной (она таковой и не является). Первое, что пришло мне в голову — это просто перебрать все знаменатели от
Такое решение верное, и задача прошла все назначенные ей тесты. Однако мой преподаватель сказал, что задачу можно решить намного красивее. Так я и познакомился с замечательной конструкцией: деревом Штерна — Броко.
Дерево Штерна — Броко
Дерево Штерна — Броко было открыто независимо друг от друга немецким математиком Мерицем Штерном и французским часовщиком Ахиллом Броко. Данное дерево позволяет построить множество всех несократимых неотрицательных дробей.
Для начала введем следующий термин: пусть даны две дроби
Построение дерева начнем с двух фиктивных дробей:
— обозначающее
— обозначающее бесконечность «в несократимом виде»
![](https://habrastorage.org/webt/bi/na/mp/binampxwtaun2b22t4clyu9xtx4.png)
Дерево Штерна — Броко не было бы столь интересным, если бы не его замечательные особенности (а их у него немало):
- несократимость дробей
- упорядоченность дробей
- наличие абсолютно всех дробей
Пусть
Теперь покажем, что при вставке медианты между дробями
Имеем:
Вот почему дроби несократимы — числитель и знаменатель всегда взаимно просты. На первый вопрос ответили! Переходим ко второму.
Почему дроби будут упорядочены? Для ответа на этот вопрос достаточно показать, что медианта двух дробей всегда лежит между ними.
Пусть
Ну и последнее: почему мы не можем пропустить хотя бы одну дробь, то есть почему все дроби присутствуют в дереве?
Если бы нам надо было найти определенную дробь в дереве, то как бы мы это сделали? Процесс поиска фактически является бинарным поиском. Мы сравниваем искомую дробь с медиантой, и возможны
- она равна медианте, поиск завершен
- медианта больше дроби, тогда рекурсивно отправляемся искать в левое поддерево
- медианта меньше дроби, тогда рекурсивно отправляемся искать в правое поддерево
Последовательность Фарея
Ну а что же с исходной задачей? Вроде бы дерево Штерна — Броко нам подходит, но в нем есть дроби большие единицы, которые являются лишними. Однако что нам мешает взять вместо фиктивных дробей
![](https://habrastorage.org/webt/wo/zk/xh/wozkxhutvimjewihlohaulne-5q.png)
Строго математически эту последовательность можно записать так:
Фактически исходную задачу можно переформулировать следующим образом: построить последовательность Фарея
def farei_sequence(n):
result = ['0/1']
def farei_sequence_rec(n, x, y, z, t):
a, b = x + z, y + t
if b <= n:
farei_sequence_rec(n, x, y, a, b)
result.append(f'{a}/{b}')
farei_sequence_rec(n, a, b, z, t)
farei_sequence_rec(n, 0, 1, 1, 1)
result.append('1/1')
return result
print(*farei_sequence(3)) # 0/1 1/3 1/2 2/3 1/1
print(*farei_sequence(4)) # 0/1 1/4 1/3 1/2 2/3 3/4 1/1
print(*farei_sequence(5)) # 0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
print(*farei_sequence(6)) # 0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1
Дроби Фарея также можно использовать при упрощении математических выражений.
Например, требуется посчитать выражение
Стандартный способ приведения к общему знаменателю нам неинтересен. Представим дроби в виде разности соседних дробей ряда Фарея:
Дерево как система счисления
Оказывается, дерево Штерна — Броко можно использовать в качестве системы счисления (символического способа) для представления рациональных чисел.
Но как сопоставить с каждой дробью некоторую последовательность символов? Для этого еще раз вспомним алгоритм поиска определенной дроби в дереве.
Пусть нам надо найти дробь
![](https://habrastorage.org/webt/-9/v2/wn/-9v2wntiu_osbyhbiai87yrpt9k.png)
Приближение действительных чисел рациональными
Если в процессе поиска дроби в дереве Штерна-Броко вместо дроби передать действительное число, то можно получить его приближение рациональными дробями. Попробуем приблизить число
Исходя из этого представления, можно предположить, что дроби
? Если статья оказалась интересной и полезной для вас, подписывайтесь на телеграм-канал «Поколение Python ?», который я веду вместе со своей командой.