Definisi

a (1) = 1
a (2) = 1
a (n) = a (na (n-1)) + a (na (n-2)) untuk n> 2 di mana n adalah bilangan bulat

Tugas

Diberikan bilangan bulat positif n, hasilkan a(n).

Testcases

Referensi

OEIS Wajib A005185

code-golf sequence arithmetic Biarawati Bocor
sumber

Terkait .

Leaky Nun

1

Bisakah kita mengembalikan True dalam bahasa yang dapat digunakan sebagai 1 ?

Dennis

1

@ Dennis Jika dalam bahasa itu true sama dengan 1 maka ya.

Leaky Nun

4

Terlepas dari tautan OEIS, ada baiknya merujuk GEB tempat urutan pertama kali muncul.

Martin Ender

1

Menyelesaikan daftar tantangan urutan terkait GEB.

Martin Ender

9

Retina , 84 83 79 74 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1.

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

Cobalah online! (Baris pertama memungkinkan suite tes yang dipisahkan dengan linefeed.)

Saya harus golf ini lagi nanti.

Martin Ender
sumber

9

Haskell, 35 33 byte

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

Menentukan fungsi a.

Anders Kaseorg
sumber

2

Trik yang bagus dengan ikatan! Bukankah sesuatu seperti (b.b)1+(b.b)2lebih pendek dari jumlah?

xnor

Kenapa ya, terima kasih @xnor.

Anders Kaseorg

8

Julia, 29 byte

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

Cobalah online!

Bagaimana itu bekerja

Kami mendefinisikan kembali operator unary !untuk tujuan kami.

Jika n adalah 1 atau 2 , n<3mengembalikan true dan ini adalah nilai pengembalian kami.

Jika n lebih besar dari 2 , n<3mengembalikan false dan || cabang dieksekusi. Ini adalah implementasi langsung dari definisi, di mana ~-nmenghasilkan n - 1 dan ~-~-nmenghasilkan n - 2 .

Dennis
sumber

7

Sesos, 54 byte

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.~.....

Cobalah online

Dibongkar

Atau dalam notasi Brainfuck:

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

Anders Kaseorg
sumber

6

C, 43 42 byte

Disimpan 1 byte berkat @Dennis

Setiap jawaban sama, saya harus melakukan sesuatu yang berbeda!

Cobalah online!

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

Penjelasan: pada dasarnya a(n-a(n-2))+a(n-a(n-1))tetapi dengan perilaku swaggy ^undefined (berfungsi di ponsel saya (gcc) dan ideone).

betseg
sumber

4

1. Anda juga harus menyebutkan kompiler; "barang curian" Anda adalah perilaku yang tidak terdefinisi. 2. Dengan GCC, Anda tidak perlu 1antara ?dan :.

Dennis

@ Dennis Menariknya, formulasi yang sama berfungsi dalam jawaban PowerShell berulang saya ...$b+=$b[$_-$b[$_-2]]+$b[$_---$b[$_]]

AdmBorkBork

@TimmyD beberapa kompiler dapat mengkompilasi a (n) sebelum n--, dan tidak ada perilaku standar (atau didefinisikan) untuk itu. Dengan demikian, perilaku tidak terdefinisi.

betseg

@ Betseg Ya, saya setuju. Hanya menunjukkan bahwa itu tidak selalu unik untuk C.

AdmBorkBork

@ TimmyD Oh, saya salah paham. Saya hanya ingin mengubah fungsi yang digunakan semua orang, jadi milik saya akan berbeda dan kasar: D

betseg

5

Mathematica, 36 byte

Hitungan byte mengasumsikan penyandian ISO 8859-1 dan $CharacterEncodingset Mathematica ke WindowsANSI(default pada Windows; pengaturan lain mungkin bekerja juga, tetapi beberapa seperti UTF-8pasti tidak).

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

Tentukan ±sebagai operator unary.

Saya mencoba menyingkirkan duplikasi, tetapi berakhir dengan jumlah byte yang sama:

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

Martin Ender
sumber

Saya dapat memberi Anda +200 karunia jika Anda melakukannya di Retina

Leaky Nun

@ LeakyNun oke? :)

Martin Ender

Dua hari kemudian.

Leaky Nun

@ LeakyNun Segera Anda tidak akan memiliki perwakilan yang tersisa jika Anda memberikan hadiah dengan mudah.

mbomb007

Mari kita lanjutkan diskusi ini dalam obrolan .

LegionMammal978

4

Jelly , 15 14 byte

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

Cobalah online! atau verifikasi semua kasus uji (perlu beberapa detik).

Bagaimana itu bekerja

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.

Dennis
sumber

Saya dapat memberi Anda +400 karunia jika Anda melakukannya di Sesos.

Leaky Nun

@ LeakyNun Sepertinya ada jawaban Sesos. Itu keluar sehari setelah komentar Anda.

Yytsi

4

Jelly , 14 12 11 byte

ịḣ2S;
1Ç⁸¡2ị

Ini adalah pendekatan berulang.

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

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.

Dennis
sumber

3

Python, 45 40 byte

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

Interpretasi naif sederhana dari tantangan.

Disimpan 5 byte berkat @LeakyNun!

Tembaga
sumber

3

Haskell, 39 37 Bytes

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

persis seperti yang dijelaskan dalam tantangan, menggunakan penjaga

KarlKastor
sumber

Maaf, saya tidak melihat solusi Anda sebelum memposting solusi haskell (identik) saya. Namun bukankah byte dihitung 38 karena baris baru harus diperhitungkan?

Laikoni

Dan penjaga harus n<3untuk h 2 menjadi 1.

Laikoni

@Laikoni Ini 37 menurut fitur Python len dengan string multiline ("" "), kecuali jika Anda menghitung baris baru sebagai dua byte. Ya, saya perhatikan hal lain itu sudah diperbaiki sekarang.

KarlKastor

TIL notepad ++ menghitung baris baru sebagai dua karakter.

Laikoni

@Laikoni menyingkirkan baris baru itu tak terbantahkan 37 byte sekarang.

KarlKastor

3

R, 50 byte

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

Pemakaian:

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

DSkoog
sumber

3

CJam, 19 18 byte

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

Cobalah online!

Menggunakan pendekatan berulang.

Martin Ender
sumber

3

C #, 51 44 byte

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

~~saya ingin tahu apakah ini dapat dipersingkat dengan membuatnya anonim,~~ terima kasih pinkfloydx33!

downrep_nation
sumber

1

c # 6 fungsi ekspresi tubuhint a(int n)=>n<3?1:a(n-a(n-a))+a(n-a(n-2));

pinkfloydx33

Sepertinya saya mengetik sambil mengetik di ponsel saya. Bagian paling -adalam di set paren pertama harus-1

pinkfloydx33

Saya juga tidak memperhatikannya, memperbaikinya rq

downrep_nation

3

JavaScript (ES6), 45 Bytes 34 Bytes

Solusi rekursif dalam ES6. Setiap tips bermain golf sangat dihargai.

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

Terima kasih kepada / u / ismillo untuk memperpendek lebih jauh.

BugHunterUK
sumber

2

Golfscript, 29 byte

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

Cobalah online!

Biarawati Bocor
sumber

2

05AB1E, 29 byte

Solusi berulang.

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

Cobalah online

Emigna
sumber

2

APL, 20 byte

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

Penjelasan:

{⍵≤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

marinus
sumber

2

VBA Excel 87 byte

Non-rekursif, karena saya ingin ini berfungsi untuk n = 100000, katakan:

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

... dan tekan return(byte # 87) di akhir baris untuk mendapatkanEnd Function pernyataan "gratis". Perhatikan bahwa nilai B diimbangi dengan -1 untuk menghindari inisialisasi untuk n = 1 dan 2.

Meminta dalam spreadsheet seperti biasa, misalnya =A(100000)untuk mendapatkan48157

Versi rekursif, 61 byte ,

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

mulai menjadi sangat lambat untuk n> 30, dan tidak bisa dikatakan bekerja sama sekali untuk n> 40.

Joffan
sumber

Kami tidak peduli dengan kinerja. Kami peduli tentang panjang kode. Anda harus memindahkan solusi yang lebih pendek ke bagian atas jawaban Anda.

mbomb007

1

@ mbomb007 Karena saya tidak pernah memenangkan golf, saya akan membuat pilihan sendiri tentang apa yang merupakan program kerja. Tidak dapat menangani bahkan integer byte tunggal tidak cukup baik sejauh yang saya ketahui, ketika ada solusi yang dapat melakukannya dengan mudah.

Joffan

2

Ruby, 36 byte

Implementasi langsung. Saran bermain golf dipersilakan.

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

Sherlock9
sumber

Afaik, Anda dapat menyingkirkan a =. Jika Anda mempostingnya di sini, itu sudah cukup ketika kode Anda mulai dengan ->. Itu dianggap sebagai fungsi anonim.

Seims

@Ims Sayangnya, karena fungsi memanggil dirinya dengan a[n-1]dan semacamnya, fungsi perlu dinamai.

Sherlock9

2

Java 7, 68 61 51 byte

17 disimpan berkat Leaky Nun.

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

Justin
sumber

Selamat datang di PPCG!

AdmBorkBork

Selamat datang di PPCG! Anda mungkin menyukai Tip untuk Golf di Jawa . Bentuk alternatif adalah int a(int n){return n<3?1:a(n-a(n-2))+a(n---a(n));}:, tetapi sayangnya menggunakan jumlah byte yang sama dengan jawaban yang sudah Anda miliki .. Juga, saya akan menentukan bahwa jawaban Anda ada di Java 7, karena jawaban Java 8 akan lebih pendek: n->return n<3?1:a(n-a(n-1))+a(n-a(n-2))( 39 byte ) .

Kevin Cruijssen

Terima kasih untuk teman-teman, dan terima kasih untuk tip di Java8 - Saya tidak menyadari lambda diizinkan seperti itu - meskipun mereka diizinkan seperti itu dengan Python, jadi saya rasa saya tidak pernah memikirkannya. Apakah lambda membutuhkan tanda titik koma?

Justin

@JustinTervay Saya tidak banyak menggunakan Java 8, tetapi dari apa yang saya dengar semi-kolon tidak dihitung dengan ekspresi garis tunggal, menurut komentar oleh @DavidConrad dan @ CAD97 dalam salah satu jawaban Java saya sendiri .

Kevin Cruijssen

2

Oasis , 9 7 5 byte (tidak bersaing)

Non-bersaing , karena bahasa tersebut mengungguli tantangan. Terima kasih kepada Kenny Lau karena telah menghemat 4 byte. Kode:

ece+V

Formulir yang diperluas ( Vkependekan dari 11):

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

Kode:

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

Cobalah online! . Menghitung n = 1000 dalam 0,1 detik.

Adnan
sumber

1

PowerShell v2 +, 85 79 69 byte

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

Mengambil input $n, menetapkan $bmenjadi array @(1, 1), lalu memasukkan loop dari 2 .. $n. Setiap iterasi kami tempelkan ke $bperhitungan terbaru dalam urutan dengan sederhana +=dan definisi urutan. Kami kemudian mengeluarkan nomor yang sesuai dari $b(dengan -1array karena di PowerShell diindeks nol). Ini berfungsi jika $nada 1atau 2karena kedua nilai tersebut telah diisi sebelumnya ke dalam indeks yang lebih rendah $bsejak awal, jadi meskipun loop diack pada junk, toh diabaikan.

Solusi rekursif 78 76 byte

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

Pertama kali saya menggunakan jawaban yang setara dengan lambda, karena biasanya solusi berulang lebih pendek (seperti yang Anda lihat dari semua parenting bersarang). ~~Tetapi, dalam kasus ini, parested bersarang hampir digandakan dalam solusi iteratif dengan panggilan array bersarang, sehingga solusi rekursif lebih pendek.~~ Tidak, solusi berulang memang lebih pendek (lihat di atas).

Sebut saja melalui operator eksekusi, seperti &$a 20. Hanya panggilan rekursif langsung.

AdmBorkBork
sumber

1

JavaScript (ES6), 66 byte

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

Versi non-rekursif untuk kecepatan; versi rekursif mungkin lebih pendek tetapi saya akan membiarkannya ditulis orang lain. Saya selalu suka ketika saya bisa menggunakannya reduce. Catatan: 1 byte disimpan dengan mengembalikan true(yang 1digunakan saat digunakan dalam konteks integer) untuk dari a(1)dan a(2).

Neil
sumber

1

Pyth, 16 byte

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

Menentukan fungsi y.

Cobalah online (ditambahkan yMS20untuk mencetak 20 nilai pertama)

Anders Kaseorg
sumber

1

Keempat, 76 byte

Saya akhirnya berhasil!

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

Cobalah online

Penjelasan:

: 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 ;

Cobalah online (sedikit tidak golf dari atas)

Sayangnya, saling rekursi agak terlalu bertele - tele untuk digunakan untuk bermain golf.

mbomb007
sumber

1

Maple, 43 41 byte

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

Pemakaian:

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

Masalah ini tentu saja merupakan kandidat yang baik untuk memoisasi. Dengan menggunakan cache pilihan , waktu proses dikurangi secara signifikan:

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

Ini bisa dilihat menggunakan:

CodeTools:-Usage( aC(50) );

DSkoog
sumber

0

J, 29 28 byte

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

Menggunakan definisi rekursif.

Pemakaian

Perintah tambahan digunakan untuk memformat beberapa input / output.

   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

Penjelasan

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

mil
sumber

0

dc, 62 byte

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

Solusi ini memanfaatkan array dan rekursi.

?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

Joe
sumber

Kesimpulannya, jika ada yang membangun IDE untuk dc, beri tahu saya!

Joe

0

Erlang, 46 byte

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

cPu1
sumber

0

Lua, 59 byte

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

brianush1
sumber

Hofstadter Q-sequence

Definisi

Tugas

Testcases

Referensi

Jawaban:

Retina , 84 83 79 74 byte

Haskell, 35 33 byte

Julia, 29 byte

Bagaimana itu bekerja

Sesos, 54 byte

Dibongkar

C, 43 42 byte

Mathematica, 36 byte

Jelly , 15 14 byte

Bagaimana itu bekerja

Jelly , 14 12 11 byte

Bagaimana itu bekerja

Python, 45 40 byte

Haskell, 39 37 Bytes

R, 50 byte

CJam, 19 18 byte

C #, 51 44 byte

JavaScript (ES6), 45 Bytes 34 Bytes

Golfscript, 29 byte

05AB1E, 29 byte

APL, 20 byte

VBA Excel 87 byte

Ruby, 36 byte

Java 7, 68 61 51 byte

Oasis , 9 7 5 byte (tidak bersaing)

PowerShell v2 +, 85 79 69 byte

Solusi rekursif 78 76 byte

JavaScript (ES6), 66 byte

Pyth, 16 byte

Keempat, 76 byte

Maple, 43 41 byte

J, 29 28 byte

Pemakaian

Penjelasan

dc, 62 byte

Erlang, 46 byte

Lua, 59 byte