Викия

Математика

Бинарное дерево Штерна-Броко

1457статей на
этой вики
Добавить новую страницу
Обсуждение0 Поделиться

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Шаблон:Rq

Существует способ построения всех неотрицательных несократимых дробей m/n, где n и m — взаимно простые целые числа, т.е. не имеющие одинаковых простых сомножителей. Суть способа в том, чтобы начать с двух дробей 0/1 и 1/0, а затем повторить необходимое число раз следующую операцию: вставить (m+m') \over (n+n') между двумя соседними дробями m \over n и m' \over n'. Метод имеет прямое отношение к ряду Фарея.

Всю совокупность вставок можно представить в виде бинарного дерева, называемого деревом Штерна-Броко, начало которого выглядит так:

Каждый узел дерева имеет вид (m+m') \over (n+n'), где m \over n — ближайший предок сверху слева, а m' \over n' — сверху справа.

Пример:

номер операции Исходная последовательность Действия Конечная последовательность
1 0/1 и 1/0 1+1 \over 1+1 0/1 1/1 1/0
2 0/1 1/1 1/0 0+1 \over 1+1, 1+1 \over 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 \over 1+2} , {1+1 \over 1+2} , {1+2 \over 1+1} , {2+1 \over 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 соответствует пустая строка). Такое представление положительных рациональных чисел назовем системой счисления Штерна-Броко.

Легко убедиться, что {m \over n} < {(m+m') \over (n+n')} < {m' \over n'}. Это значение (медианта) не лежит точно посередине между предшественниками, поэтому для достижения некоторых дробей нужно сделать большее число шагов, чем для других с тем же знаменателем. Если выполнять нахождение медиант только в случае если значение её знаменателя не превосходит 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 \over 563 потребуется 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();
}

Викия-сеть

Случайная вики