Мы все знакомы с последовательностью Фибоначчи :

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

Однако вместо этого f(n) = f(n-1) + f(n-2)мы возьмем цифровую сумму предыдущих 2 записей.

Последовательность должна все еще начинаться 0, 1, после этого различия быстро становятся очевидными. Этот список 0-индексирован, вы также можете использовать 1-индексированный, состояние, которое вы использовали.

f(0)  = 0
f(1)  = 1
f(2)  = 1   # 0 + 1
f(3)  = 2   # 1 + 1
f(4)  = 3   # 1 + 2
f(5)  = 5   # 2 + 3
f(6)  = 8   # 3 + 5
f(7)  = 13  # 8 + 5
f(8)  = 12  # 8 + 1 + 3
f(9)  = 7   # 1 + 3 + 1 + 2
f(10) = 10  # 1 + 2 + 7
f(11) = 8   # 7 + 1 + 0
f(12) = 9   # 1 + 0 + 8
f(13) = 17  # 8 + 9
f(14) = 17  # 9 + 1 + 7
f(15) = 16  # 1 + 7 + 1 + 7
f(16) = 15  # 1 + 7 + 1 + 6
f(17) = 13  # 1 + 6 + 1 + 5
f(18) = 10  # 1 + 5 + 1 + 3
f(19) = 5   # 1 + 3 + 1 + 0
f(20) = 6   # 1 + 0 + 5
f(21) = 11  # 5 + 6
f(22) = 8   # 6 + 1 + 1
f(23) = 10  # 1 + 1 + 8
f(24) = 9   # 8 + 1 + 0
f(25) = 10  # 1 + 0 + 9
f(26) = 10  # 9 + 1 + 0
f(27) = 2   # 1 + 0 + 1 + 0
(After this point it repeats at the 3rd term, 0-indexed)

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

Ваша задача, учитывая число n, вывести n-ую цифру этой последовательности.

Первые 3 цифры: [0,1,1],

24-значный повторный шаблон: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]

Подсказка: вы можете использовать это повторение в своих интересах.

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

БОНУС: Если вы используете повторение в своем ответе, я присваиваю ответ с наименьшим количеством байтов, который использует преимущество повторения в последовательности, вознаграждение в 100 баллов. Это должно быть представлено как часть вашего исходного ответа, после вашего исходного ответа. Посмотрите этот пост как пример того, о чем я говорю: https://codegolf.stackexchange.com/a/108972/59376

Чтобы получить этот бонус, ваш код должен выполняться в постоянном времени ( O(1)) с объяснением.

Победитель премии: Деннис https://codegolf.stackexchange.com/a/108967/59376 <Денис выиграл.

Самая уникальная реализация: https://codegolf.stackexchange.com/a/108970/59376
(также получит 100 баллов, завершенных после выбора правильного ответа)

Оазис , 5 байт

Код:

ScS+T

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

Расширенная версия:

ScS+10

Объяснение:

ScS+   = a(n)
     0 = a(0)
    1  = a(1)
S      # Sum of digits on a(n-1)
 c     # Compute a(n-2)
  S    # Sum of digits
   +   # Add together

JavaScript (ES6), 45 байт

f=(n,x=0,y=1)=>n?f(n-1,y,(x%9||x)+(y%9||y)):x

<input type=number min=0 oninput=o.textContent=f(this.value)><pre id=o>

xи yне может быть и того и другого 9, поскольку для этого потребуется предыдущее число 0, поэтому их цифровая сумма не может превышать 17. Это означает, что цифровой корень для чисел больше, чем 9тот же, что и остаток по модулю 9.

Python 2, 53 байта

f=lambda n:n>1and sum(map(int,`f(n-1)`+`f(n-2)`))or n

Рекурсивная функция. Базовые случаи n=0и n=1выходом n, большее число вычислить значение путем вызова f(n-1)и f(n-2)преобразования каждого в строку, конкатенации двух строк, преобразование каждого символа в целое число с помощью mapс intфункцией, а затем суммирует результирующий список.

Используя информацию по модулю 24, я могу получить 56-байтовую нерекурсивную безымянную функцию:

lambda n:int(('011'+'2358dc7a89hhgfda56b8a9aa'*n)[n],18)

JavaScript (ES6), 34 байта

f=n=>n<2?n:~-f(--n)%9+~-f(--n)%9+2

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

c=[];f=n=>n<2?n:c[n]=c[n]||~-f(--n)%9+~-f(--n)%9+2

<input type=number value=0 min=0 step=1 oninput="O.value=f(this.value)"> <input id=O value=0 disabled>

Как указано в блестящем ответе Нила , выходной сигнал никогда не может превышать 17, поэтому цифровая сумма любого выходного сигнала выше 9 равна n%9. Это также работает с выходами ниже 9; мы можем заставить его работать и для 9, вычитая 1 с ~-до модуля, а затем добавляя обратно в 1 после.

Лучшее, что я мог сделать с жестким кодированием - это 50 байт:

n=>"0x"+"7880136ba5867ffedb834968"[n%24]-(n<3)*9+2

Желе , 8 байт

;DFS
ç¡1

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

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

ç¡1   Main link. No arguments. Implicit left argument: 0

  1   Set the right argument to 1.
ç¡    Repeatedly execute the helper link n times – where n is an integer read from
      STDIN – updating the left argument with the return value and the right
      argument with the previous value of the left argument. Yield the last result.


;DFS  Helper link. Arguments: a, b

;     Concatenate; yield [a, b].
 D    Decimal; convert both a and b to their base-10 digit arrays.
  F   Flatten the result.
   S  Compute the sum of the digits.

Альтернативное решение, 19 байтов, постоянное время

;DFS
9⁵ç23С⁸ịµṠ>?2

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

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

9⁵ç23С⁸ịµṠ>?2  Main link. Argument: n

9               Set the return value to 9
 ⁵              Yield 10.
  ç23С         Execute the helper link 23 times, with initial left argument 10
                and initial right argument 9, updating the arguments as before.
                Yield all intermediate results, returning
                [10,10,2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9].
   ⁸ị           Extract the element at index n. Indexing is 1-based and modular.
     µ          Combine all links to the left into a chain.
       >?2      If n > 2, execute the chain.
      Ṡ         Else, yield the sign if n.

JavaScript (ES6), 52 46 45 байт

_=$=>$<2?$:eval([..._(--$)+[_(--$)]].join`+`)

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

_=$=>$<2?$:eval([..._(--$)+[_(--$)]].join`+`)
_(7)

Выход

13

объяснение

Эта функция проверяет, меньше ли входное значение, чем 2, и если да, то возвращает входное. В противном случае он создает массив из двух значений, которые добавляются друг к другу в виде строк. Эти два значения являются результатом вызова функции с помощью input - 1и input - 2.

...Оператор разбивает эту строку в массив символов, который затем преобразуется в строку еще раз, но теперь с +эс между значениями. Затем эта строка интерпретируется как код, поэтому вычисляется сумма, которая затем возвращается.

Это двойной рекурсивный алгоритм, что делает его довольно неэффективным. ^n-2Для ввода требуется 2 вызова функций n. Таким образом, вот более длинное, но более быстрое решение. Спасибо ETHproductions за то, что придумали.

f=($,p=1,c=0)=>$?f($-1,c,eval([...p+[c]].join`+`)):c

05AB1E , 8 байтов

XÎF‚¤sSO

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

объяснение

XÎ        # push 1,0,input
  F       # input_no times do:
   ‚      # pair the top 2 elements of the stack
    ¤     # push a copy of the 2nd element to the stack
     s    # swap the pair to the top of the stack
      S   # convert to list of digits
       O  # sum

CJam, 22 20 байт

Сохранено 2 байта благодаря Мартину Эндеру

ri2,{(_(jAb\jAb+:+}j

Простой рекурсивный алгоритм, ничего особенного. 0 индексированные.

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

объяснение

ri                    Read an integer from input
  2,                  Push the array [0 1]
    {             }j  Recursive block, let's call it j(n), using the input as n and [0 1] as base cases
     (                 Decrement (n-1)
      _(               Duplicate and decrement again (n-2)
        jAb            Get the list digits of j(n-2)
           \           Swap the top two elements
            jAb        Get the list of digits of j(n-1)
               +       Concatenate the lists of digits
                :+     Sum the digits

CJam, 42 байта

Решение с помощью повторения. Аналогичен алгоритму решения Джонатана Аллана.

ri_2,1+"[2358DC7A89HHGFDA56B8A9AA]"S*~@*+=

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

Perl 6 ,  41  37 байт

{(0,1,{[+] |$^a.comb,|$^b.comb}...*)[$_]}

Попытайся

{(0,1,*.comb.sum+*.comb.sum...*)[$_]}

Попытайся

{ # bare block lambda with implicit parameter ｢$_｣
  (

    0, 1,           # first two values

    # WhateverCode lambda with two parameters ( the two ｢*｣ )
    *.comb.sum      # digital sum of first parameter
    +
    *.comb.sum      # digital sum of second parameter

    ...            # keep using that code object to generate new values until:

    *              # never stop

  )[ $_ ]          # index into the sequence
}

MATL , 15 байт

lOi:"yyhFYAss]&

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

lO       % Push 1, then 0. So the next generated terms will be 1, 1, 2,... 
i        % Input n
:"       % Repeat that many times
  yy     %   Duplicate top two elements in the stack
  h      %   Concatenate into length-2 horizontal vector
  FYA    %   Convert to decimal digits. Gives a 2-row matrix
  ss     %   Sum of all matrix entries
]        % End
&        % Specify that next function (display) will take only 1 input
         % Implicit display

Python 2 , 54 46 байт

f=lambda n:n>2and~-f(n-1)%9+~-f(n-2)%9+2or n>0

Сильно вдохновлен ответом @ETHproductions на ES6 .

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

C 96 байтов

или 61 байт, считая управляющие коды как 1 байт каждый

0 проиндексировано. Подобно некоторым другим ответам, я индексирую таблицу поиска значений, но я сжал ее в 4-байтовые куски. Я не удосужился исследовать версию мода 24, потому что я не думал, что она была настолько интересной, так как другие уже сделали это, но давайте посмотрим правде в глаза, C все равно не победит.

#define a(n) n<3?!!n:2+(15&"\x1\x36\xba\x58\x67\xff\xed\xb8\x34\x96\x87\x88"[(n-3)/2%12]>>n%2*4)

объяснение:

#define a(n)                                                                                     // using a preprocessor macro is shorter than defining a function
             n<3?!!n:                                                                            // when n is less than 3 !!n will give the series 0,1,1,1..., otherwise..
                                                                             (n-3)/2%12          // condition the input to correctly index the string...
                           "\x1\x36\xba\x58\x67\xff\xed\xb8\x34\x96\x87\x88"                     // which has the repeating part of the series encoded into 4 bits each number
                                                                                                 // these are encoded 2 less than what we want as all numbers in the series after the third are 2 <= a(n>2) <= 17 which conforms to 0 <= a(n>2) - 2 <= 15
                                                                                        >>n%2*4  // ensure the data is in the lower 4 bits by shifting it down, n%2 will give either 0 or 1, which is then multiplied by 4
                        15&                                                                      // mask those bits off
                     2+                                                                          // finally, add 2 to correct the numbers pulled from the string

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

Japt , 27 25 байт

U<2?U:~-ß´U %9+~-ß´U %9+2

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

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

Haskell , 54 байта

a!b=sum$read.pure<$>([a,b]>>=show)
g=0:scanl(!)1g
(g!!)

Попробуйте онлайн! Использование:(g!!) 12

Mathematica, 49 байтов

If[#<2,#,Tr[Join@@IntegerDigits[#0/@{#-1,#-2}]]]&

Простое рекурсивное определение. Становится довольно медленно через некоторое время.

Mathematica, 79 71 байт

If[#<3,Sign@#,(9@@LetterNumber@"JJBCEHMLGJHIQQPOMJEFKHJ")[[#~Mod~24]]]&

Жесткое кодирование периодической структуры. Молниеносно и приятно оскорбительно для Mathematica :) Спасибо JungHwan Min за сохранение 8 байт!

Python 2 , 56 байт

Простое итеративное решение.

a,b=0,1
exec'a,b=b,(a%9or a)+(b%9or b);'*input()
print a

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

Использование на (a%9or a)+(b%9or b)самом деле оказалось короче sum(map(int(`a`+`b`)))!

PowerShell , 79 байт

$b,$c=0,1;for($a=$args[0];$a;$a--){$z=[char[]]"$b$c"-join'+'|iex;$b=$c;$c=$z}$b

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

Длинное скучное итеративное решение, которое выполняет вычисления с цифрами и суммами в каждом forцикле В конце цикла, число, которое мы хотим, находится в $b, так что это остается на конвейере и вывод неявный. Обратите внимание, что если ввод 0, то цикл не будет введен, так как условие ложно, поэтому $bостается 0.

Пакетная, 85 байт

@set/ax=0,y=1
@for /l %%i in (1,1,%1)do @set/az=x-x/10*9+y-y/10*9,x=y,y=z
@echo %x%

Мне было интересно, как я собирался перенести мой ответ JavaScript на пакет, но ключ был в решении Python от @ Dennis.

Pyth, 20 байтов

J,01VQ=+JssjRT>2J)@J

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

Набор тестов (Первая часть для форматирования)

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

[Объяснение будет позже]

Рубин, 58 байт

->n{n<3?n<=>0:"9aa2358dc7a89hhgfda56b8a"[n%24].to_i(18)}

Простое жестко закодированное решение.

сложено , 40 байтов

{!2:>[:$digitsflatmap sum\last\,]n*last}

Эта лямбда эквивалентна следующей лямбде:

{n : 2:>[:$digitsflatmap sum\last\,]n*last}

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

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

function f = fib(n)
  if (n <= 1)
    f = n;
  else
    f = sum(int2str((fib(n - 1)))-48) + sum(int2str((fib(n - 2)))-48);
  endif
endfunction

Haskell, 151 байт

import Numeric
import Data.Char
s i=foldr(\c i->i+digitToInt c)0$showInt i""
d a b=a:d b(s a+s b)
f 0=0
f 1=1
f 2=1
f i=d 2 3!!fromIntegral(mod(i-3)24)

Вызовите функцию f 123456789012345678901234567890123456789012345678, например.

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

Несжатый код:

-- FibonacciDigital
-- Gerhard
-- 13 February 2017

module FibonacciDigital () where

import Numeric
import Data.Char

-- sum of digits
digitSum :: Int -> Int 
digitSum i = foldr (\c i -> i + digitToInt c) 0 $ showInt i ""

-- fibonacci digital sequence function with arbitrary starting values
fibonacciDigitals :: Int -> Int -> [Int]
fibonacciDigitals a b = a : fibonacciDigitals b (digitSum a + digitSum b)

-- index -> fibonacci digital value
f :: Integer -> Int 
f 0 = 0 
f 1 = 1 
f 2 = 1 
f i = fibonacciDigitals 2 3 !! fromIntegral (mod (i-3) 24) 

-- End

R, 90 байт

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

function(n,x=0:1){repeat`if`(n,{x=c(x,sum(scan(t=gsub('',' ',x))))[-1];n=n-1},break);x[1]}

Это безымянная функция, которая использует gsubи scan(t=для разделения чисел в векторе на цифры. Их сумма добавляется к вектору, когда первый элемент отбрасывается. repeatиспользуется для пошагового выполнения последовательностиn а результатом является первый элемент вектора.

PHP, 80 байт

for($r=[0,1];$i<$argn;)$r[]=array_sum(str_split($r[$i].$r[++$i]));echo$r[$argn];

Онлайн версия

Mathematica, 67 байт

r=IntegerDigits;f@0=0;f@1=1;f[x_]:=f@x=Tr@r@f[x-1]+Tr@r@f[x-2];f@#&