Дерево на системы счисления

Занятие 5

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

Немного похоже на бинарный поиск работает дерево Штерна-Броко, позволяющее получить множество всех несократимых положительных дробей `m/n` . Начиная с двух дробей 0/1 и 1/0, нужно несколько раз выполнить операцию вставки дробей `(m+m’)/(n+n’)` между двумя соседними дробями `m/n` и `/` .

После первого шага получается последовательность 0/1, 1/1, 1/0, после второго – 0/1, 1/2, 1/1, 2/1, 1/0, после третьего – 0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0. Верхние уровни дерева выглядят так:

Легко убедиться, что `m/n\ /` . Это значение (медианта) не лежит точно посередине между предшественниками, поэтому для достижения некоторых дробей нужно сделать большее число шагов, чем для других с тем же знаменателем. Если выполнять нахождение медиант только в случае если значение её знаменателя не превосходит `N` , то можно получить последовательность Фарея порядка `N` – множество всех несократимых дробей от 0 до 1, знаменатели которых не превосходят `N` , расположенных в возрастающем порядке.

Дерево Штерна-Броко можно использовать как систему счисления для представления рациональных чисел. Движение вниз по левой ветке будем обозначать L, а по правой – R. Обозначение LRRL соответствует дроби 5/7. Для преобразования дроби `m/n` в эту систему счисления можно использовать следующую программу.

void toSB(int m, int n) < while(m!=n) < if(m else < putchar('R'); m-=n; >> >

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

Используя аналог алгоритма бинарного поиска можно построить представление Штерна-Броко для иррациональных чисел. Анализируя в какой промежуток попадает число `e` =2.718281828459045, мы получим следующую последовательность медиант 1/1, 2/1, 3/1, 5/2, 8/3, 11/4, 19/7, 30/11, 49/18, 68/25, 87/32, 106/39, 193/71, 299/110, …, которые будут наилучшими рациональными приближениями к числу `e` сверху или снизу. Интересно, что в записи числа `e` в системе Штерна-Броко есть закономерность: `e=»RL»^0″RLR»^2″LRL»^4″RLR»^6″LRL»^8″RLR»^10″LRL»^12L…` .

typedef long long ll; pair calc(ll a, ll b = 1000000000000000000LL) < ll p1 = 0, p2 = 1; ll q1 = 1, q2 = 0; while (b != 0) < ll t = a / b; p1 += t * p2; q1 += t * q2; a -= t * b; if (q1 > T9) break; swap(p1, p2); swap(q1, q2); swap(a, b); > return ; >

Источник

Дерево на системы счисления

Можно интерпретировать Н-фрактал на рис. 0,2 как план города, непригодного для уличного движения, ибо дорога блокируется во многих местах. Н-фрактал относится к так называемым «дендритам», от греческого «dendron»—дерево.

Это название очень подходящее, потому что структура такого фрактала аналогична структуре дерева: ствол разделяется на две отдельные ветви, каждая из которых является стволом для следующих, более мелких, ветвей и т.д. Если этот процесс продолжить до бесконечности, то будем иметь бесконечное число уровней. Дерево на рис. 1.1 строится именно по такому принципу. На каждом уровне вертикальные линии разделяются на две. Показатель уменьшения выберем, например, равным 1/2. Вертикальные ветви удваиваются на каждом уровне, тогда как их длины одновременно уменьшаются вдвое. Каждая горизонтальная линия — это удвоенная длина вертикальной линии, расположенной выше. Если мы зададим ветвь на самом нижнем уровне длиной 1, то к вертикальной длине каждый раз прибавляется 1:

1 + 2 * 1/2 + 4 * 1/4 + 8 * 1/8 + 16 * 1/16 + .

Что бросается в глаза на рис. 1.1 (p = 7; p — число уровней) — это самоподобие. Каждая вертикальная ветвь может рассматриваться как ствол целого дерева — масштабированная копня всей фигуры. Чем выше расположены ветви, тем они теснее. Их длина всегда будет уменьшаться по сравнению с предыдущим уровнем. Суммируя длины вертикальных ветвей (по одной на каждом уровне), получим ряд:

Разбиение какого-либо множества на группы из двух элементов, или, наоборот, комбинирование в группы из двух элементов, характерно для двоичной системы счисления (десятинная система основана на разбиении или комбинировании в группы из 10). Фрактал-дендрит на рис. 1.1 является, возможно, самым простым примером семейства фракталов, в котором структура системы счисления представляется геометрически. Поэтому обратимся к системам счисления.

Мы едва ли задумываемся, что повсеместно используемый в наши дни (десятичный) способ счисления является результатом долгой культурно-исторической эволюции. Ее основы были заложены индийцами 14 веков назад, а, возможно, и ранее — китайцами. Современные десятичные дроби начали использоваться в Европе Симоном Стевином (1548 — 1620). И нам десятичная система, кажется, очень простой и удобной. Запись любого числа находится разложением его по степеням 10:

1998 = 1 * 10 0 + 9 * 10 2 + 9 * 10 1 + 8 * 10 0

Господство десятичной системы связано, скорее всего, с тем фактом, что люди имеют десять пальцев. Где-то на другой планете во Вселенной, возможно, живут восьмипалые существа, использующие восьмеричную систему.

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

Около 5000 лет назад в Месопотамии шумеры развили шестидесятеричную систему счисления, которая удовлетворяла практическим потребностям (в агрокультуре, астрологии). Им мы обязаны делением времени на часы, минуты, секунды.

Другие люди, например, майя, развили двадцатеричную систему. В наше время доминирует десятичная система счисления, а в компьютерах используется двоичная.

Двоичная система

Пример: 423 = 110100111:
110100111 = 2 8 + 2 7 + 0 * 2 6 + 2 5 + 0 * 2 4 + 0 * 2 3 + 2 3 + 2 2 + 2 1 — 2 0 .
Таблица умножения:

Недостаток — длинная запись числа.

Четверичная и восьмеричная системы

423 = 110100111 — двоичная система.
423 = 12213 — четверичная система:
423 = 1 * 4 4 + 2 * 4 3 + 2 * 4 2 + 1 * 4 1 + 3 * 4 0 .
423 = 647 = 6 * 8 2 + 4 * 8 1 — 7 * 8 0 — восьмиричная система.

Троичная система

423 = 1 * 243 + 2 * 81 + 2 * 9 = 1 * 3 5 — 2 * 3 4 — 0 * 3 3 + 2 * 3 2 + 0 * 3 1 + 0 * 3 0 .
Итак, 423 равно 120200 в троичной системе. В этой системе таблица умножения лишь немного сложнее, чем в двоичной:

X	0	1	2
0	0	0	0
1	0	1	2
2	0	2	1

Рассмотрим дендрит, представленный на рис. 1.2. Структура этого дендрита основана на троичной системе. Из одной точки под утло 120° друг к другу выходят три главные ветви. Каждый из трех концов сам является точкой, из которой выходят три более мелкие ветви, и т.д. Направление вправо мы помечаем «О», направление влево-вверх — «1», влево-вниз «2».

Используя данный алгоритм, можно построить троичное дерево на компьютере (рис. 1.3, где число шагов p=6).

Решето Серпинского

В 1915 голу польский математик Вацлан Серпинский придумал красивый объект, похожий на «троичное» дерево. Сейчас он известен как решето (сито) Серпинского. Процесс начинается с равностороннего треугольника.

Фрактал Кантора

Кантор (1845 — 1918) явился одним из основателей теории множеств. Он также придумал один из старейших фракталов (1883). Построение этого фрактала показано на рис. 1.6.

Из исходного отрезка единичной длины выбрасывается интервал (1/3.2/3). Далее из каждого оставшегося отрезка выбрасываем средние трети и т. д. В пределе получим фрактал Кантора (на Западе подобные множества называют иногда пылью Кантора).

После трех шагов будет 2 3 = 8 отрезков, и каждый имеет длину 3 -3 = 1/27. После n шагов получим 2 n отрезков, каждый длины 3 -n . Общая длина оставшихся отрезков равна (2/3) n . Она стремится к нулю, когда n → ∞. Это означает, что множество Кантора имеет меру Лебега (то есть, грубо говоря, общую длину), равную нулю, и нулевую топологическую размерность. Далее мы узнаем, что есть другое определение размерности, в соответствии с которым множество Кантора имеет размерность 0.6309. Эта размерность дробное (нецелое) число. Отсюда возник и термин «фрактальная размерность».

Арифметические свойства фрактала Кантора

Так как отрезки делятся на три части, то будем использовать троичную систему. Мы имеем дело с числами от 0 до 1, поэтому арифметический метод представления фрактала Кантора включает разложение дробей вида

где c₁, c₂, c₃. могут быть числа О, 1, 2. Например,

0.3 = 3/10 = 0.0220; 0.5 = 1/2 = 0.1; 0.8 = 4/5 = 0.2101.

Построение начинается с отрезка [О; 1]. Отмечается одна треть отрезка в середине (то есть все члены, имеющие троичную дробь, начинающуюся с единицы). На следующем шаге мы делаем то же для второго положения точки (рис. 1.6) и т. д. В итоге выбрасываем все числа, которые имеют 1 в их разложении, как троичной дроби.

Диаграмма (рис. 1.6) показывает, что многие числа исчезают на первом шаге, например число 0.5 (десятичное). Число 0.8 исчезает на втором шаге, так как O.8 = 0.2101. Число 0.3 = 0.0220 никогда не исчезает. Таким образом, множество Кантора можно определить как множество всех чисел между нулем и единицей, которые можно записать в троичной системе, используя лишь «0» и «2». Числа «О» и «1» также включаются, ибо 1 = 0.2 (в троичном виде: 1 ≈ 0.2222. подобно 1 ≈ 0.9999. в десятичной системе).

Источник

Дерево на системы счисления

Вставить между двумя соседними дробями и

Например, первый шаг дает нам одно новое вхождение между 0/1 и 1/0:

Следующий шаг даст еще два:

Следующий шаг даст еще четыре:

0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0

Весь массив можно рассматривать, как бесконечное бинарное дерево, чьи верхние уровни выглядят так:

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

Фактически мы можем рассматривать дерево Штерна-Броко как систему счисления для представления рациональных чисел, потому что каждая положительная, сокращенная дробь встречается в дереве только один раз. Будем использовать буквы L и R для обозначения того, двигаемся мы по левой или по правой ветви дерева, когда спускаемся от корня дерева к определенной дроби; тогда строка, состоящая из определенной последовательности этих L и R, уникальным образом определяет положение в дереве. Например, LRRL означает, что мы идем по левой ветви от 1/1 к 1/2, затем по правой к 2/3, затем по правой к 3/4, затем по левой к 5/7. Мы можем рассматривать LRRL как представление 5/7. Любая положительная дробь представляется таким путем уникальным строкой, состоящей из L и R.

Ну, скажем, почти любая дробь. Дроби 1/1 соответствует пустая строка. Мы будем обозначать ее I, так как это похоже на 1 и является первой буквой слова «identity» (единица).

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

Вход. Состоит из нескольких тестов. Каждый тест состоит из двух взаимно простых натуральных чисел m и n. Последний тест содержит две единицы и не обрабатывается.

Выход. Для каждого теста выведите в отдельной строке представление заданной дроби в системе счисления Штерна-Броко.

Источник