Prawdopodobnie słyszałeś o liczbach Fibonacciego. Wiesz, ta liczba całkowita, która zaczyna się od 1, 1, a następnie każda nowa liczba jest sumą dwóch ostatnich?

1 1 2 3 5 8 13...

I tak dalej. Wyzwania dotyczące liczb Fibonacciego są tutaj dość popularne . Ale kto mówi, że liczby Fibonacciego muszą zaczynać 1, 1? Dlaczego nie mogli zacząć 0, 1? W porządku, zdefiniujmy je na nowo od 0:

0 1 1 2 3 5 8 13...

Ale ... Nie musimy się na tym kończyć! Jeśli możemy dodać dwie ostatnie liczby, aby uzyskać następną, możemy również odjąć pierwszą liczbę od drugiej liczby, aby wstawić nową liczbę. Więc może zacząć od 1, 0:

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

Możemy nawet skończyć z negatywami:

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

Ta seria również trwa wiecznie. Myślę, że to ciekawe, jak to się w pewnym sensie odzwierciedla jak zwykłe liczby Fibonacciego, tylko z każdą inną liczbą ujemną:

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

Nazwijmy tę serię „rozszerzoną liczbą Fibonacciego” lub EFN . Ponieważ tak naprawdę nie ma oczywistej liczby ujemnej na początek tej serii, powiemy, że 0 pokazuje się na 0 , zwykłe liczby Fibonacciego rozciągają się na indeksy dodatnie, a ujemne (pół-ujemne?) Liczby Fibonacciego rozciągają się w indeksach ujemnych, tak:

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

Prowadzi to do dzisiejszego wyzwania:

Biorąc pod uwagę liczbę całkowitą N , zwraca każdy indeks, przy którym N pojawia się w serii EFN .

Kilka losowych obserwacji tego zadania:

• 1 pojawia się kilka razy w europejskiej sieci prognozowania niż jakikolwiek inny numer: [-1, 1, 2]. Żadna liczba nie pojawi się w więcej niż 3 miejscach.

• Każda liczba Fibonacciego> 1 pojawi się raz (3, 8, 21 itd.) Lub dwa razy (2, 5, 13 itd.)

Wyjaśnienie reguł:

• Jeśli abs(N)nie jest liczbą Fibonacciego, nigdy nie pojawi się w serii EFN , więc nie możesz nic wypisać / pustej kolekcji, jeśli to możliwe, lub jeśli nie jest to możliwe w twoim języku, możesz wygenerować pewną stałą wartość nienumeryczną.
• Jeśli N pojawia się w wielu miejscach w EFN , dane wyjściowe nie muszą być sortowane. Chociaż każdy indeks musi pojawić się dokładnie raz.
• Chociaż większość wyzwań sekwencyjnych pozwala wybrać, czy chcesz używać indeksowania opartego na 1, czy 0, wyzwanie to musi wykorzystywać opisaną indeksację (gdzie 0 pojawia się przy 0).
• Możesz wziąć we / wy w dowolnym standardowym formacie.

Przypadki testowe

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

I niektóre większe przypadki testowe:

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

Jak zwykle, najkrótsza odpowiedź w bajtach wygrywa!

Haskell , 78 bajtów

4 bajty zapisane dzięki nim

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]}

Wypróbuj online!

Najpierw musimy założyć (#), (#)przyjmuje dwa parametry, ai b, i zwraca listę zaczynając aa następnie b#(a-b). To tworzy nieskończoną listę, ale ponieważ Haskell jest leniwy, nie musimy się martwić, że zapętli się na zawsze. To zasadniczo działa wstecz, tworząc sekwencję Fibonacciego przed określoną parą. Na przykład (0#1)byłaby lista wszystkich liczb Fibonacciego z indeksem ujemnym.

Stąd robimy f. fprzyjmuje argument, aktóry jest liczbą, którą próbujemy znaleźć w sekwencji. W tym celu używamy donotacji, aby wykonać analizę listy. Zaczynamy od pierwszych a*a+1elementów listy 0#1¹ . Ponieważ funkcja a*a+1rośnie szybciej niż odwrotność sekwencji Fibonacciego, możemy być pewni, że jeśli sprawdzimy w tym zakresie, znajdziemy wszystkie wyniki. Uniemożliwia nam to wyszukiwanie nieskończonej listy. Następnie dla każdej wartości xi indeksu i, jeśli x==aznaleźliśmy aw ujemnej połowie sekwencji, więc wrócimy -i, a jeśli również abs x==awrócimy, iponieważ wartość bezwzględna połowy ujemnej jest połową dodatnią, więc znaleźliśmy ją.

Ponieważ to sprawia, że ​​lista [0,0]na 0stałe kodujemy poprawne wyjście dla tego.

^{1: Ta sztuczka pochodzi od „czystej” odpowiedzi . Te same aplies tutaj SpeedUp jak tam wymienić a*a+1z abs a+1zaoszczędzić sporo czasu.}

Czysty , 132 120 109 bajtów

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]

Wypróbuj online!

g :: Int -> Intjest funkcją Fibonacciego.
? :: Int -> [Int]tylko indeksy do elementów europejskiej sieci prognozowania promieniu k^2+1od 0.

Aby uzyskać wersję, która działa w rozsądnym czasie, zmień k*k+1na abs k+1.

Galaretka , 11 bajtów

A‘ŒRÆḞẹ_A_2

Wypróbuj online!

JavaScript (ES6),  94  93 bajty

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

Wypróbuj online!

$-0$$n=0$

APL (Dyalog Classic) , 52 50 bajtów

Wymaga ⎕IO←0

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

Wypróbuj online!

Retina 0.8.2 , 104 102 bajtów

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

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

Wypróbuj online! Wyjaśnienie:

[1-9].*
$*

Konwertuj na unary, chyba że wartość wejściowa wynosi zero

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

Oblicz indeks Fibonacciego wartości bezwzględnej, ale jeśli liczba nie jest liczbą Fibonacciego, usuń ją, chyba że była równa zero. To używa wyrażenia regularnego @ Fibonacciego @ MartinEndera.

-1(11)+$

Usuń liczby ujemne, których wartości bezwzględne są nieparzystymi liczbami Fibonacciego.

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

Dodaj ujemne wskaźniki dla nieparzystych dodatnich liczb Fibonacciego.

1+
$.&

Konwertuj na dziesiętny.

^2$
-1,1,2

Dodaj dodatkowe wskaźniki dla 1.

Właściwie 34 bajty

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

Brutalna siła ratuje dzień

Wyjaśnienie:

;╗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)

Wypróbuj online!

Python 3 , 92 bajty

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}

Wypróbuj online!

Zwraca zestaw indeksów.

Python 2 , 87 85 bajtów

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[]

Wypróbuj online!

05AB1E , 36 bajtów

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

Musi być lepsze podejście 0.

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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)

Kilka przykładów krok po kroku:

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 bajty

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

Wypróbuj online!

C # (interaktywny kompilator Visual C #) , 144 bajty

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);}

Wypróbuj online!