Вдохновленный предыдущим вопросом .

Самоописывающая последовательность Голомба g (n) - это последовательность, в которой любое натуральное число nповторяется в последовательности g (n) раз.

Первые несколько чисел в последовательности:

n    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
g(n) 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

Вы можете видеть, что g (4) = 3, и что «4» повторяется 3 раза в последовательности.

Учитывая вход n, выход g(n).

Ограничения: n <100000.

Наименьший код выигрывает.

GolfScript (31 символ)

~([1 2.]2{.2$=[1$)]*@\+\)}3$*;=

демонстрация

Желе , неконкурентоспособное

10 байт. Этот ответ не является конкурирующим, поскольку задача предшествует созданию желе.

’ßßạ¹ß‘µṖ¡

При этом используется рекурсивная формула a (1) = 1, a (n + 1) = 1 + a (n + 1 - a (a (n))) со страницы OEIS.

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

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

’ßßạ¹ß‘µṖ¡ Main link. Input: n

’          Decrement; yield n - 1.
 ßß        Recursively call the main link twice, with argument n - 1.
   ạ¹      Take the absolute difference of a(a(n - 1)) and n.
     ß     Recursively call the main link, with argument n - a(a(n - 1)).
      ‘    Increment the result, yielding 1 + a(n - a(a(n - 1))).
       µ   Combine the chain to the left into a single link.
        Ṗ  Pop [1, ..., n]. This yields [] iff n == 1.
         ¡ Execute the chain iff Ṗ returned a non-empty array.

PHP - 63 символа

function g($n){for(;++$i<=$n;){for(;++$j<=$i;){echo $i;}$j=0;}}

Быстро И коротко.

Я, кажется, имел в виду неправильную последовательность. Derp.

Это правильно, быстро и коротко.

function g($n){for(;++$i<$n;){echo round(1.201*pow($i,.618));}}

Точность может пострадать за отметку в 100 000 баллов, но я на самом деле соответствовал этой отметке.

PHP

Эта рекурсивная версия короче (60), но вычислительно неэффективна:

function g($n){return$n==1?1:1+g($n-g(g($n-1)));}echo g($n);

Это намного быстрее, но дольше (78):

$a=[1,2,2];for($i=3;$i<$n;$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Гораздо быстрее, но на 89 символов будет:

$a=[1,2,2];for($i=3;!isset($a[$n-1]);$i++)for($j=0;$j<$a[$i-1];$j++)$a[]=$i;echo$a[$n-1];

Который есть O (n)

Haskell, 30 27 символов

g 1=1
g n=1+(g$n-g(g$n-1))

Оазис , 7 байтов (неконкурирующий)

Код:

n<aae>T

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

Оазис - это язык, разработанный Аднаном, который специализируется на последовательностях.

В настоящее время этот язык может делать рекурсию и закрытую форму.

В Tконце это сокращение для 10, которое указывает, что a(0) = 0и a(1) = 1. Чтобы добавить больше тестовых случаев, просто добавьте в список в конце.

n<aae>T
n<aae>10  expanded

       0  a(0) = 0
      1   a(1) = 1

n         push n (input)
 <        -1
  a       a(above)  [a is the sequence]
   a      a(above)
    e     a(n-above)
     >    +1

Теперь мы по сути рассчитали a(n-a(a(n-1))+1.

Perl, 48 символов

(@a=(@a,($,)x($a[$,++]||$,)))<$_?redo:say$,for<>

Вход на стандартный вывод, вывод на стандартный вывод. Требуется Perl 5.10+ и -M5.010для включения этой sayфункции. Занимает около O ( n ² ) времени из-за неэффективного манипулирования массивом, но все еще достаточно быстро, чтобы легко вычислить до 100 000-го члена.

Юлия - 28

По рекурсивным образом:

a(n)=n==1?1:1+a(n-a(a(n-1)))

Выход:

[a(i) for i=1:20]'
1x20 Array{Int64,2}:
 1  2  2  3  3  4  4  4  5  5  5  6  6  6  6  7  7  7  7  8

Python - 64 символа

n=input()
g=[1,2,2]
for i in range(3,n):g+=[i]*g[i-1]
print g[n]

Javascript, 93 символа

c=[,1],i=c.length;function g(n){for(i;i<n;i++) c[i]=g(i);return c[n]||(c[n]=1+g(n-g(g(n-1))))}

J, 43 знака

f=:3 :'<.@:+&0.5(p^2-p)*y^p-1[p=:(+%)/20$1'

Определяет функцию, используя асимптотическое выражение, указанное на странице википедии.

   f 5
3
   f 20
8
   f 100000
1479

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

Прелюдия , 69 55 54 байта

?1-(v  #1)-
1   0v ^(#    0 (1+0)#)!
    (#)  ^#1-(0)#

Если используется стандартный совместимый интерпретатор, он принимает входные и выходные данные как байтовые значения . Чтобы фактически использовать десятичные числа в STDIN / STDOUT, вам понадобится интерпретатор Python с NUMERIC_OUTPUT = Trueдополнительной опцией NUMERIC_INPUT = True.

объяснение

Скелет программы

?1-(    1 -
1                     )!

Мы читаем ввод Nв первый голос и уменьшаем его, чтобы получить N-1. Мы также инициализируем второй голос 1. Затем мы N-1выполняем цикл один раз, каждая итерация которого получает следующее значение последовательности во втором стеке. В конце мы печатаем Nномер.

Идея программы состоит в том, чтобы поместить каждый элемент последовательности в очередь на третий голос и уменьшить заголовок этой очереди в каждой итерации. Когда голова достигает 0, мы увеличиваем значение последовательности и удаляем это 0.

Теперь проблема в том, что Prelude использует стеки, а не очереди. Поэтому нам нужно немного переместиться вокруг этого стека, чтобы использовать его как очередь.

v  #
0v ^
(#)

Это копирует текущее значение последовательности в первый голос (как временная копия), помещает a 0во второй голос (чтобы отметить конец очереди). И затем выполняет цикл для смещения (и, таким образом, обращения) третьего стека на второй. После цикла мы помещаем копию текущего значения последовательности поверх второго стека (который является хвостом нашей очереди).

 )
(#
 ^#1-

Это выглядит немного уродливо, но по сути это цикл, который сдвигает стек обратно на третий голос. Поскольку )столбец находится в том же столбце, что и инструкции по сдвигу, 0второй голос , который мы добавили ранее, также окажется в третьем голосе, поэтому нам нужно удалить его другим #. Затем уменьшите начало 3-го голоса, то есть главы очереди.

Теперь это немного раздражает - мы хотим запустить некоторый код, когда это значение 0, но единственная управляющая структура Prelude (цикл) реагирует только на ненулевые значения.

 0 (1+0)#
(0)#

Обратите внимание, что верхняя часть второго голоса является правдивой (поскольку последовательность Голомба не содержит никаких 0s). Таким образом, рабочая нагрузка переходит в этот голос (последняя пара скобок). Нам просто нужно предотвратить это, если глава очереди 0еще не существует. Итак, сначала у нас есть «петля» на третьем голосе, которая выдвигает 0на второй голос, если заголовок очереди все еще не равен нулю. Мы также добавили 0третий голос, чтобы сразу выйти из цикла. #На третий голос затем либо удаляет это 0, или удаляет главу очереди , если что уже ноль. Теперь этот второй цикл вводится только в том случае, если заголовок очереди равен нулю (а0на второй голос никогда не давил). В этом случае мы увеличиваем текущее значение последовательности и нажимаем a, 0чтобы выйти из цикла. Наконец, всегда будет 0верхняя часть стека, которую мы должны отбросить.

Я говорил вам, что логическое отрицание раздражает в Prelude ...

Mathematica, 27 байт

f@1=1;f@n_:=1+f[n-f@f[n-1]]

Еще одно рекурсивное решение.

CJam, 14 байтов

CJam намного моложе этой задачи, поэтому этот ответ не имеет права на зеленую галочку. Тем не менее, довольно редко вы можете использовать jэто красиво, поэтому я все равно хотел опубликовать его.

l~2,{_(jj-j)}j

Проверьте это здесь.

объяснение

jв основном "запомнившийся оператор рекурсии". Требуется целое число N, массив и блок F. Массив используется для инициализации запоминания: для элемента iвозвращается индекс F(i). jзатем вычисляет F(N), либо просматривая его, либо выполняя блок (со nстеком), если значение еще не было запомнено. Отличная особенность заключается в том, что внутри блока jпринимает только целое число iи вызывает F(i)рекурсивно. Итак, вот код:

l~             "Read and eval input.";
  2,           "Push a 2-range onto the stack, i.e. [0 1]. The first value is irrelevant
                but the second value is the base case of the recursion.";
    {       }j "Compute F(N).";
     _(        "Duplicate i and decrement to i-1.";
       jj      "Compute F(F(i-1)).";
         -     "Subtract from i.";
          j    "Compute F(n-F(F(i-1))).";
           )   "Increment the result.";

J, 16 байт

    <:{1($1+I.)^:[~]

    (<:{1($1+I.)^:[~]) every 1+i.20  NB. results for inputs 1..20
1 2 2 3 3 4 4 4 5 5 5 6 6 6 6 7 7 7 7 8

Это решение в значительной степени основано на алгоритмическом решении аналогичной проблемы. Вы можете найти некоторое объяснение об этом методе там.

J, 33 байта

В этом подходе я строю последовательность h(k)со значениями первых индексов, iгде g(i)=kтак h = 1 2 4 6 9 12 16.... Мы можем получить h(k)довольно просто из h(1..k-1)выражения, ({:+1+[:+/#<:])где ввод h(1..k-1).

Вычислить вывод из hочень просто.h ([:+/]>:[) input

[:+/]>:1 2(,{:+1+[:+/#<:])@]^:[~]

Brachylog , 13 байт (не конкурирует)

1|-₁↰↰:?-ṅ↰+₁

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

объяснение

1                Input = 1 = Output
 |               Or
  -₁↰            a(Input - 1)
     ↰           a(a(Input - 1))
      :?-ṅ       Input - a(a(Input - 1))
          ↰      a(Input - a(a(Input - 1))
           +₁    1 + a(Input - a(a(Input -1))

Питон - 76 символов

n=20;g=[1,2,2];[[g.append(i)for j in range(g[i-1])]for i in range(3,n)];g[n]

JavaScript - 48 символов

for(g=[,i=j=k=1,2];i<1e5;k=--k?k:g[++j])g[i++]=j

Создает 1-индексированный массив, gсодержащий значения последовательности.

Редактировать - JavaScript - 46 символов

v=[,1];for(x=2;x<1e5;)v[x]=1+v[x-v[v[x++-1]]]

Создает 1-индексированный массив, vсодержащий значения последовательности.

Редактировать 2 - ECMAScript 6 - 27 символов

g=x=>x-1?1+g(x-g(g(x-1))):1

Первые два довольно быстрые, третий очень медленный

Haskell, 63 байта

f n|n<3=n|n<4=2|1>0=foldr1(++)[replicate(f m)m|m<-[1..]]!!(n-1)

Это наивный подход, я не знал об очень коротком повторении, когда писал это, но я думал, что выложу его в любом случае, даже если это дольше, чем все другие реализации Haskell, как, например,

Вычислить n-й член последовательности самоописания Голомба

и

/codegolf//a/23979/24877