Дерево Штерна-Броко является бинарным деревом фракций , где каждая фракция приобретается путем добавления числителе и знаменателя двух фракций соседних его в указанных выше уровнях.
Он генерируется, начиная с 0/1
и 1/0
как «фракции конечной точки», и оттуда, итерируя, помещая одну дробь между каждой последовательной парой дробей, добавляя вместе числители и знаменатели этих дробей, например, так:
0. 0/1 1/0
1. 0/1 1/1 1/0
2. 0/1 1/2 1/1 2/1 1/0
3. 0/1 1/3 1/2 2/3 1/1 3/2 2/1 3/1 1/0
4. 0/1 1/4 1/3 2/5 1/2 3/5 2/3 3/4 1/1 4/3 3/2 5/3 2/1 5/2 3/1 4/1 1/0
В каждой итерации дерева Штерна-Броко ( n
итерация) 2^n + 1
в последовательности присутствуют элементы, которым мы можем приписать дробь от 0/2^n
до 2^n/2^n
. Каждая новая итерация просто вставляет одну дробь «наполовину» между каждой парой последовательных дробей.
Это делает дерево Штерна-Броко взаимно однозначным отображением между положительными рациональными числами и двоичными дробями между 0 и 1, что также служит доказательством того, что два набора имеют одинаковую мощность.
Ваша задача - написать программу или функцию, которая, учитывая числитель и знаменатель положительного рационального числа в самых низких терминах, определяет двоичную дробь, которая соответствует позиции этой дроби в дереве Штерна-Броко.
Примеры входов и выходов приведены ниже:
2/3 -> 3/8 (4th number in iteration 3)
4/7 -> 9/32 (between 1/2 and 3/5 in the chart above)
1/1 -> 1/2 (middle number in the first iteration)
Входы, которые вам не нужно поддерживать, но включены для справки:
0/1 -> 0/1 (0/1 is considered the left number)
1/0 -> 1/1 (1/0 is considered the rightmost number)
Самая короткая программа на любом языке для достижения этой цели побеждает.
1/1 => 1
,1/2 => 2
,2/1 => 3
,1/3 => 4
и т.д.). Если число, сгенерированное таким образом для узла, равноn
, то2^lg n
(двоичный журнал) - это самый высокий установленный битn
, и желаемая двоичная дробь равна(2*(n - 2^lg n) + 1) / 2^(lg n + 1)
. (Любой, кто пытается использовать ассемблерное решение в наборе команд с битом-наивысшего набора, вероятно, захочет использовать этот подход).Ответы:
GolfScript (
49 4846 символов)или же
Оба являются функциями, которые принимают числитель и знаменатель в стеке и оставляют числитель и знаменатель в стеке. Демо онлайн .
Основная идея выражена в псевдокоде в разделе 4.5 « Бетонная математика » (p122 в моем издании):
Если строка Ls и Rs интерпретируется как двоичное значение с L = 0 и R = 1, то в два раза это значение плюс один является числителем, а знаменатель на один бит длиннее.
Как точка интереса для Golfscripters, это один из тех редких случаев, когда я нашел разворачивание полезным. (Хорошо, я использую его только как счетчик циклов, но это лучше, чем ничего).
источник
Mathematica,
130 114111 символовПример:
источник
Рубин,
132125Рубин и игра в гольф эталонное решение от @JoeZ.
Примеры использования:
источник
Ruby (69 символов)CoffeeScript (59 символов)Это функция, которая принимает числитель и знаменатель в качестве аргументов и возвращает массив, содержащий числитель и знаменатель после биекции.
Онлайн демо
В нем используется тот же подход, что и в моем решении GolfScript, описанном выше, но он гораздо более читабелен, потому что я могу использовать 4 переменные, не беспокоясь о том, чтобы упаковать и распаковать в массив. Я выбрал CoffeeScript, потому что он не содержит префиксов переменных
$
(20 символов сохранены, например, в PHP), имеет короткий синтаксис определения функции, который допускает значения параметров по умолчанию (поэтому нет необходимости переноситьf(a,b,x,y)
в функциюg(a,b) = f(a,b,0,1)
) и позволяет использовать логические значения в качестве целых чисел в выражения с полезными значениями. Для тех, кто этого не знает, у CoffeeScript нет стандартного тернарного оператора в стиле C (C?P:Q
), но я могу заменить егоC&&P||Q
здесь, потому чтоP
он никогда не будет ложным.Возможно более элегантный, но бесспорно менее короткая, альтернатива заменить повторное вычитание с делением и по модулю:
(65 символов; онлайн демо ). Написание этого таким образом выявляет связь с алгоритмом Евклида.
источник
a<b
которых вы экономите один символ. Встраиваниеc
дает еще два. Вы можете также рассмотреть синтаксисf=->a,b,x=0,y=1{...}
для еще более короткого определения.c=a<b ?
с дополнительным пробелом послеb
. В противном случае вопросительный знак рассматривается как частьb
.Питон - 531
Разгаданное в Python решение, которое будет служить последним справочным решением:
Он просто выполняет двоичный поиск между дробями, используя преимущество того факта, что посредник любых двух дробей всегда будет между значениями этих двух дробей.
источник
GolfScript, 54 символа
Входные данные должны быть указаны в STDIN в форме, указанной в задании. Вы можете попробовать код онлайн .
источник
Mathematica 138
Не такой обтекаемый, как процедура с алефальцами, но это было лучшее, что я смог сделать до сих пор.
тестирование
источник
JavaScript 186
может быть меньше, но мне нравится читаемый гольф
источник
Haskell , 125 байт
Попробуйте онлайн!
Ввод и вывод в виде пары
(n,d)
.Краткое объяснение:
n
создаёт следующую строку из предыдущей, просматривая каждую пару дробей и вставляя новую между первой и рекурсивной (что и поместит вторую дробь прямо там). Базовый случай очень прост, поскольку в основном это просто функция тождества.t
Функция перебирает эту функцию на неопределенное время, основанную от начального состояния с помощью всего двух граничных фракций.t
затем индексирует каждую строку (i
) и каждый элемент в строке (j
) и ищет первую дробь, которая соответствует тому, что мы ищем. Когда это находит, это даетj
как числитель и2^i
как знаменатель.источник