Anda mungkin pernah mendengar angka Fibonacci. Ya tahu, urutan integer yang dimulai dengan 1, 1, dan kemudian setiap nomor baru adalah jumlah dari dua yang terakhir?

1 1 2 3 5 8 13...

Dan seterusnya. Tantangan tentang angka Fibonacci cukup populer di sini . Tetapi siapa yang mengatakan bahwa angka-angka Fibonacci harus dimulai dengan 1, 1? Mengapa mereka tidak bisa memulainya 0, 1? Baiklah, mari kita mendefinisikan kembali mereka mulai dari 0:

0 1 1 2 3 5 8 13...

Tapi ... Kita juga tidak harus berhenti di situ! Jika kita dapat menambahkan dua angka terakhir untuk mendapatkan yang berikutnya, kita juga bisa mengurangi angka pertama dari angka kedua untuk menambahkan angka baru. Jadi itu bisa dimulai dengan 1, 0:

1 0 1 1 2 3 5 8 13...

Kita bahkan dapat berakhir dengan negatif:

-1 1 0 1 1 2 3 5 8 13...

Dan seri ini juga berlangsung selamanya. Saya pikir itu menarik bagaimana akhirnya agak mencerminkan angka-angka Fibonacci biasa, hanya dengan setiap angka lainnya dibuat negatif:

13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13...

Sebut seri ini "Nomor Fibonacci Diperpanjang", atau EFN . Karena sebenarnya tidak ada angka negatif yang jelas untuk memulai seri ini, kita akan mengatakan bahwa 0 muncul pada 0 , angka Fibonacci reguler meluas ke indeks positif, dan angka Fibonacci negatif (setengah negatif?) ke indeks negatif, seperti:

Indices: ...-7  -6 -5  -4 -3  -2 -1  0  1  2  3  4  5  6  7 ...
Values:  ...13  -8  5  -3  2  -1  1  0  1  1  2  3  5  8  13...

Ini mengarah ke tantangan hari ini:

Dengan bilangan bulat N , kembalikan setiap indeks tempat N muncul dalam seri EFN .

Beberapa pengamatan acak pada tugas ini:

• 1 muncul lebih kali dalam EFN dari nomor lain: [-1, 1, 2]. Tidak ada nomor akan muncul di lebih dari 3 tempat.

• Setiap angka Fibonacci> 1 akan muncul sekali (3, 8, 21, dll.) Atau dua kali (2, 5, 13, dll.)

Klarifikasi Peraturan:

• Jika abs(N)bukan angka Fibonacci, itu tidak akan pernah muncul di seri EFN , jadi Anda harus mengeluarkan apa-apa / koleksi kosong jika memungkinkan, atau jika itu tidak mungkin dalam bahasa Anda, Anda dapat menampilkan beberapa nilai non-numerik yang konstan.
• Jika N muncul di banyak tempat di EFN , output Anda tidak perlu disortir. Meskipun setiap indeks harus muncul tepat satu kali.
• Meskipun sebagian besar tantangan urutan memungkinkan Anda untuk memilih apakah Anda ingin menggunakan pengindeksan berbasis 1 atau 0, tantangan ini harus menggunakan pengindeksan yang dijelaskan (di mana 0 muncul pada 0).
• Anda dapat mengambil I / O melalui format standar apa pun.

Uji Kasus

-13: []
-12: []
-11: []
-10: []
-9: []
-8: [-6]
-7: []
-6: []
-5: []
-4: []
-3: [-4]
-2: []
-1: [-2]
0: 0
1: [-1, 1, 2]
2: [-3, 3]
3: [4]
4: []
5: [-5, 5]
6: []
7: []
8: [6]
9: []
10: []
11: []
12: []
13: [-7, 7]

Dan beberapa test case yang lebih besar:

89: [-11, 11]
1836311903: [46]
10000: []
-39088169: [-38]

Seperti biasa, jawaban terpendek dalam byte menang!

Haskell , 78 byte

4 byte disimpan berkat nimi

a#b=a:b#(a-b)
f 0=[0]
f a=do{(i,x)<-zip[0..a*a+1]$0#1;[-i|x==a]++[i|abs x==a]}

Cobalah online!

Pertama-tama kita mengatur (#), (#)mengambil dua parameter, adan b, dan mengembalikan daftar yang dimulai dengan adan diikuti oleh b#(a-b). Ini membuat daftar yang tidak terbatas, tetapi karena Haskell malas, kita tidak perlu khawatir tentang hal itu berulang selamanya. Ini pada dasarnya bekerja mundur menciptakan urutan Fibonacci sebelum pasangan tertentu. Misalnya (0#1)akan menjadi daftar semua angka Fibonacci dengan indeks negatif.

Dari sini kita buat f. fmengambil argumen ayang merupakan nomor yang kami coba temukan dalam urutan. Di sini kita menggunakan donotasi untuk melakukan pemahaman daftar. Kami mulai dengan mengambil a*a+1elemen pertama dari daftar 0#1¹ . Karena fungsi a*a+1tumbuh lebih cepat daripada kebalikan dari deret Fibonacci kita dapat yakin bahwa jika kita memeriksa dalam batas ini kita akan menemukan semua hasil. Ini mencegah kita mencari daftar yang tidak terbatas. Kemudian untuk setiap nilai xdan indeks i, jika x==akami menemukan adalam setengah negatif dari urutan maka kami kembali -i, dan jika abs x==akami kembali ijuga karena nilai absolut dari setengah negatif adalah setengah positif sehingga kami menemukannya di sana.

Karena ini membuat daftar [0,0]untuk 0kita hardcode output yang benar untuk yang itu.

^{1: Trik ini diambil dari jawaban bersih Οurous ' . Speedup yang sama berlaku di sini seperti di sana, ganti a*a+1dengan abs a+1untuk menghemat banyak waktu.}

Bersih , 132 120 109 byte

import StdEnv
g n|n<2=n=g(n-1)+g(n-2)
?k=[e\\p<-[0..k*k+1],e<-if(isOdd p)([~p,p]%(0,k))[p*sign k]|g p==abs k]

Cobalah online!

g :: Int -> Intadalah fungsi Fibonacci.
? :: Int -> [Int]hanya indeks ke dalam unsur-unsur dari EFN dalam k^2+1dari 0.

Untuk versi yang berjalan dalam jumlah waktu yang waras, ubah k*k+1menjadi abs k+1.

Jelly , 11 byte

A‘ŒRÆḞẹ_A_2

Cobalah online!

JavaScript (ES6),  94  93 byte

n=>(g=a=>a*a<n*n?g(b,b+=a,i++):a%n)(i=0,b=1)?[]:i&1?n<0?~n?[]:-2:i-1?[-i,i]:[-i,i,2]:n<0?-i:i

Cobalah online!

$-0$$n=0$

APL (Dyalog Classic) , 52 50 byte

Membutuhkan ⎕IO←0

{X-⍨⍸⍵=F,⍨⌽0,F×1 ¯1⍴⍨≢F←{⍵≤1:1⋄+/∇¨⍵-1 2}¨⍳X←1+|⍵}

Cobalah online!

Retina 0.8.2 , 104 102 byte

[1-9].*
$*
(-)?(\b1|(?>\3?)(\2))*(1)$|(0)?.*
$5$1$4$4$#2$*
-1(11)+$

^1(11)+$
-$&,$&
1+
$.&
^2$
-1,1,2

Cobalah online! Penjelasan:

[1-9].*
$*

Konversi ke unary, kecuali inputnya nol.

(-)?(\b1|(?>\3?)(\2))*(1)$|(0)?.*
$5$1$4$4$#2$*

Hitung indeks Fibonacci dari nilai absolut, tetapi jika angka tersebut bukan angka Fibonacci maka hapus saja, kecuali jika itu nol. Ini menggunakan regex Fibonacci-testing @ MartinEnder.

-1(11)+$

Hapus angka negatif yang nilai absolutnya adalah angka Fibonacci aneh.

^1(11)+$
-$&,$&

Tambahkan indeks negatif untuk angka Fibonacci positif ganjil.

1+
$.&

Konversikan ke desimal.

^2$
-1,1,2

Tambahkan indeks ekstra untuk 1.

Sebenarnya , 34 byte

;╗3*;±kSix⌠;;AF@;1&@0>*YτD(s**╜=⌡░

Brute-force menyelamatkan hari

Penjelasan:

;╗3*;±kSix⌠;;AF@;1&@0>*YτD(s**╜=⌡░
;╗                                  save a copy of the input (let's call it N) to register 0 (the main way to get additional values into functions)
  3*;±                              -3*N, 3*N
      kSi                           push to list, sort, flatten (sort the two values on the stack so that they are in the right order for x)
         x                          range(min(-3*N, 3*N), max(-3*N, 3*N))
          ⌠;;AF@;1&@0>*YτD(s**╜=⌡░  filter (remove values where function leaves a non-truthy value on top of the stack):
           ;;                         make two copies of parameter (let's call it n)
             AF                       absolute value, Fib(|n|)
               @;                     bring a copy of n to the top of the stack and make another copy
                 1&                   0 if n is divisible by 2 else 1
                   @0>                1 if n is negative else 0 (using another copy of n)
                      *               multiply those two values (acts as logical AND: is n negative and not divisible by 2)
                       YτD            logical negate, double, decrement (maps [0, 1] to [1, -1])
                          (s          sign of n (using the last copy)
                            **        multiply Fib(|n|), sign of n, and result of complicated logic (deciding whether or not to flip the sign of the value for the extended sequence)
                              ╜=      push value from register 0, equality comparison (1 if value equals N else 0)

Cobalah online!

Python 3 , 92 byte

f=lambda x,l=[],i=0,a=0,b=1:i<x*x+2and f(x,l+[i][:a==x]+[-i][:i%2*2*a-a==x],i+1,b,a+b)or{*l}

Cobalah online!

Mengembalikan satu set indeks.

Python 2 , 87 85 byte

f=lambda v,a=0,b=1,i=1:v*v>=a*a and[i]*(v==b)+[1-i]*((-1)**i*a==v)+f(v,b,a+b,i+1)or[]

Cobalah online!

05AB1E , 36 byte

x*ÝʒÅfIÄQ}Ii®šë1KIdiÐ`ÉiD(ì}ëD`Èi(ë¯

Harus ada pendekatan yang lebih baik ..>.> Ada enam (atau tujuh jika kita memasukkan 0) skenario berbeda untuk tantangan ini, dan itu membunuhku ..

Cobalah secara online atau verifikasi semua kasus uji .

Penjelasan:

x*Ý            # Create a list in the range [0, (implicit) input * input * 2]
   ʒ     }     # Filter this list by:
    Åf         #  Where the Fibonacci value at that index
      IÄQ      #  Is equal to the absolute value of the input
Ii             # If the input is exactly 1:
  ®š           #  Prepend -1 to the list
ë              # Else:
 1K            #  Remove all 1s (only applies to input -1)
 Idi           #  If the input is non-negative:
    Ð`Éi   }   #   If the found index in the list is odd:
        D(ì    #    Prepend its negative index to the list
   ë           #  Else (the input is negative):
    D`Èi       #   If the found index in the list is even:
        (      #    Negate the found index
       ë       #   Else (found index is odd):
        ¯      #    Push an empty array
               # (Output the top of the stack implicitly as result)

Beberapa contoh langkah demi langkah:

Input:  Filtered indices:  Path it follows (with actions) and result:

-8      [6]                NOT 1 → neg → even index → negate index: [-6]
-5      [5]                NOT 1 → neg → odd index → push empty array: []
-1      [1,2]              NOT 1 → (remove 1) neg → even remaining index: negate index: [-2]
0       [0]                NOT 1 → even index → negate index: [0]    
1       [1,2]              1 → prepend -1: [-1,1,2]
5       [5]                NOT 1 → non-neg → odd index → Prepend neg index: [-5,5]
8       [6]                NOT 1 → non-neg → even index → (nothing): [6]

Python 2 , 95 92 94 byte

x=input()
i=a=0;b=1
while x*x>=a:
 if 0<a==x:print i
 if[-a,a][i%2]==x:print-i
 a,b=b,a+b;i+=1

Cobalah online!

C # (Visual C # Interactive Compiler) , 144 byte

o=>{int c=0,n=1,i=0,k=Math.Abs(o);for(;c<k;i++,n+=c,c=n-c);return new[]{c>k|o<0?0.1:i,(i>0|o<0)&i%2>0&c==k?-i:0.1,o==1?2:0.1}.Where(p=>p!=0.1);}

Cobalah online!