Последовательность Штерна-Броко представляет собой последовательность, подобную Фибоначчи, которая может быть построена следующим образом:
- Инициализируйте последовательность с помощью
s(1) = s(2) = 1
- Установить счетчик
n = 1
- Добавить
s(n) + s(n+1)
к последовательности - Добавить
s(n+1)
к последовательности - Инкремент
n
, вернитесь к шагу 3
Это эквивалентно:
Среди других свойств последовательность Штерна-Броко может быть использована для генерации любого возможного положительного рационального числа. Каждое рациональное число будет сгенерировано ровно один раз, и оно всегда будет отображаться в самых простых терминах; например, 1/3
это 4-е рациональное число в последовательности, но эквивалентные числа 2/6
и 3/9
т. д. вообще не появятся.
Мы можем определить n-е рациональное число как r(n) = s(n) / s(n+1)
, где s(n)
n-е число Штерна-Броко, как описано выше.
Ваша задача - написать программу или функцию, которая выведет n-е рациональное число, сгенерированное с использованием последовательности Штерна-Броко.
- Описанные выше алгоритмы 1-индексированы; если ваша запись 0 проиндексирована, пожалуйста, укажите в своем ответе
- Описанные алгоритмы предназначены только для иллюстративных целей, вывод может быть получен любым способом (кроме жесткого кодирования)
- Ввод может быть через STDIN, параметры функции или любой другой разумный механизм ввода
- Выход может быть STDOUT, консоль, возвращаемое значение функции или любой другой разумный выходной поток
- Выходные данные должны быть представлены в виде строки в форме
a/b
, гдеa
иb
- соответствующие записи в последовательности Штерна-Броко. Оценка доли до выхода не допускается. Например, для ввода12
, вывод должен быть2/5
, а не0.4
. - Стандартные лазейки запрещены
Это код-гольф , поэтому самый короткий ответ в байтах победит.
Контрольные примеры
Тестовые случаи здесь 1-индексированы.
n r(n)
-- ------
1 1/1
2 1/2
3 2/1
4 1/3
5 3/2
6 2/3
7 3/1
8 1/4
9 4/3
10 3/5
11 5/2
12 2/5
13 5/3
14 3/4
15 4/1
16 1/5
17 5/4
18 4/7
19 7/3
20 3/8
50 7/12
100 7/19
1000 11/39
Запись OEIS: A002487
Превосходное видео Numberphile, обсуждающее последовательность: бесконечные дроби
True
s вместо1
s?True/2
недопустимая дробь (насколько я понимаю). Кроме того,True
не всегда1
- некоторые языки используют-1
вместо этого, чтобы избежать потенциальных ошибок при применении побитовых операторов. [нужная цитата]True
эквивалентен1
иTrue/2
будет1/2
.Ответы:
Желе , 14 байт
Попробуйте онлайн!
Ох, похоже, я могу побить принятый ответ @Dennis, и на этом же языке. Это работает с использованием формулы из OEIS: количество способов выразить (число минус 1) в гипербинарном (то есть двоичном с 0, 1, 2 в качестве цифр). В отличие от большинства программ Jelly (которые работают либо как полная программа, либо как функция), эта программа работает только как полная программа (поскольку она отправляет часть вывода в стандартный вывод и возвращает остальную часть; при использовании в качестве полной программы возвращаемое значение отправляется в stdout неявно, поэтому все выходные данные находятся в одном месте, но это не сработает для отправки функции).
Эта версия программы очень неэффективна. Вы можете создать гораздо более быструю программу, которая работает для всех входных данных до 2ⁿ, поместив n сразу после
ẋ
первой строки; программа имеет производительность O ( n × 3ⁿ), поэтому здесь очень важно сохранить n маленьким. Программа в том виде, в котором она написана, устанавливает n равным входному значению, которое явно достаточно большое, но также явно слишком большое почти во всех случаях (но, эй, оно сохраняет байты).объяснение
Как обычно в моих объяснениях Jelly, текст в фигурных скобках (например
{the input}
) показывает что-то, что автоматически заполняется Jelly из-за отсутствия операндов в исходной программе.Вспомогательная функция (вычисляет n- й знаменатель, т.е. n + 1-й числитель):
Первые пять байтов в основном просто генерируют все возможные гипербинарные числа вплоть до заданной длины, например, при вводе 3 выходные данные
Ḷ
будут [[0,1,2], [0,1,2], [0,1,2 ]] поэтому декартово произведение есть [[0,0,0], [0,0,1], [0,0,2], [0,1,0],…, [2,2,1], [2,2,2]].Ḅ
в основном просто умножает последнюю запись на 1, предпоследнюю запись на 2, предпоследнюю запись на 4 и т. д., а затем добавляет; хотя это обычно используется для преобразования двоичного числа в десятичное, оно может прекрасно обрабатывать цифру 2 и, таким образом, работает и для гипербинарных данных. Затем мы подсчитываем, сколько раз вход появляется в результирующем списке, чтобы получить соответствующую запись в последовательности. (К счастью, числитель и знаменатель следуют в той же последовательности).Основная программа (запрашивает числитель и знаменатель и форматирует вывод):
Почему-то я продолжаю писать программы, которые занимают почти столько же байтов для обработки ввода-вывода, сколько и для решения реальной проблемы ...
источник
CJam (20 байтов)
Демо онлайн . Обратите внимание, что это 0-индексированный. Чтобы сделать его 1-индексированным, замените начальное
1_
наT1
.рассечение
Это использует характеристику из-за Моше Ньюмана, что
Если
x = s/t
тогда мы получимТеперь, если мы предположим, что
s
иt
взаимно просты, тоТак
a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))
работает отлично.источник
Haskell,
78 77 6558 байтБесстыдно воровать оптимизированный подход дает нам:
Спасибо @nimi за игру в несколько байт с помощью функции инфикса!
(По-прежнему) использует индексирование на основе 0.
Старый подход:
Блин формат вывода ... И операторы индексации. РЕДАКТИРОВАТЬ: И приоритет.
Забавный факт: если бы разнородные списки были чем-то, последняя строка могла бы быть:
источник
s!!n
должно быть на один байт короче:f n|x<-s!!n=x:x+x+1:f$n+1
s!!n+1
нет,(s!!n)+1
ноs!!(n+1)
именно поэтому я не могу этого сделать: /s!!n
там!++'/':(show.s$n+1)
в ,r
чтобы сохранить байты.(s#t)0=show...
,(s#t)n=t#(s+t-2*mod s t)$n-1
,r=1#1
. Вы можете даже опуститьr
, то есть последняя строка просто1#1
.Желе , 16 байт
Попробуйте онлайн! или проверьте все контрольные примеры .
Как это работает
источник
05AB1E ,
34332523 байтаобъяснение
Попробуйте онлайн
Сохранено 2 байта благодаря Аднану.
источник
XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý
.ý
могу отформатировать список. Ницца.MATL , 20 байтов
При этом используется характеристика в терминах биномиальных коэффициентов, приведенных на странице OEIS .
Алгоритм теоретически работает для всех чисел, но на практике он ограничен числовой точностью MATL и поэтому не работает для больших записей. Результат является точным для входных данных, по
20
крайней мере, до.Попробуйте онлайн!
объяснение
источник
Python 2,
8581 байтЭто представление 1-проиндексировано.
Используя рекурсивную функцию, 85 байтов:
Если вывод вроде бы
True/2
приемлем, вот один на 81 байт:источник
JavaScript (ES6), 43 байта
1-индексированных; изменить
n=1
на 0-indexed. Связанная страница OEIS имеет полезную повторяемость для каждого термина в терминах двух предыдущих терминов; Я просто переосмыслил это как повторение для каждой фракции с точки зрения предыдущей фракции. К сожалению, у нас нет встроенного TeX, поэтому вам просто нужно вставить его на другой сайт, чтобы узнать, как он форматируется:источник
Python 2, 66 байт
Использует рекурсивную формулу.
источник
C (GCC), 79 байтов
Использует индексирование на основе 0.
Ideone
источник
x?:y
это расширение gcc.На самом деле, 18 байт
Попробуйте онлайн!
Это решение использует формулу Питера и также 0-индексировано. Спасибо Leaky Nun за байт.
Объяснение:
источник
MATL ,
3230 байтЭто использует прямой подход: генерирует достаточно членов последовательности, выбирает два желаемых и форматирует выходные данные.
Попробуйте онлайн!
источник
R, 93 байта
Буквально самая простая реализация. Работаю над игрой в гольф немного.
источник
м4, 131 байт
Определяет такой макрос
r
, которыйr(n)
оценивает в соответствии со спецификацией. Не совсем в гольф, я просто закодировал формулу.источник
Рубин, 49 байтов
Это 0-индексировано и использует формулу Питера Тейлора. Предложения по игре в гольф приветствуются.
источник
> <> , 34 + 2 = 36 байт
Увидев отличный ответ Питера Тейлора, я переписал свой тестовый ответ (который был смущающим 82 байта, используя очень неуклюжую рекурсию).
Ожидается, что вход будет присутствовать в стеке, поэтому +2 байта для
-v
флага. Попробуйте онлайн!источник
Октава, 90 байт
источник
C #,
9190 байтПриводит к
Func<int, string>
. Это рекурсивная реализация.Ungolfed:
Редактировать: -1 байт. Оказывается, C # не нуждается в промежутке между
return
и$
для интерполированных строк.источник
Python 2, 59 байт
Использует формулу Питера и аналогично 0-индексируется.
Попробуйте онлайн
источник
J, 29 байт
использование
Большие значения n требуют суффикса,
x
который обозначает использование расширенных целых чисел.источник
100
считается "большим значением"?Mathematica,
108106101 байтисточник
R , 84 байта
Попробуйте онлайн!
Более старая реализация R не соответствует спецификациям, возвращая с плавающей точкой, а не строку, так что вот что делает.
источник