Urutan Kuasa Fibonacci Bendera

Dennis 08/19/2017. 12 answers, 2.084 views
code-golf math sequence array-manipulation fibonacci

Definisi

The Sequence Fibonacci Power Alternator dibentuk seperti berikut.

  1. Mulakan dengan urutan kosong dan tetapkan n ke 1 .

  2. Kira f n , nombor Fibonacci bukan negatif n , dengan pengulangan.
    0 adalah yang pertama, 1 ialah yang kedua dan yang ketiga, 2 ialah yang keempat. Semua yang lain diperoleh dengan menjumlahkan dua nombor sebelumnya dalam urutan, jadi 3 = 1 + 2 adalah kelima, 5 = 2 + 3 adalah keenam, dsb.

  3. Jika n adalah ganjil, tukar tanda f n .

  4. Tambah 2n-1 salinan f n ke urutan.

  5. Peningkatan n dan kembali ke langkah 2.

Ini adalah seratus segi pertama 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 penuh atau fungsi yang mengambil integer positif n sebagai input dan mencetak atau mengembalikan tempoh n urutan JPA.

Sekiranya anda lebih suka mengindeks berasaskan 0, anda boleh memilih integer bukan negatif n dan mencetak atau mengembalikan nombor APF pada indeks n .

Ini adalah ; boleh kod terkecil dalam bait menang!

Kes ujian (berasaskan 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 

Kes ujian (berasaskan 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 
4 Comments
Okx 01/31/2017
Adakah terdapat kekangan untuk n ?
2 Dennis♦ 01/31/2017
Selagi algoritma anda berfungsi dengan n nilainya yang besar, anda boleh mengandaikan ia sesuai dengan jenis data anda.
1 Mindwin 02/01/2017
Adakah ini mempunyai nombor OEIS?
Dennis♦ 02/01/2017
@Mindwin Ia tidak.

12 Answers


Jonathan Allan 01/31/2017.

Jeli , 5 bait

BLCÆḞ 

Try it online!

Bagaimana?

Memperluas siri Fibonacci kembali ke indeks negatif supaya hubungan f(i) = f(i-2) + f(i-1) masih memegang:

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=0 angka-angka itu adalah yang kita perlu ulangi 2n-1 kali, dan Fibonacci Jelly's built-in, ÆḞ , akan menghitungnya.

Kita boleh mencari -i (nombor positif) yang kita perlukan dengan mengambil bit-panjang n dan tolak 1 .

Kerana kita mahu i (nombor negatif) kita boleh sebaliknya melakukan 1-bitLength dan Jelly mempunyai atom untuk 1-x , C , monad pelengkap.

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 
3 comments
miles 01/31/2017
Saya tahu ada jalan yang lebih pendek tetapi tidak dengan banyaknya, fikir ia akan menjadi 7 byte dengan cara untuk menghapus µ dan
Jonathan Allan 01/31/2017
Penolakan yang berulang kali anda pandai walaupun, saya melihat kekuatan minus one, yang menambah beberapa bait, sehingga saya teringat mengenai nilai Fibonacci negatif dan cuba memasukkannya ke dalam monadanya Jelly.
4 ETHproductions 01/31/2017
Secara jujur, saya terkejut Jelly tidak mempunyai one-byte builtin untuk mendapatkan panjang biner nombor ...

xnor 01/31/2017.

Python 2 , 30 bait

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

Cuba dalam talian!

Satu diindeks.

Urutan itu dirasakan seperti teka-teki, sesuatu yang dihasilkan oleh Dennis dengan cara yang singkat untuk menyatakannya. Ulangan kuasa dua menerangkan pengulangan oleh bit-shifting (pembahagi lantai dengan 2). Rekod Fibonacci yang bersilih ganti f(n)=f(n-2)-f(n-1) boleh disesuaikan dengan bitshift di tempat pengurangan. Kes asas berfungsi dengan baik kerana semua funnels kepada n=0 .


martin 02/01/2017.

Mathematica, 43 36 24 bytes

Fibonacci@-Floor@Log2@#& 

7 bait disimpan terima kasih kepada @GregMartin, dan 12 lagi terima kasih kepada @JungHwanMin.

2 comments
1 Greg Martin 01/31/2017
Anda boleh menyimpan beberapa bait dengan Floor@Log2@# , dan dengan menulis Fibonacci[t=...] (dan dengan membuang ruang dalam eksponen terakhir).
1 JungHwan Min 02/01/2017
-12 bait: Fibonacci@-Floor@Log2@#& - Fibonacci boleh mengambil argumen negatif juga (menjaga tanda untuk anda).

Luis Mendo 02/01/2017.

MATL , 19 17 16 11 bait

lOiB"yy-]x& 

Input adalah berasaskan 1.

Cuba dalam talian! Atau sahkan semua kes ujian .

Bagaimana ia berfungsi

Untuk input berasaskan n , mari m ialah bilangan digit dalam pengembangan binari n . Istilah n -th dalam urutan output adalah istilah m -th dalam urutan Fibonacci, mungkin dengan tanda itu berubah.

Satu idea adalah untuk melancarkan m kali untuk mengira terma urutan Fibonacci. Ini mudah dengan for each gelung menggunakan pelbagai digit binari. Sekiranya urutan Fibonacci telah diisialisasikan dengan 0 , maka 1 seperti biasa, melangkah m kali akan menghasilkan m+2 pada timbunan, jadi dua angka teratas perlu dipadamkan. Sebaliknya, kami memulakan dengan 1 , kemudian 0 . Dengan cara itu, istilah yang dijana akan datang ialah 1 , 1 , 2 , ... dan hanya one penghapusan yang diperlukan.

Tanda itu boleh ditangani dengan menggunakan gelung lain untuk menukar masa m log. Tetapi itu mahal. Adalah lebih baik untuk mengintegrasikan kedua-dua gelung, yang dilakukan hanya dengan subtracting dan bukannya menambah dalam lelaran 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 

ETHproductions 04/13/2017.

JavaScript (ES6), 33 bait

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

1 diindeks.

Jawapan pelabuhan xnor ialah 23:

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

ovs 02/18/2017.

Python 2 , 83 82 79 bait

 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) 

Cuba dalam talian!

1 comments
TuukkaX 01/31/2017
Whitespace tidak diperlukan pada or -1 .

miles 01/31/2017.

Jelly , 9 bait

BLµ’ÆḞN⁸¡ 

Menggunakan satu indeks berasaskan.

Cuba dalam talian!

Penjelasan

Kaedah ini berfungsi jika fungsi Fibonacci anda hanya menyokong argumen bukan 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) 

ETHproductions 01/31/2017.

Japt , 6 bait

Mg1-¢l 

Uji dalam talian!

Bagaimana ia berfungsi

Seperti yang dinyatakan dalam jawapan yang lain, istilah n dalam siri simbol Fibonacci yang bersilih ganti adalah sama dengan istilah -n dalam siri biasa. n boleh didapati dengan mengambil sedikit input dan mengurangkan satu; menafikan keputusan ini dalam 1 tolak bit-panjang.

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

Emigna 04/13/2017.

05AB1E , 11 10 bait

Menggunakan pengindeksan berasaskan 1

Fungsi Fibonacci 05AB1E mengembalikan nombor fib positif yang kurang dari n , yang bermaksud kita perlu menghasilkan lebih daripada yang diperlukan, dapatkan yang betul dengan indeks dan kemudian hitung tanda itu. Oleh itu, saya meragui apa-apa kaedah berdasarkan sekitar yang akan lebih pendek daripada mengira nombor iteratif.

Menggunakan kesedaran bahawa kita dapat memulakan stack dengan 1, 0 diterbalikkan untuk mengendalikan kes apabila n=1 seperti yang dijelaskan dalam jawapan MATL Luis Mendo .

XÎbgG‚D«`- 

Cuba dalam talian!

Explanation

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 

smls 01/31/2017.

Perl 6 , 53 bait

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

Pelaksanaan jujukan itu secara langsung, cara ia diterangkan.
Berasaskan nol.


Dennis 04/13/2017.

Julia 0.5 , 19 bait

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

Cuba dalam talian!

Bagaimana ia berfungsi

Ini menggunakan formula yang sama dengan jawapan Python @ xnor . Hubungan berulang
g(n) = g(n-2) + g(n-1) menjana sebutan negatif urutan Fibonacci, yang sama dengan istilah positif dengan tanda-tanda ganti. Dari mana-mana sahaja dalam pengulangan 2 k berulang dengan nombor yang sama, kita dapat memilih sebarang pengulangan pada run sebelumnya dari 2 k-1 nombor dan run 2 k-2 nombor sebelum mereka dengan membahagikan indeks dengan 2 dan 4 .

Bukannya langsung

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

kita boleh mentakrifkan semula operator bagi tujuan kita. Juga, f akan bekerja seperti halnya dengan terapung, jadi kita dapat

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

Akhir sekali, jika kita mengemas kini n dengan pembahagian sebanyak 4 , kita dapat menulis n/2 sebagai 2n dan meninggalkan sepasang parens, yang membawa kepada definisi fungsi 19-bait dalam jawapan ini.


miles 02/05/2017.

J , 18 bait

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

Menggunakan satu indeks berasaskan. Mengambil input integer n > 0 dan mengira floor(log2(n)) dengan mencari panjang perwakilan binari dan kemudian menaksir nilai itu dengan satu. Ia kemudian mendapati floor(log2(n))-1 pekali floor(log2(n))-1 th atas fungsi penjanaan x / (1 + x - x 2 ) yang merupakan gf untuk nilai Fibonacci yang diindeks negatif.

Cuba dalam talian!

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 

Related questions

Hot questions

Language

Popular Tags