Определение

а (1) = 1
а (2) = 1
a (n) = a (na (n-1)) + a (na (n-2)) для n> 2, где n - целое число

задача

Учитывая положительное целое число n, генерировать a(n).

Testcases

Ссылка

Обязательный OEIS A005185

code-golf sequence arithmetic Дрянная Монахиня
источник

Относящиеся .

Дрянная Монахиня

1

Можем ли мы вернуть True в языках, где его можно использовать как 1 ?

Деннис

1

@Dennis Если на этом языке true равно 1, тогда да.

Дрянная Монахиня

4

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

Мартин Эндер

1

Завершение списка связанных с GEB задач последовательности.

Мартин Эндер

9

Сетчатка , 84 83 79 74 байта

Число байтов предполагает кодировку ISO 8859-1.

.+
$*;1¶1¶
+`;(?=(1)+¶(1)+)(?=(?<-1>(1+)¶)+)(?=(?<-2>(1+)¶)+)
$3$4¶
G3=`
1

Попробуйте онлайн! (Первая строка включает набор тестов, разделенных переводом строки.)

Я буду играть в гольф еще немного позже.

Мартин Эндер
источник

9

Haskell, 35 33 байта

a n|n<3=1|b<-a.(-)n=b(b 1)+b(b 2)

Определяет функцию a.

Андерс Касеорг
источник

2

Хороший трюк с привязкой! Разве что-то не (b.b)1+(b.b)2будет короче суммы?

xnor

Почему да, спасибо @xnor.

Андерс Касеорг

8

Юлия, 29 байт

!n=n<3||!(n-!~-n)+!(n-!~-~-n)

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

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

Мы переопределяем унарный оператор !для наших целей.

Если n равно 1 или 2 , n<3возвращает true, и это наше возвращаемое значение.

Если n больше 2 , n<3возвращает false и || ветвь исполняется. Это прямая реализация определения, где ~-nприводит к n - 1 и ~-~-nприводит к n - 2 .

Деннис
источник

7

Sesos, 54 байта

0000000: eefb5b 04f83a a75dc2 36f8d7 cf6dd0 af7b3b 3ef8d7  ..[..:.].6...m..{;>..
0000015: cfed12 f661f0 ae9d83 ee63e6 065df7 ce6183 af7383  ....a.....c..]..a..s.
000002a: 76ef3c 3f6383 7eff9c b9e37f                       v.<?c.~.....

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

разобранный

Или в обозначении Brainfuck:

+>+>>>>>>,-[[->+<]>-<<++[<<<<[->>>+<<<]>>>>[-<<<+<+>>>>]<<<[->>>+<<<]>>>>++[<<<<<[<
[->>+<<]>[-<+>]<-]>>[-<+<+>>]>[<<[->+<]>>[-<<+>>]>]>>>-]<<[-<<<+>>>]>-]>>]<<<<<<<.

Андерс Касеорг
источник

6

C, 43 42 байта

Сохранено 1 байт благодаря @Dennis

Каждый ответ один и тот же, я должен сделать что-то другое!

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

a(n){return n<3?:a(n-a(n-2))+a(n---a(n));}

Пояснение: это в основном, a(n-a(n-2))+a(n-a(n-1))но с нестабильным ^{неопределенным} поведением (работает на моем телефоне (gcc) и ideone).

betseg
источник

4

1. Вы должны также упомянуть компилятор; ваш "swag" - неопределенное поведение. 2. С GCC вам не нужно 1между ?и :.

Деннис

@Dennis Интересно, что та же самая формулировка работает в моем итеративном ответе PowerShell ...$b+=$b[$_-$b[$_-2]]+$b[$_---$b[$_]]

AdmBorkBork

@TimmyD Некоторые компиляторы могут компилировать a (n) перед n--, и для этого нет стандартного (или определенного) поведения. Таким образом, неопределенное поведение.

Betseg

@betseg Да, я согласен. Просто отметив, что он не обязательно уникален для C.

AdmBorkBork

@TimmyD О, я неправильно понял это. Я просто хотел изменить функцию, которую используют все, так что моя была бы другой и неаккуратной: D

betseg

5

Mathematica, 36 байт

Количество байт принимает ISO 8859-1 кодирование и Mathematica в $CharacterEncodingнабор для WindowsANSI(по умолчанию на Windows; другие параметры могут работать хорошо, но некоторые , как , UTF-8безусловно , не делают).

±1=±2=1
±n_:=±(n-±(n-1))+±(n-±(n-2))

Определяет ± как унарный оператор.

Я попытался избавиться от дублирования, но получилось с тем же количеством байтов:

±1=±2=1
±n_:=Tr[±(n-±(n-#))&/@{1,2}]

Мартин Эндер
источник

Я могу дать вам +200 наград, если вы сделаете это в Retina

Leaky Nun

@ LeakyNun хорошо? :)

Мартин Эндер

Два дня спустя.

Дрянная монахиня

@LeakyNun Скоро у вас не останется ни одного представителя, если вы так легко начисляете награды.

mbomb007

Давайте продолжим эту дискуссию в чате .

LegionMammal978

4

Желе , 15 14 байт

2Rạ⁸ß€$⁺Sµ1>?2

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

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

2Rạ⁸ß€$⁺Sµ1>?2  Main link. Argument: n (integer)

2R              Yield [1, 2].
      $         Combine the previous three links into a monadic chain.
   ⁸                Yield n.
  ạ                 Take the absolute difference of the return value and n.
    ß€              Recursively call the main link on each result.
       ⁺            Duplicate the chain.
                    The first copy maps [1, 2] to [a(n - 1), a(n - 2)].
                    The second copy maps [a(n - 1), a(n - 2)] to
                    [a(n - a(n - 1)), a(n - a(n - 2))].
        S           Take the sum.
         µ          Combine all links to the left into a chain.
            ?       If...
           > 2          n is greater than 2, call the chain.
          1         Else, return 1.

Деннис
источник

Я могу дать вам +400 щедрости, если вы сделаете это в Сесосе.

Утренняя монахиня

@LeakyNun Кажется, есть ответ Sesos. Он вышел через день после вашего комментария.

Yytsi

4

Желе , 14 12 11 байт

ịḣ2S;
1Ç⁸¡2ị

Это итеративный подход.

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

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

1Ç¡2ị   Main link. Argument: n

1       Set the return value to 1.
 Ç¡     Call the helper link n times, updating the return value after each call.
   2ị   Extract the second element of the resulting array.


ịḣ2S;   Helper link. Argument: A (array)

ị       At-index; retrieve the elements of A at the values of A.
 ḣ2     Head 2; extract the first two results.
    S   Take the sum of the result.
     ;  Prepend the sum to A.

Деннис
источник

3

Python, 45 40 байт

a=lambda n:n<3or a(n-a(n-1))+a(n-a(n-2))

Простое наивное толкование задачи.

Сохранено 5 байтов благодаря @LeakyNun!

медь
источник

3

Haskell, 39 37 байт

h n|n<3=1|n>2=h(n-h(n-1))+h(n-h(n-2))

точно так же, как описано в вызове, с использованием охранников

KarlKastor
источник

Извините, я не видел ваше решение до публикации моего (идентичного) решения на Haskell. Однако не считается ли число байтов 38, поскольку новая строка должна быть принята во внимание?

Лайкони

И охранник должен быть n<3для того, h 2 чтобы быть 1.

Лайкони

@Laikoni Это 37 в соответствии с функцией Pythons len с многострочной ("" ") строкой, если только вы не считаете символ новой строки двумя байтами. Да, я заметил другую вещь, которая исправлена сейчас

KarlKastor

TIL notepad ++ считает перевод строки двумя символами.

Лайкони

@Laikoni избавились от новой строки , это неоспоримо 37 байт в настоящее время.

КарлКастор

3

R, 50 байтов

a=function(n)ifelse(n<3,1,a(n-a(n-1))+a(n-a(n-2)))

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

> a(1)
  1
> a(20)
  12

DSkoog
источник

3

CJam, 19 18 байтов

XXri{_($2$$+}*]-3=

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

Использует итеративный подход.

Мартин Эндер
источник

3

C #, 51 44 байта

int a(int n)=>n<3?1:a(n-a(n-1))+a(n-a(n-2));

~~Интересно, можно ли это сократить, сделав это анонимным~~ благодаря pinkfloydx33!

downrep_nation
источник

1

c # 6 выражение функции int a(int n)=>n<3?1:a(n-a(n-a))+a(n-a(n-2));

тела

Кажется, я печатал, печатая это на моем телефоне. Самое внутреннее -aв первом наборе паренов должно быть-1

pinkfloydx33

Я тоже этого не заметил, плохо исправлю rq

downrep_nation

3

JavaScript (ES6), 45 байт, 34 байта

Рекурсивное решение в ES6. Любые советы по гольфу очень ценятся.

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

Спасибо / u / ismillo за сокращение еще больше.

BugHunterUK
источник

2

Гольфскрипт, 29 байт

~[1 1]{..0=(=\..1=(=@+\+}@*2=

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

Дрянная Монахиня
источник

2

05AB1E, 29 байт

Итеративное решение.

XˆXˆÍL>v¯¤ys-è¯y¯yÍè-è+ˆ}¯¹<è

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

Emigna
источник

2

APL, 20 байт

{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}

Объяснение:

{⍵≤2:1⋄+/∇¨⍵-∇¨⍵-⍳2}
 ⍵≤2:1               If argument is 2 or less, return 1
      ⋄              Otherwise:
               ⍵-⍳2  Subtract [1, 2] from the argument
             ∇¨      Recursive call on both
           ⍵-        Subtract both results from the argument     
         ∇¨          Recursive call on both again
       +/            Sum

Мэринус
источник

2

VBA Excel 87 байт

Не рекурсивный, так как я хочу, чтобы это работало для n = 100000, скажем:

Function A(N):ReDim B(N):For i=3 To N:B(i)=B(i-B(i-1)-1)+B(i-B(i-2)-1)+1:Next:A=B(N)+1

... и нажмите return(байт # 87) в конце строки, чтобы получить End Functionутверждение "бесплатно". Обратите внимание, что значения B смещены на -1, чтобы избежать инициализации для n = 1 и 2.

Вызвать в таблице как обычно, например, =A(100000)чтобы получить48157

Рекурсивная версия, 61 байт ,

Function Y(N):If N<3 Then Y=1 Else Y=Y(N-Y(N-1))+Y(N-Y(N-2))

начинает становиться неоправданно медленным для n> 30, и нельзя сказать, что он работает вообще для n> 40.

Joffan
источник

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

mbomb007

1

@ mbomb007 Так как я далеко не выиграл в гольф, я сам сделаю выбор, что составляет рабочую программу. Насколько мне известно, неспособность обрабатывать даже однобайтовые целые числа недостаточно хороша, когда есть решение, которое может сделать это легко.

Джоффан

2

Рубин, 36 байт

Прямая реализация. Любые предложения по игре в гольф приветствуются.

a=->n{n<3?1:a[n-a[n-1]]+a[n-a[n-2]]}

Sherlock9
источник

Афаик, ты можешь избавиться от а =. Если вы разместите его здесь, достаточно, чтобы ваш код начинался с ->. Тогда это считается анонимной функцией.

Seims

@Seims К сожалению, так как функция вызывает себя с a[n-1]и тому подобное, функция должна быть названа.

Sherlock9

2

Java 7, 68 61 51 байт

17 спасен благодаря Лики Монахиня.

int a(int n){return n<3?1:a(n-a(n-1))+a(n-a(n-2));}

Джастин
источник

Добро пожаловать в PPCG!

AdmBorkBork

Добро пожаловать в PPCG! Вам могут понравиться Советы по игре в гольф на Java . Альтернативная форма была бы:, int a(int n){return n<3?1:a(n-a(n-2))+a(n---a(n));}но, к сожалению, она использует то же количество байтов, что и у ответа, который у вас уже есть. Также я хотел бы указать, что ваш ответ на Java 7, так как ответ на Java 8 будет короче: n->return n<3?1:a(n-a(n-1))+a(n-a(n-2))( 39 байт ) ,

Кевин Круйссен

Спасибо за приветствия, ребята, и спасибо за совет по Java8 - я не знал, что лямбды разрешены таким образом - хотя они разрешены так в Python, поэтому, я думаю, я просто никогда не думал об этом. Нужна ли лямбда точка с запятой?

Джастин

@JustinTervay Я не очень часто использую Java 8, но из того, что я слышал, точка с запятой не учитывается в однострочных выражениях, согласно комментарию точка запятой @DavidConrad и @ CAD97 в одном из моих собственных ответов на Java ,

Кевин Круйссен

2

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

Не конкурирует , так как язык задним числом. Спасибо Кенни Лау за сохранение 4 байта. Код:

ece+V

Расширенная форма ( Vсокращенно 11):

a(n) = ece+
a(0) = 1
a(1) = 1

Код:

e        # Stack is empty, so a(n - 1) is used, and it calculates a(n - a(n - 1))
 c       # Calculate a(n - 2)
  e      # Calculate a(n - a(n - 2))
   +     # Add up

Попробуйте онлайн! , Вычисляет n = 1000 за 0,1 секунды.

Аднан
источник

1

PowerShell v2 +, 85 79 69 байт

param($n)$b=1,1;2..$n|%{$b+=$b[$_-$b[$_-1]]+$b[$_-$b[$_-2]]};$b[$n-1]

Принимает ввод $n, устанавливает $bв массив @(1, 1), затем входит в цикл из 2 .. $n. Каждую итерацию мы привязываем $bк последнему вычислению в последовательности с простым +=и определением последовательности. Затем мы выводим соответствующее число из$b (с помощью -1массива в PowerShell с нулевым индексированием). Это работает, если $nесть 1или 2потому что оба эти значения предварительно заполняются в более низкие индексы $bс самого начала, поэтому, даже если цикл привязывается к мусору, он все равно игнорируется.

Рекурсивное решение 78 76 байт

$a={param($k)if($k-lt3){1}else{(&$a($k-(&$a($k-1))))+(&$a($k-(&$a($k-2))))}}

В первый раз я использовал эквивалент лямбды в качестве ответа, так как обычно итеративное решение короче (как вы можете видеть из всех вложенных паренов). Но в этом случае вложенные парены почти дублируются в итеративном решении вызовами вложенного массива, поэтому рекурсивное решение короче. Нет, итеративное решение действительно короче (см. Выше).

Назовите это через оператор выполнения, как &$a 20. Просто прямой рекурсивный вызов.

AdmBorkBork
источник

1

JavaScript (ES6), 66 байт

n=>[...Array(n+1)].reduce((p,_,i,a)=>a[i]=i<3||a[i-p]+a[i-a[i-2]])

Нерекурсивная версия для скорости; рекурсивная версия, вероятно, короче, но я оставлю это кому-то другому, чтобы написать. Мне всегда нравится, когда я использую reduce. Примечание: 1 байт сохраняется путем возврата true(который 1используется при использовании в целочисленном контексте) для of a(1)и a(2).

Нил
источник

1

Pyth, 16 байт

L|<b3smy-bytdtBb

L                  def y(b):
 |<b3                b < 3 or …
      m      tBb       map for d in [b - 1, b]:
       y-bytd            y(b - y(d - 1))
     s                 sum

Определяет функцию y.

Попробуйте онлайн (добавлено, yMS20чтобы напечатать первые 20 значений)

Андерс Касеорг
источник

1

Далее 76 байт

Я наконец получил это работает!

: Q recursive dup dup 3 < if - 1+ else 2dup 2 - Q - Q -rot 1- Q - Q + then ;

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

Объяснение:

: Q recursive                           \ Define a recursive function Q
    dup dup 3 <                         \ I moved a dup here to golf 2 bytes
    if                                  \ If n < 3, return 1
        - 1                             \ Golf: n-n is zero, add one. Same as 2drop 1+
    else
        2dup 2 - Q - Q                  \ Copy n until 4 on stack, find Q(n-Q(n-2))
        -rot                            \ Move the result below 2 copies of n
        1- Q - Q +                      \ Find Q(n-Q(n-2)), then add to previous ^
    then ;

Попробуйте онлайн (слегка не в гольф сверху)

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

mbomb007
источник

1

Клен, 43 41 байт

a:=n->`if`(n>2,a(n-a(n-1))+a(n-a(n-2)),1)

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

> a(1);
  1
> a(20);
  12

Эта проблема, безусловно, хороший кандидат на запоминание. Используя кеш опций , время выполнения значительно сокращается:

aC := proc(n) 
      option cache; 
      ifelse( n > 2, aC( n - aC(n-1) ) + aC( n - aC(n-2) ), 1 ); 
end proc:

Это можно увидеть с помощью:

CodeTools:-Usage( aC(50) );

DSkoog
источник

0

J, 29 28 байт

1:`(+&$:/@:-$:@-&1 2)@.(2&<)

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

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

Дополнительные команды используются для форматирования нескольких входов / выходов.

   f =: 1:`(+&$:/@:-$:@-&1 2)@.(2&<)
   (,:f"0) >: i. 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 1 2 3 3 4 5 5 6  6  6  8  8  8 10  9 10 11 11 12

объяснение

1:`(+&$:/@:-$:@-&1 2)@.(2&<)  Input: n
                        2&<   If n < 2
1:                              Return 1
                              Else
               -&1 2            Subtract [1, 2] from n to get [n-1, n-2]
            $:@                 Call recursively on n-1 and n-2
           -                    Subtract each of the results from n
        /@:                     Reduce using
      $:                          A recursive call on each
    +&                            Then summation
                                Return that value as the result

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

0

постоянный ток, 62 байта

?si2sa1dd2:a:a[la1+dsadd1-;a-;alad2-;a-;a+r:ali;a0=A]dsAxli;af

Это решение использует массивы и рекурсию.

?si          # Take input from stdin and store it in register `i'
2sa          # Initialise register `a' with 2, since we'll be putting in the first
             #   two values in the sequence
1dd2         # Stack contents, top-down: 2 1 1 1
:a           # Pop index, then pop value: Store 1 in a[2]
:a           # Ditto:                     Store 1 in a[1]
[            # Open macro definition
 la 1+ dsa   # Simple counter mechanism: Increment a and keep a copy on stack

# The STACK-TRACKER(tm): Top of stack will be at top of each column, under the
#   dashed line. Read commands from left to right, wrapping around to next line.
#   This will be iteration number n.
  dd   1-    ;a       -          ;a            la            d          
#-----------------------------------------------------------------------
# n    n-1   a[n-1]   n-a[n-1]   a[n-a[n-1]]   n             n          
# n    n     n        n          n             a[n-a[n-1]]   n          
# n    n     n                                 n             a[n-a[n-1]]
#                                                            n          
#                                                                       

  2-            ;a            -             ;a            +      r    :a
#-----------------------------------------------------------------------
# n-2           a[n-2]        n-a[n-2]      a[n-a[n-2]]   a[n]   n      
# n             n             a[n-a[n-1]]   a[n-a[n-1]]   n      a[n]   
# a[n-a[n-1]]   a[n-a[n-1]]   n             n                           
# n             n                                                       

 li;a        # Load index of target element, and fetch that element's current value
             #    Uninitialised values are zero
 0=A         # If a[i]==0, execute A to compute next term
]dsAx        # Close macro definition, store on `A' and execute
li;a         # When we've got enough terms, load target index and push value
f            # Dump stack (a[i]) to stdout

Джо
источник

В заключение, если кто-то создает IDE для dc, дайте мне знать!

Джо

0

Эрланг, 46 байт

f(N)when N<3->1;f(N)->f(N-f(N-1))+f(N-f(N-2)).

CPU1
источник

0

Луа, 59 байт

function a(n)return n<3 and 1 or a(n-a(n-1))+a(n-a(n-2))end

brianush1
источник

Q-последовательность Хофштадтера

Определение

задача

Testcases

Ссылка

Ответы:

Сетчатка , 84 83 79 74 байта

Haskell, 35 33 байта

Юлия, 29 байт

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

Sesos, 54 байта

разобранный

C, 43 42 байта

Mathematica, 36 байт

Желе , 15 14 байт

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

Желе , 14 12 11 байт

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

Python, 45 40 байт

Haskell, 39 37 байт

R, 50 байтов

CJam, 19 18 байтов

C #, 51 44 байта

JavaScript (ES6), 45 байт, 34 байта

Гольфскрипт, 29 байт

05AB1E, 29 байт

APL, 20 байт

VBA Excel 87 байт

Рубин, 36 байт

Java 7, 68 61 51 байт

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

PowerShell v2 +, 85 79 69 байт

Рекурсивное решение 78 76 байт

JavaScript (ES6), 66 байт

Pyth, 16 байт

Далее 76 байт

Клен, 43 41 байт

J, 29 28 байт

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

объяснение

постоянный ток, 62 байта

Эрланг, 46 байт

Луа, 59 байт