Бинарное дерево Штерна-Броко
Материал из Википедии — свободной энциклопедии
|
Для улучшения статьи желательно:
|
Существует способ построения всех неотрицательных несократимых дробей m/n, где n и m — взаимно простые целые числа, т.е. не имеющие одинаковых простых сомножителей. Суть способа в том, чтобы начать с двух дробей 0/1 и 1/0, а затем повторить необходимое число раз следующую операцию: вставить 
между двумя соседними дробями 
и 
.
Всю совокупность вставок можно представить в виде бинарного дерева, называемого деревом Штерна-Броко, начало которого выглядит так:
Каждый узел дерева имеет вид , где — ближайший предок сверху слева, а — сверху справа.
Пример:
| номер операции | Исходная последовательность | Действия | Конечная последовательность |
|---|---|---|---|
| 1 | 0/1 и 1/0 |  |
0/1 1/1 1/0 |
| 2 | 0/1 1/1 1/0 |  ,  |
0/1 1/2 1/1 2/1 1/0 |
| 3 | 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 |
Можно воспользоваться символами L и R для идентификации левой и правой ветви при продвижении вниз по дереву от корня, дроби 1/1, к некоторой определенной дроби. Тогда каждая положительная дробь получает единственное представление в виде строки состоящей из символов "R" и "L" (дроби 1/1 соответствует пустая строка). Такое представление положительных рациональных чисел назовем системой счисления Штерна-Броко.
Легко убедиться, что 
. Это значение (медианта) не лежит точно посередине между предшественниками, поэтому для достижения некоторых дробей нужно сделать большее число шагов, чем для других с тем же знаменателем. Если выполнять нахождение медиант только в случае если значение её знаменателя не превосходит N, то можно получить последовательность Фарея порядка N - множество всех несократимых дробей от 0 до 1, знаменатели которых не превосходят N, расположенных в возрастающем порядке.
Дерево Штерна-Броко можно использовать как систему счисления для представления рациональных чисел. Движение вниз по левой ветке будем обозначать L, а по правой - R. Обозначение LRRL соответствует дроби 5/7.
Для определения дроби записанной в данной системе счисления можно воспользоваться следующим кодом на C#
public static void fromSB(string s)
{
int m = 0, n = 1, m1 = 1, n1= 0;
foreach (char c in s)
{
if (c == 'L')
{
m1 = m + m1;
n1 = n + n1;
}
else
{
m = m + m1;
n = n + n1;
}
}
m = m + m1; n = n + n1;
Console.WriteLine("Ответ: {0}/{1}", m, n);
}
Для обратного преобразования можно воспользоваться следующим кодом (учтите, что для некоторых дробей этот процесс может оказаться достаточно долгим на данной машине. К примеру, для дроби 
потребуется 562 операции вычитания, не считая всех прочих операций).
public static string toSB(int m, int n)
{
StringBuilder sb = new StringBuilder();
if ((m > 0) && (n > 0))
{
while (m != n)
{
if (m < n )
{
sb.Append('L');
n = n - m;
}
else
{
sb.Append('R');
m = m - n;
}
}
}
return sb.ToString();
}
