| rdfs:comment
| - Существует способ построения всех неотрицательных несократимых дробей m/n, где n и m — взаимно простые целые числа, т.е. не имеющие одинаковых простых сомножителей. Суть способа в том, чтобы начать с двух дробей 0/1 и 1/0, а затем повторить необходимое число раз следующую операцию: вставить между двумя соседними дробями и . Метод имеет прямое отношение к ряду Фарея. Всю совокупность вставок можно представить в виде бинарного дерева, называемого деревом Штерна-Броко, начало которого выглядит так: thumb|center|550px } }
|
| abstract
| - Существует способ построения всех неотрицательных несократимых дробей m/n, где n и m — взаимно простые целые числа, т.е. не имеющие одинаковых простых сомножителей. Суть способа в том, чтобы начать с двух дробей 0/1 и 1/0, а затем повторить необходимое число раз следующую операцию: вставить между двумя соседними дробями и . Метод имеет прямое отношение к ряду Фарея. Всю совокупность вставок можно представить в виде бинарного дерева, называемого деревом Штерна-Броко, начало которого выглядит так: thumb|center|550px Каждый узел дерева имеет вид , где — ближайший предок сверху слева, а — сверху справа. Можно воспользоваться символами 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(); }
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)