Выведите n-е рациональное число в соответствии с последовательностью Штерна-Броко

30

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

  1. Инициализируйте последовательность с помощью s(1) = s(2) = 1
  2. Установить счетчик n = 1
  3. Добавить s(n) + s(n+1)к последовательности
  4. Добавить s(n+1)к последовательности
  5. Инкремент n, вернитесь к шагу 3

Это эквивалентно:

s (n) = \ begin {case} 1 & \ textrm {if} n = 1 \ s (\ frac n 2) & \ textrm {if} n \ textrm {четный} \ s (\ frac {n-1 } 2) + s (\ frac {n + 1} 2) & \ textrm {в противном случае} \ end {case}

Среди других свойств последовательность Штерна-Броко может быть использована для генерации любого возможного положительного рационального числа. Каждое рациональное число будет сгенерировано ровно один раз, и оно всегда будет отображаться в самых простых терминах; например, 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, обсуждающее последовательность: бесконечные дроби

Sok
источник
Может ли вывод использовать Trues вместо 1s?
Loovjo
1
@ Loovjo Нет, True/2недопустимая дробь (насколько я понимаю). Кроме того, Trueне всегда 1- некоторые языки используют -1вместо этого, чтобы избежать потенциальных ошибок при применении побитовых операторов. [нужная цитата]
Сок
2
@ Сок цитирование
mbomb007
1
@ Сок, но в Python, Trueэквивалентен 1и True/2будет 1/2.
Утренняя монахиня

Ответы:

3

Желе , 14 байт

3ẋḶŒpḄċ
’Ç”/⁸Ç

Попробуйте онлайн!

Ох, похоже, я могу побить принятый ответ @Dennis, и на этом же языке. Это работает с использованием формулы из OEIS: количество способов выразить (число минус 1) в гипербинарном (то есть двоичном с 0, 1, 2 в качестве цифр). В отличие от большинства программ Jelly (которые работают либо как полная программа, либо как функция), эта программа работает только как полная программа (поскольку она отправляет часть вывода в стандартный вывод и возвращает остальную часть; при использовании в качестве полной программы возвращаемое значение отправляется в stdout неявно, поэтому все выходные данные находятся в одном месте, но это не сработает для отправки функции).

Эта версия программы очень неэффективна. Вы можете создать гораздо более быструю программу, которая работает для всех входных данных до 2ⁿ, поместив n сразу после первой строки; программа имеет производительность O ( n × 3ⁿ), поэтому здесь очень важно сохранить n маленьким. Программа в том виде, в котором она написана, устанавливает n равным входному значению, которое явно достаточно большое, но также явно слишком большое почти во всех случаях (но, эй, оно сохраняет байты).

объяснение

Как обычно в моих объяснениях Jelly, текст в фигурных скобках (например {the input}) показывает что-то, что автоматически заполняется Jelly из-за отсутствия операндов в исходной программе.

Вспомогательная функция (вычисляет n- й знаменатель, т.е. n + 1-й числитель):

3ẋḶŒpḄċ
3ẋ       3, repeated a number of times equal to {the argument}
  Ḷ      Map 3 to [0, 1, 2]
   Œp    Take the cartesian product of that list
     Ḅ   Convert binary (or in this case hyperbinary) to a number
      ċ  Count number of occurrences of {the argument} in the resulting list

Первые пять байтов в основном просто генерируют все возможные гипербинарные числа вплоть до заданной длины, например, при вводе 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 и, таким образом, работает и для гипербинарных данных. Затем мы подсчитываем, сколько раз вход появляется в результирующем списке, чтобы получить соответствующую запись в последовательности. (К счастью, числитель и знаменатель следуют в той же последовательности).

Основная программа (запрашивает числитель и знаменатель и форматирует вывод):

’Ç”/⁸Ç
’Ç      Helper function (Ç), run on {the input} minus 1 (‘)
  ”/    {Output that to stdout}; start again with the constant '/'
    ⁸Ç  {Output that to stdout}; then run the helper function (Ç) on the input (⁸)

Почему-то я продолжаю писать программы, которые занимают почти столько же байтов для обработки ввода-вывода, сколько и для решения реальной проблемы ...


источник
Боже мой, вы не шутили, что это неэффективно - на TIO 12 требуется 20 секунд, а 13 раз полностью! Принято, хотя я не могу проверить все контрольные примеры.
Сок
11

CJam (20 байтов)

1_{_@_2$%2*-+}ri*'/\

Демо онлайн . Обратите внимание, что это 0-индексированный. Чтобы сделать его 1-индексированным, замените начальное 1_на T1.

рассечение

Это использует характеристику из-за Моше Ньюмана, что

фракция a(n+1)/a(n+2)может быть получена из предыдущей фракции a(n)/a(n+1) = xпути1/(2*floor(x) + 1 - x)

Если x = s/tтогда мы получим

  1 / (2 * floor(s/t) + 1 - s/t)
= t / (2 * t * floor(s/t) + t - s)
= t / (2 * (s - s%t) + t - s)
= t / (s + t - 2 * (s % t))

Теперь, если мы предположим, что sи tвзаимно просты, то

  gcd(t, s + t - 2 * (s % t))
= gcd(t, s - 2 * (s % t))
= gcd(t, -(s % t))
= 1

Так a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))работает отлично.

1_           e# s=1, t=1
{            e# Loop...
  _@_2$%2*-+ e#   s, t = t, s + t - 2 * (s % t)
}
ri*          e# ...n times
'/\          e# Separate s and t with a /
Питер Тейлор
источник
Любите методологию здесь, отличный ответ!
Сок
Если вы прокрутите дальше вниз запись OEIS, вы обнаружите, что Mike Stay уже отправил эту формулу.
Нил
11

Haskell, 78 77 65 58 байт

Бесстыдно воровать оптимизированный подход дает нам:

(s#t)0=show s++'/':show t
(s#t)n=t#(s+t-2*mod s t)$n-1
1#1

Спасибо @nimi за игру в несколько байт с помощью функции инфикса!

(По-прежнему) использует индексирование на основе 0.


Старый подход:

s=(!!)(1:1:f 0)
f n=s n+s(n+1):s(n+1):(f$n+1)
r n=show(s n)++'/':(show.s$n+1)

Блин формат вывода ... И операторы индексации. РЕДАКТИРОВАТЬ: И приоритет.

Забавный факт: если бы разнородные списки были чем-то, последняя строка могла бы быть:

r n=show>>=[s!!n,'/',s!!(n+1)]
ThreeFx
источник
Использование охранника для привязки s!!nдолжно быть на один байт короче:f n|x<-s!!n=x:x+x+1:f$n+1
Laikoni
@Laikoni s!!n+1нет, (s!!n)+1но s!!(n+1)именно поэтому я не могу этого сделать: /
ThreeFx
Действительно, это должно было быть очевидно. Это просто ... так много s!!nтам!
Лайкони
1
Вы можете использовать ++'/':(show.s$n+1)в , rчтобы сохранить байты.
Ними
1
Переключение на инфиксный: (s#t)0=show..., (s#t)n=t#(s+t-2*mod s t)$n-1, r=1#1. Вы можете даже опустить r, то есть последняя строка просто 1#1.
Ними
6

Желе , 16 байт

L‘Hị⁸Sṭ
1Ç¡ṫ-j”/

Попробуйте онлайн! или проверьте все контрольные примеры .

Как это работает

1Ç¡ṫ-j”/  Main link. Argument: n

1         Set the return value to 1.
 Ç¡       Apply the helper link n times.
   ṫ-     Tail -1; extract the last two items.
     j”/  Join, separating by a slash.


L‘Hị⁸Sṭ   Helper link. Argument: A (array)

L         Get the length of A.
 ‘        Add 1 to compute the next index.
  H       Halve.
   ị⁸     Retrieve the item(s) of A at those indices.
          If the index in non-integer, ị floors and ceils the index, then retrieves
          the items at both indices.
    S     Compute the sum of the retrieved item(s).
     ṭ    Tack; append the result to A.
Деннис
источник
5

05AB1E , 34 33 25 23 байта

XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý

объяснение

XX‚                        # push [1,1]
   ¹G           }          # input-1 times do
     Â                     # bifurcate
      2£                   # take first 2 elements of reversed list
        DO¸                # duplicate and sum 1st copy, s(n)+s(n+1)
           s¦              # cut away the first element of 2nd copy, s(n)
             ìì            # prepend both to list
               ¨           # remove last item in list
                 R2£       # reverse and take the first 2 elements
                    '/ý    # format output
                           # implicitly print

Попробуйте онлайн

Сохранено 2 байта благодаря Аднану.

Emigna
источник
Значит ли это работать ?: XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý.
Аднан
@ Adnan Действительно. Я забыл, что ýмогу отформатировать список. Ницца.
Эминья
4

MATL , 20 байтов

FT+"@:qtPXnosV47]xhh

При этом используется характеристика в терминах биномиальных коэффициентов, приведенных на странице OEIS .

Алгоритм теоретически работает для всех чисел, но на практике он ограничен числовой точностью MATL и поэтому не работает для больших записей. Результат является точным для входных данных, по 20крайней мере, до.

Попробуйте онлайн!

объяснение

FT+      % Implicitly take input n. Add [0 1] element-wise. Gives [n n+1]
"        % For each k in [n n+1]
  @:q    %   Push range [0 1 ... k-1]
  tP     %   Duplicate and flip: push [k-1 ... 1 0]
  Xn     %   Binomial coefficient, element-wise. Gives an array
  os     %   Number of odd entries in that array
  V      %   Convert from number to string
  47     %   Push 47, which is ASCII for '\'
]        % End for each
x        % Remove second 47
hh       % Concatenate horizontally twice. Automatically transforms 47 into '\'
         % Implicitly display
Луис Мендо
источник
4

Python 2, 85 81 байт

x,s=input(),[1,1]
for i in range(x):s+=s[i]+s[i+1],s[i+1]
print`s[x-1]`+"/"+`s[x]`

Это представление 1-проиндексировано.

Используя рекурсивную функцию, 85 байтов:

s=lambda x:int(x<1)or x%2 and s(x/2)or s(-~x/2)+s(~-x/2)
lambda x:`s(x)`+"/"+`s(x+1)`

Если вывод вроде бы True/2приемлем, вот один на 81 байт:

s=lambda x:x<1 or x%2 and s(x/2)or s(-~x/2)+s(~-x/2)
lambda x:`s(x)`+"/"+`s(x+1)`
Loovjo
источник
3

JavaScript (ES6), 43 байта

f=(i,n=0,d=1)=>i?f(i-1,d,n+d-n%d*2):n+'/'+d

1-индексированных; изменить n=1на 0-indexed. Связанная страница OEIS имеет полезную повторяемость для каждого термина в терминах двух предыдущих терминов; Я просто переосмыслил это как повторение для каждой фракции с точки зрения предыдущей фракции. К сожалению, у нас нет встроенного TeX, поэтому вам просто нужно вставить его на другой сайт, чтобы узнать, как он форматируется:

aббa+б-2(aмодификацияб)
Нил
источник
3

Python 2, 66 байт

f=lambda n:1/n or f(n/2)+n%2*f(-~n/2)
lambda n:`f(n)`+'/'+`f(n+1)`

Использует рекурсивную формулу.

XNOR
источник
3

C (GCC), 79 байтов

Использует индексирование на основе 0.

s(n){return!n?:n%2?s(n/2):s(-~n/2)+s(~-n/2);}r(n){printf("%d/%d",s(n),s(n+1));}

Ideone

betseg
источник
1
x?:yэто расширение gcc.
Ричи
3

На самом деле, 18 байт

11,`│;a%τ@-+`nk'/j

Попробуйте онлайн!

Это решение использует формулу Питера и также 0-индексировано. Спасибо Leaky Nun за байт.

Объяснение:

11,`│;a%τ@-+`nk'/j
11                  push 1, 1
  ,`│;a%τ@-+`n      do the following n times (where n is the input):
                      stack: [t s]
    │                 duplicate the entire stack ([t s t s])
     ;                dupe t ([t t s t s])
      a               invert the stack ([s t s t t])
       %              s % t ([s%t s t t])
        τ             multiply by 2 ([2*(s%t) s t t])
         @-           subtract from s ([s-2*(s%t) s t])
           +          add to t ([t+s-2*(s%t) t])
                      in effect, this is s,t = t,s+t-2*(s%t)
              k'/j  push as a list, join with "/"
Mego
источник
@LeakyNun Я задержусь на этом улучшении, пока не будет разъяснений от ОП.
Мего
2

MATL , 32 30 байт

1i:"tt@TF-)sw@)v]tGq)V47bG)Vhh

Это использует прямой подход: генерирует достаточно членов последовательности, выбирает два желаемых и форматирует выходные данные.

Попробуйте онлайн!

Луис Мендо
источник
2

R, 93 байта

f=function(n)ifelse(n<3,1,ifelse(n%%2,f(n/2-1/2)+f(n/2+1/2),f(n/2)))
g=function(n)f(n)/f(n+1)

Буквально самая простая реализация. Работаю над игрой в гольф немного.

user5957401
источник
2

м4, 131 байт

define(s,`ifelse($1,1,1,eval($1%2),0,`s(eval($1/2))',`eval(s(eval(($1-1)/2))+s(eval(($1+1)/2)))')')define(r,`s($1)/s(eval($1+1))')

Определяет такой макрос r, который r(n)оценивает в соответствии со спецификацией. Не совсем в гольф, я просто закодировал формулу.

Программист
источник
2

Рубин, 49 байтов

Это 0-индексировано и использует формулу Питера Тейлора. Предложения по игре в гольф приветствуются.

->n{s=t=1;n.times{s,t=t,s+t-2*(s%t)};"#{s}/#{t}"}
Sherlock9
источник
1

> <> , 34 + 2 = 36 байт

Увидев отличный ответ Питера Тейлора, я переписал свой тестовый ответ (который был смущающим 82 байта, используя очень неуклюжую рекурсию).

&01\$n"/"on;
&?!\:@}:{:@+@%2*-&1-:

Ожидается, что вход будет присутствовать в стеке, поэтому +2 байта для -v флага. Попробуйте онлайн!

Sok
источник
1

Октава, 90 байт

function f(i)S=[1 1];for(j=1:i/2)S=[S S(j)+S(j+1) (j+1)];end;printf("%d/%d",S(i),S(i+1));end
dcsohl
источник
1

C #, 91 90 байт

n=>{Func<int,int>s=_=>_;s=m=>1==m?m:s(m/2)+(0==m%2?0:s(m/2+1));return$"{s(n)}/{s(n+1)}";};

Приводит к Func<int, string> . Это рекурсивная реализация.

Ungolfed:

n => 
{
    Func<int,int> s = _ => _; // s needs to be set to use recursively. _=>_ is the same byte count as null and looks cooler.
    s = m =>
        1 == m ? m               // s(1) = 1
        : s(m/2) + (0 == m%2 ? 0 // s(m) = s(m/2) for even
        : s(m/2+1));             // s(m) = s(m/2) + s(m/2+1) for odd
    return $"{s(n)}/{s(n+1)}";
};

Редактировать: -1 байт. Оказывается, C # не нуждается в промежутке между returnи $для интерполированных строк.

молоко
источник
1

J, 29 байт

([,'/',])&":&([:+/2|]!&i.-)>:

использование

Большие значения n требуют суффикса, xкоторый обозначает использование расширенных целых чисел.

   f =: ([,'/',])&":&([:+/2|]!&i.-)>:
   f 1
1/1
   f 10
3/5
   f 50
7/12
   f 100x
7/19
   f 1000x
11/39
миль
источник
100считается "большим значением"?
dcsohl
1
@dcsohl В этом методе вычисляются биномиальные коэффициенты, и для n = 100 самый большой из них вычисляется как C (72, 28) = 75553695443676829680> 2 ^ 64 и потребует расширенных целых чисел, чтобы избежать значений с плавающей запятой.
миль
1

Mathematica, 108 106 101 байт

(s={1,1};n=1;a=AppendTo;t=ToString;Do[a[s,s[[n]]+s[[++n]]];a[s,s[[n]]],#];t@s[[n-1]]<>"/"<>t@s[[n]])&
numbermaniac
источник