Definisi

Urutan Fibonacci Kekuatan Bergantian dibentuk sebagai berikut.

1. Mulai dengan urutan kosong dan atur n ke 1 .

2. Hitung f _n , yang n ^th non-negatif Fibonacci nomor , dengan pengulangan.
   0 adalah yang pertama, 1 adalah yang kedua dan yang ketiga, 2 adalah yang keempat. Semua yang lain diperoleh dengan menjumlahkan dua angka sebelumnya dalam urutan, sehingga 3 = 1 + 2 adalah yang kelima, 5 = 2 + 3 adalah yang keenam, dll.

3. Jika n ganjil, ubah tanda f _n .

4. Append 2 ^n-1 salinan f _n ke urutan.

5. Kenaikan n dan kembali ke langkah 2.

Ini adalah seratus syarat pertama dari urutan APF.

 0  1  1 -1 -1 -1 -1  2  2  2  2  2  2  2  2 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3
-3 -3 -3 -3 -3 -3  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5  5
 5  5  5  5  5  5  5  5  5  5  5  5  5 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8
-8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8 -8

Tugas

Tulis program lengkap atau fungsi yang mengambil bilangan bulat positif n sebagai input dan mencetak atau mengembalikan istilah ^ke- n dari urutan APF.

Jika Anda lebih suka pengindeksan 0 berbasis, Anda alternatif dapat mengambil integer non-negatif n dan mencetak atau kembali jumlah APF pada indeks n .

Ini adalah kode-golf ; semoga kode terpendek dalam byte menang!

Uji kasus (berbasis 1)

    1 ->    0
    2 ->    1
    3 ->    1
    4 ->   -1
    7 ->   -1
    8 ->    2
  100 ->   -8
  250 ->   13
  500 ->  -21
 1000 ->   34
11111 ->  233
22222 -> -377
33333 ->  610

Test case (berbasis-0)

    0 ->    0
    1 ->    1
    2 ->    1
    3 ->   -1
    6 ->   -1
    7 ->    2
   99 ->   -8
  249 ->   13
  499 ->  -21
  999 ->   34
11110 ->  233
22221 -> -377
33332 ->  610

Jelly , 5 byte

BLCÆḞ

Cobalah online!

Bagaimana?

Memperluas seri Fibonacci kembali ke indeks negatif sehingga hubungan f(i) = f(i-2) + f(i-1)masih berlaku:

  i   ...   -8  -7  -6  -5  -4  -3  -2  -1   0   1   2   3   4   4   5 ...
f(i)  ...  -21  13  -8   5  -3   2  -1   1   0   1   1   2   3   5   8 ...

Kembali dari i=0angka adalah yang kita perlu ulangi 2 ^n-1 kali, dan Fibonacci bawaan Jelly ÆḞ, akan menghitungnya.

Kita dapat menemukan -i(angka positif) yang kita butuhkan dengan mengambil bit-length of ndan kurangi 1.

Karena kita menginginkan i(angka negatif) kita dapat melakukan 1-bitLengthdan Jelly memiliki atom untuk 1-x,, Cmonad komplemen.

BLCÆḞ - Main link: n               e.g.  500
B     - convert n to a binary list      [1,1,1,1,1,0,1,0,0]
 L    - get the length                   9
  C   - complement                      -8
   ÆḞ - Fibonacci                       -21

Python 2 , 30 byte

f=lambda n:n<1or f(n/4)-f(n/2)

Cobalah online!

Diindeks satu.

Urutannya terasa seperti teka-teki, sesuatu yang dihasilkan Dennis dengan memiliki cara singkat untuk mengekspresikannya. Kekuatan-dari-pengulangan menyarankan berulang dengan menggeser-bit (lantai-membagi dengan 2). Rekursi Fibonacci-tanda bolak f(n)=f(n-2)-f(n-1)dapat disesuaikan dengan bithift sebagai pengganti decrementing. Kasing dasar bekerja dengan baik karena semuanya menyalurkan ke n=0.

Mathematica, 43 36 24 byte

Fibonacci@-Floor@Log2@#&

7 byte disimpan berkat @GregMartin, dan 12 byte lagi berkat @JungHwanMin.

MATL , 19 17 16 11 byte

lOiB"yy-]x&

Input berbasis 1.

Cobalah online! Atau verifikasi semua kasus uji .

Bagaimana itu bekerja

Untuk input n berbasis 1 , misalkan m adalah jumlah digit dalam ekspansi biner dari n . Istilah n -th dalam urutan output adalah istilah ke- m dalam urutan Fibonacci, mungkin dengan tandanya berubah.

Satu ide akan iterate m kali untuk menghitung hal deret Fibonacci. Ini mudah dengan for eachloop menggunakan array angka biner. Jika deret Fibonacci diinisialisasi dengan 0 , maka 1 seperti biasa, iterasi m kali akan menghasilkan istilah m + 2 pada tumpukan, sehingga dua angka teratas harus dihapus. Sebagai gantinya, kami memulai dengan 1 , lalu 0 . Dengan begitu istilah yang dihasilkan berikutnya adalah 1 , 1 , 2 , ... dan hanya satu penghapusan yang diperlukan.

Tanda bisa ditangani dengan menggunakan loop lain untuk mengubah kali tanda m . Tapi itu mahal. Lebih baik untuk mengintegrasikan dua loop, yang dilakukan hanya dengan mengurangi daripada menambahkan dalam iterasi Fibonacci.

l       % Push 1
O       % Push 0
iB      % Input converted to binary array
"       % For each
  yy    %   Duplicate top two elements
  -     %   Subtract. This computes the new Fibonacci term with the sign changes
]       % End
x       % Delete top number
&       % Specify that implicit display should take only one input
        % Implicitly display the top of the stack

JavaScript (ES6), 33 byte

f=(n,p=1,c=0)=>n?-f(n>>1,c,p+c):p

1-diindeks.

Port jawaban xnor adalah 23:

f=n=>n<1||f(n/4)-f(n/2)

Python 2 , 83 82 79 byte

def f(n,a=0,b=1):
 l=bin(n)[2:]
 for _ in l:a,b=b,a+b
 return a*-(len(l)%2or-1)

Cobalah online!

Jelly , 9 byte

BLµ’ÆḞN⁸¡

Menggunakan pengindeksan berbasis satu.

Cobalah online!

Penjelasan

Metode ini berfungsi jika fungsi Fibonacci Anda hanya mendukung argumen non-negatif.

BLµ’ÆḞN⁸¡  Input: integer n
B          Binary digits of n
 L         Length. len(bin(2)) = floor(log2(n)))
  µ        Start new monadic chain on x = len(bin(2))
   ’       Decrement
    ÆḞ     Get Fibonacci(x-1)
       ⁸¡  Repeat x times on that
      N      Negate.
           Return Fibonacci(x-1) if x is even else -Fibonacci(x-1)

Japt , 6 byte

Mg1-¢l

Uji secara online!

Bagaimana itu bekerja

Seperti disebutkan dalam jawaban lain, suku ^ke- n dalam seri Fibonacci tanda-bertanda adalah sama dengan suku ^ke- n dalam seri reguler. n dapat ditemukan dengan mengambil bit-length dari input dan mengurangi satu; meniadakan ini menghasilkan 1 dikurangi bit-length.

Mg1-¢l
    ¢l  // Calculate the length of the input in binary.
  1-    // Subtract this from 1.
Mg      // Get the Fibonacci number at this index.

05AB1E , 11 10 byte

Menggunakan pengindeksan berbasis 1

Fungsi Fibonacci 05AB1E mengembalikan angka fib positif kurang dari n , artinya kita harus menghasilkan lebih dari yang diperlukan, dapatkan yang benar dengan indeks dan kemudian hitung tandanya. Jadi saya ragu metode apa pun yang berbasis di sekitar itu akan lebih pendek daripada menghitung angka secara iteratif.

Menggunakan kesadaran bahwa kita dapat menginisialisasi tumpukan dengan 1, 0terbalik untuk menangani kasus ketika n=1seperti yang dijelaskan dalam jawaban MATL Luis Mendo .

XÎbgG‚D«`-

Cobalah online!

Penjelasan

X             # push 1
 Î            # push 0 and input
  b           # convert input to binary
   g          # get length of binary number
    G         # for N in [1...len(bin(input))-1] do:
     ‚        # pair the top 2 elements of the stack in a list
      D       # duplicate the list 
       «      # concatenate the 2 lists together
        `     # split into separate elements on the stack
         -    # subtract the top 2 elements

Perl 6 , 53 byte

{flat(((0,1,*+*...*)Z*|<-1 1>xx*)Zxx(1,2,4...*))[$_]}

Implementasi sederhana dari urutan, seperti yang dijelaskan.
Berbasis nol.

Julia 0,5 , 19 byte

!n=n<1||!(n/=4)-!2n

Cobalah online!

Bagaimana itu bekerja

Ini menggunakan rumus yang sama dengan jawaban Python @ xnor . Hubungan perulangan
g (n) = g (n-2) + g (n-1) menghasilkan istilah negatif dari deret Fibonacci, yang sama dengan syarat positif dengan tanda-tanda yang bergantian. Dari mana saja dalam menjalankan pengulangan 2 ^k dari angka yang sama, kita dapat memilih pengulangan apa pun dari pengerjaan sebelumnya dari 2 ^k-1 angka dan menjalankan 2 ^k-2 angka sebelumnya dengan membagi indeks dengan 2 dan 4 .

Alih-alih langsung

f(n)=n<1||f(n÷4)-f(n÷2) # 25 bytes

kita dapat mendefinisikan kembali operator untuk tujuan kita. Juga, f akan bekerja sama baiknya dengan mengapung, jadi kita dapatkan

!n=n<1||!(n/4)-!(n/2)   # 21 bytes

Akhirnya, jika kita memperbarui n dengan pembagian dengan 4 , kita dapat menulis n / 2 sebagai 2n dan menghilangkan sepasang parens, yang mengarah ke definisi fungsi 19-byte dalam jawaban ini.

J , 18 byte

(%>:-*:)t.@<:@#@#:

Menggunakan pengindeksan berbasis satu. Mengambil integer input n > 0 dan menghitung floor(log2(n))dengan menemukan panjang representasi binernya dan kemudian menurunkan nilai tersebut satu. Kemudian menemukan koefisien floor(log2(n))-1^th dari fungsi menghasilkan x / (1 + x - x ² ) yang merupakan gf untuk nilai-nilai Fibonacci yang diindeks negatif.

Cobalah online!

Penjelasan

(%>:-*:)t.@<:@#@#:  Input: integer n
                #:  Binary
              #@    Length
           <:@      Decrement
(      )            The generating function x/(1+x-x^2)
  >:                  Increment x
     *:               Square x
    -                 Subtract
 %                    Divide x by previous
        t.          Get series coefficient at the index given by previous value