Kita semua akrab dengan deret Fibonacci :

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

Namun, alih-alih, f(n) = f(n-1) + f(n-2)kami akan mengambil jumlah digital dari 2 entri sebelumnya.

Urutan masih harus dimulai dengan 0, 1, setelah itu perbedaannya jelas dengan cepat. Daftar ini diindeks 0, Anda dapat menggunakan 1-diindeks juga, menyatakan yang Anda gunakan.

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)

Catatan: Saya tidak melihat pengulangan sampai saya memposting tantangan itu sendiri, dan di sini saya berpikir tidak mungkin untuk menulis tantangan Fibonacci novel baru.

Tugas Anda adalah, diberi nomor n, menampilkan digit ke-n dari urutan ini.

Pertama 3 digit: [0,1,1],

Pola berulang 24 digit: [2,3,5,8,13,12,7,10,8,9,17,17,16,15,13,10,5,6,11,8,10,9,10,10]

Petunjuk: Anda mungkin dapat memanfaatkan pengulangan ini untuk keuntungan Anda.

Ini adalah kode-golf , byte-count terendah adalah pemenangnya.

BONUS: Jika Anda menggunakan pengulangan dalam jawaban Anda, saya akan memberikan jawaban byte-count terendah yang mengambil keuntungan dari pengulangan dalam urutan hadiah 100 poin. Ini harus diserahkan sebagai bagian dari jawaban awal Anda, setelah jawaban awal Anda. Lihat posting ini sebagai contoh dari apa yang saya bicarakan: https://codegolf.stackexchange.com/a/108972/59376

Agar memenuhi syarat untuk bonus ini, kode Anda harus dijalankan dalam waktu yang konstan ( O(1)) dengan penjelasan.

Pemenang Bonus: Dennis https://codegolf.stackexchange.com/a/108967/59376 <Dennis menang.

Implementasi Paling Unik: https://codegolf.stackexchange.com/a/108970/59376
(Juga akan menerima 100 poin, diselesaikan setelah jawaban yang benar dipilih)

Oasis , 5 byte

Kode:

ScS+T

Cobalah online!

Versi yang diperluas:

ScS+10

Penjelasan:

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 byte

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>

xdan ytidak bisa keduanya 9, karena itu akan membutuhkan nomor sebelumnya 0, jadi jumlah digital mereka tidak dapat melebihi 17. Ini berarti bahwa akar digital untuk angka lebih besar dari 9sama dengan modulo sisanya 9.

Python 2, 53 byte

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

Fungsi rekursif. Kasus dasar n=0dan n=1hasil n, angka yang lebih besar menghitung nilai dengan memanggil f(n-1)dan f(n-2)mengonversikan masing-masing menjadi string, menggabungkan dua string, mengubah setiap karakter menjadi integer menggunakan fungsi, mapdengan intfungsi, dan kemudian menjumlahkan daftar yang dihasilkan.

Menggunakan informasi modulo-24 saat ini saya bisa mendapatkan fungsi tanpa nama non-rekursif 56 byte:

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

JavaScript (ES6), 34 byte

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

Dapat membekukan browser Anda untuk input di atas 27 atau lebih, tetapi itu berfungsi untuk semua nilai input. Ini dapat diverifikasi dengan cache sederhana:

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>

Seperti yang ditunjukkan dalam jawaban brilian Neil , output tidak pernah bisa melebihi 17, sehingga jumlah digital dari setiap output di atas 9 sama dengan n%9. Ini juga bekerja dengan output di bawah 9; kita dapat membuatnya bekerja untuk 9 juga dengan mengurangi 1 dengan ~-sebelum modulus, lalu menambahkan kembali 1 setelah.

Yang terbaik yang bisa saya lakukan dengan hardcoding adalah 50 byte:

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

Jelly , 8 byte

;DFS
ç¡1

Cobalah online!

Bagaimana itu bekerja

ç¡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.

Solusi alternatif, 19 byte, waktu konstan

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

Cobalah online!

Bagaimana itu bekerja

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 byte

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

Pemakaian

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

Keluaran

13

Penjelasan

Fungsi ini memeriksa apakah input lebih kecil dari 2, dan jika demikian, ia mengembalikan input. Kalau tidak, itu menciptakan array dari dua nilai yang ditambahkan satu sama lain sebagai string. Kedua nilai tersebut adalah hasil dari memanggil fungsi dengan input - 1dan input - 2.

The ...Operator membagi string ini ke dalam array dari karakter, yang kemudian dikonversi ke string lagi, tapi sekarang dengan +es antara nilai-nilai. String ini kemudian diartikan sebagai kode, sehingga jumlahnya dihitung, yang kemudian dikembalikan.

Ini adalah algoritma rekursif ganda, yang membuatnya tidak efisien. Perlu 2 ^n-2panggilan fungsi untuk input n. Karena itu, inilah solusi yang lebih panjang tetapi lebih cepat. Terima kasih kepada ETHproductions untuk datang dengan itu.

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

05AB1E , 8 byte

XÎF‚¤sSO

Cobalah online!

Penjelasan

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 byte

Disimpan 2 byte berkat Martin Ender

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

Algoritma rekursif langsung, tidak ada yang mewah. Diindeks 0.

Cobalah online! atau tes untuk 0-50 (sebenarnya berjalan cukup cepat).

Penjelasan

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 byte

Solusi menggunakan pengulangan. Algoritma serupa dengan solusi Jonathan Allan.

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

Cobalah online!

Perl 6 ,  41  37 byte

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

Cobalah

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

Cobalah

{ # 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 byte

lOi:"yyhFYAss]&

Cobalah online!

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 byte

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

Sangat terinspirasi oleh jawaban ES6 dari @ETHproductions .

Cobalah online!

C, 96 byte

atau 61 byte menghitung kode melarikan diri masing-masing 1 byte

0 diindeks. Mirip dengan beberapa jawaban lain saya mengindeks tabel pencarian nilai tetapi saya telah mengompresnya menjadi potongan 4 byte. Saya tidak repot-repot menyelidiki versi mod 24 karena saya tidak berpikir itu menarik karena yang lain sudah melakukannya tetapi mari kita hadapi itu, C tidak akan menang lagi.

#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)

penjelasan:

#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

Cobalah online!

Japt , 27 25 byte

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

Cobalah online!

Disimpan 2 byte berkat produk ETH.

Haskell , 54 byte

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

Cobalah online! Pemakaian:(g!!) 12

Mathematica, 49 byte

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

Definisi rekursif langsung. Akan sangat lambat setelah beberapa saat.

Mathematica, 79 71 byte

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

Hardcoding pola periodik. Petir cepat dan memuaskan kasar untuk Mathematica :) Terima kasih kepada JungHwan Min untuk menghemat 8 byte!

Python 2 , 56 byte

Solusi berulang sederhana.

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

Cobalah online!

Penggunaan (a%9or a)+(b%9or b)sebenarnya ternyata lebih pendek dari sum(map(int(`a`+`b`)))!

PowerShell , 79 byte

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

Cobalah online!

Solusi iteratif membosankan yang panjang yang melakukan perhitungan digit-sum langsung setiap forloop. Pada akhir dari loop, angka yang kita inginkan ada $b, jadi yang tersisa di pipeline dan outputnya implisit. Perhatikan bahwa jika inputnya adalah 0, maka loop tidak akan masuk karena kondisinya salah, jadi $btetap 0.

Batch, 85 byte

@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%

Saya bertanya-tanya bagaimana saya akan mem-porting jawaban JavaScript saya ke batch tetapi petunjuknya ada pada solusi Python @ Dennis.

Pyth, 20 byte

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

Suatu program yang mengambil input dari bilangan bulat yang diindeks nol dan mencetak hasilnya.

Test suite (Bagian pertama untuk pemformatan)

Bagaimana itu bekerja

[Penjelasan datang nanti]

Ruby, 58 byte

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

Solusi hardcoded sederhana.

ditumpuk , 40 byte

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

Lambda ini setara dengan lambda berikut:

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

Cobalah online!

Oktaf, 148 byte

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 byte

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)

Aktifkan fungsi dengan f 123456789012345678901234567890123456789012345678, misalnya.

Kode ini juga berfungsi dengan indeks yang sangat besar. Karena fungsionalitas modulo 24 yang diterapkan sangat cepat.

Kode tidak terkompresi:

-- 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 byte

Solusi yang sangat panjang, tapi ini lebih baik daripada yang semula saya miliki. Saya curiga ada banyak cara yang lebih baik untuk melakukan ini, tetapi saya tidak bisa melihatnya saat ini.

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

Ini adalah fungsi tanpa nama yang menggunakan gsubdan scan(t=untuk membagi angka-angka dalam vektor menjadi digit. Jumlahnya ditambahkan ke vektor sementara item pertama dijatuhkan. repeatdigunakan untuk melangkah melalui urutan nwaktu dan hasilnya adalah item pertama dari vektor.

PHP, 80 Bytes

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

Versi Online

Mathematica, 67 byte

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