Вы, наверное, слышали о числах Фибоначчи. Вы знаете, что целочисленная последовательность начинается с 1, 1, а затем каждое новое число является суммой двух последних?

1 1 2 3 5 8 13...

И так далее. Проблемы с числами Фибоначчи довольно популярны здесь . Но кто сказал, что числа Фибоначчи должны начинаться с 1, 1? Почему они не могли начать с 0, 1? Хорошо, давайте переопределим их, чтобы начать с 0:

0 1 1 2 3 5 8 13...

Но ... Мы не должны останавливаться на достигнутом! Если мы можем добавить последние два числа, чтобы получить следующее, мы могли бы также вычесть первое число из второго числа, чтобы добавить новый номер. Так что это может начаться с 1, 0:

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

Мы можем даже получить негативы:

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

И эта серия также продолжается вечно. Я думаю, что интересно, как это в конечном итоге отражает обычные числа Фибоначчи, просто с каждым другим числом, сделанным отрицательным:

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

Давайте назовем эту серию «Расширенное число Фибоначчи», или EFN . Поскольку на самом деле не существует очевидного отрицательного числа, с которого начинается этот ряд, мы скажем, что 0 отображается в 0 , регулярные числа Фибоначчи распространяются на положительные индексы, а отрицательные (полуотрицательные?) Числа Фибоначчи расширяются по отрицательным показателям, вот так:

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

Это приводит к сегодняшнему вызову:

Учитывая целое число N , вернуть каждый индекс, по которому N появляется в ряду EFN .

Несколько случайных наблюдений по этой задаче:

• 1 появляется несколько раз в EFN , чем любое другое число: [-1, 1, 2]. Ни один номер не появится более чем в 3 местах.

• Каждое число Фибоначчи> 1 будет отображаться либо один раз (3, 8, 21 и т. Д.), Либо дважды (2, 5, 13 и т. Д.)

Пояснения к правилу:

• Если abs(N)это не число Фибоначчи, оно никогда не появится в серии EFN , поэтому вы должны вывести ничего / пустую коллекцию, если это возможно, или, если это невозможно на вашем языке, вы можете вывести некоторое постоянное нечисловое значение.
• Если N появляется в нескольких местах в EFN , ваш вывод не нужно сортировать. Хотя каждый индекс должен появляться ровно один раз.
• Хотя большинство задач последовательности позволяют вам выбрать, хотите ли вы использовать индексацию на основе 1 или 0, для этой задачи необходимо использовать описанную индексацию (где 0 отображается в 0).
• Вы можете осуществлять ввод-вывод в любом стандартном формате.

Тестовые случаи

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

И несколько больших тестовых случаев:

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

Как обычно, кратчайший ответ в байтах побеждает!

Haskell , 78 байт

4 байта сохранены благодаря 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]}

Попробуйте онлайн!

Сначала мы настраиваем (#), (#)принимаем два параметра, aи b, и возвращаем список, начинающийся с aи после b#(a-b). Это создает бесконечный список, но поскольку Haskell ленив, нам не нужно беспокоиться о его зацикливании навсегда. По сути, это работает в обратном направлении, создавая последовательность Фибоначчи перед определенной парой. Например, (0#1)будет список всех чисел Фибоначчи с отрицательным индексом.

Отсюда мы делаем f. fпринимает аргумент, aкоторый является числом, которое мы пытаемся найти в последовательности. Здесь мы используем doнотацию для понимания списка. Начнем с того, что возьмем первые a*a+1элементы списка 0#1¹ . Поскольку функция a*a+1растет быстрее, чем обратная последовательность Фибоначчи, мы можем быть уверены, что, если мы проверим в этой границе, мы найдем все результаты. Это мешает нам искать бесконечный список. Затем для каждого значения xи индекса i, если x==aмы нашли aотрицательную половину последовательности, мы возвращаемся -i, и если abs x==aмы также вернемся, iпотому что абсолютное значение отрицательной половины - это положительная половина, поэтому мы нашли ее там.

Так как это делает список [0,0]для 0нас жёстко правильный выход для того.

^{1: Этот трюк взят из «чистого» чистого ответа . Та же SpeedUp aplies здесь , как там, замените a*a+1с , abs a+1чтобы сэкономить много времени.}

Чисто , 132 120 109 байт

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]

Попробуйте онлайн!

g :: Int -> Intявляется функцией Фибоначчи.
? :: Int -> [Int]только индексы в элементах EFN в пределах k^2+1от 0.

Для версии, которая выполняется в нормальное время, измените k*k+1на abs k+1.

Желе , 11 байт

A‘ŒRÆḞẹ_A_2

Попробуйте онлайн!

JavaScript (ES6),  94  93 байта

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

Попробуйте онлайн!

$-0$$n=0$

APL (Dyalog Classic) , 52 50 байт

требует ⎕IO←0

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

Попробуйте онлайн!

Сетчатка 0.8.2 , 104 102 байта

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

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

Попробуйте онлайн! Объяснение:

[1-9].*
$*

Преобразовать в унарный, если вход не равен нулю.

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

Вычислите индекс Фибоначчи по абсолютному значению, но если число не является числом Фибоначчи, то удалите его, если оно не равно нулю. Для этого используется регулярное выражение Фибоначчи @ MartinEnder.

-1(11)+$

Удалите отрицательные числа, абсолютные значения которых являются нечетными числами Фибоначчи.

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

Добавьте отрицательные индексы для нечетных положительных чисел Фибоначчи.

1+
$.&

Преобразовать в десятичную.

^2$
-1,1,2

Добавьте дополнительные индексы для 1.

На самом деле , 34 байта

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

Грубая сила спасает день

Объяснение:

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

Попробуйте онлайн!

Python 3 , 92 байта

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}

Попробуйте онлайн!

Возвращает набор индексов.

Python 2 , 87 85 байт

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

Попробуйте онлайн!

05AB1E , 36 байт

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

Должен быть лучший подход ..>.> Есть шесть (или семь, если мы включим 0) различных сценариев для этой задачи, и это убивает меня ..

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

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)

Несколько пошаговых примеров:

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 байта

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

Попробуйте онлайн!

C # (интерактивный компилятор Visual C #) , 144 байта

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

Попробуйте онлайн!