Твое задание:

Напишите программу или функцию, чтобы проверить, является ли введенное число числом Фибоначчи . Число Фибоначчи - это число, содержащееся в последовательности Фибоначчи.

Последовательность Фибоначчи определяется как: F(n) = F(n - 1) + F(n - 2)

С семенами F(0) = 0и F(1) = 1.

Входные данные:

Неотрицательное целое число от 0 до 1 000 000 000, которое может быть или не быть числом Фибоначчи.

Выход:

Истинное / ложное значение, указывающее, является ли входное значение числом Фибоначчи.

Примеры:

0-->truthy
1-->truthy
2-->truthy
12-->falsy

Подсчет очков:

Это код-гольф , выигрывает меньшее количество байт.

Нейм , 2 байта

f𝕚

Объяснение:

f       Push an infinite fibonacci list
 𝕚      Is the input in that list?

Работает так же, как мой ответ « Это бедро, чтобы быть квадратным» , но использует другой бесконечный список: fдля Фибоначчи.

Попробуй!

JavaScript (ES6), 34 байта

f=(n,x=0,y=1)=>x<n?f(n,y,x+y):x==n

Рекурсивно генерирует последовательность Фибоначчи, пока не найдет элемент, больший или равный входному значению, затем возвращает элемент == входное значение.

Сетчатка , 23 байта

^$|^(^1|(?>\2?)(\1))*1$

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

Вход в унарный, выходы 0или 1.

объяснение

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

Так как мы получаем числа Фибоначчи, добавляя второй к последнему элементу к последнему, различия между ними также являются только числами Фибоначчи. Таким образом, мы должны сопоставить каждый сегмент как сумму двух предыдущих. Суть регулярного выражения заключается в следующем:

(         # This is group 1 which is repeated 0 or more times. On each
          # iteration it matches one Fibonacci number.
  ^1      # On the first iteration, we simply match 1 as the base case.
|         # Afterwards, the ^ can no longer match so the second alternative
          # is used.
  (?>\2?) # If possible, match group 2. This ends up being the Fibonacci
          # number before the last. The reason we need to make this optional
          # is that this group isn't defined yet on the second iteration.
          # The reason we wrap it in an atomic group is to prevent backtracking:
          # if group 2 exists, we *have* to include it in the match, otherwise
          # we would allow smaller increments.
  (\1)    # Finally, match the previous Fibonacci number and store it in
          # group 2 so that it becomes the second-to-last Fibonacci number
          # in the next iteration.
)*

Теперь это выливается сложения чисел Фибоначчи , начиная с 1 , то есть 1, 1, 2, 3, 5, ... . Те дополнения до 1, 2, 4, 7, 12, ... . Т.е. они на единицу меньше, чем числа Фибоначчи, поэтому мы добавляем 1в конце. Единственный случай, который не покрывает это ноль, поэтому у нас есть ^$альтернатива, чтобы покрыть это.

Regex (на ECMAScript), 392 358 328 224 206 165 байтов

Методы, которые необходимо использовать для сопоставления чисел Фибоначчи с регулярным выражением ECMAScript (в унарном формате), далеки от того, как это лучше всего сделать в большинстве других разновидностей регулярных выражений. Отсутствие прямых / вложенных обратных ссылок или рекурсии означает, что невозможно напрямую подсчитать или сохранить промежуточный итог чего-либо. Отсутствие осмотрительности часто затрудняет работу даже при наличии достаточного пространства для работы.

К многим проблемам нужно подходить с совершенно иной точки зрения, и они кажутся неразрешимыми до появления какой-то ключевой идеи. Это заставляет вас создавать более широкую сеть, чтобы определить, какие математические свойства чисел, с которыми вы работаете, могут быть использованы для решения конкретной задачи.

В марте 2014 года это произошло с числами Фибоначчи. Глядя на страницу Википедии, я изначально не мог найти выход, хотя одно конкретное свойство казалось мучительно близким. Затем математик Теукон описал метод, который дал понять, что это возможно сделать, используя это свойство вместе с другим. Он не хотел на самом деле построить регулярное выражение. Его реакция, когда я пошел вперед и сделал это:

Ты сумасшедший! ... Я думал, что вы могли бы сделать это.

Как и в других моих постах по унарным математическим регулярным выражениям в ECMAScript, я дам предупреждение: я настоятельно рекомендую узнать, как решать унарные математические задачи в регулярных выражениях в ECMAScript. Для меня это было увлекательное путешествие, и я не хочу испортить его тем, кто потенциально может попробовать его сами, особенно тем, кто интересуется теорией чисел. См. Этот пост для списка последовательно рекомендованных спойлером проблем, решаемых один за другим.

Так что не читайте дальше, если вы не хотите, чтобы какая-то магия унарного выражения была испорчена для вас . Если вы действительно хотите сами разобраться в этой магии, я настоятельно рекомендую начать с решения некоторых проблем в регулярном выражении ECMAScript, как описано в этом посте, связанном выше.

Задача, с которой я изначально столкнулся: положительное целое число x - это число Фибоначчи тогда и только тогда, когда 5x ² + 4 и / или 5x ² - 4 - идеальный квадрат. Но нет места, чтобы вычислить это в регулярном выражении. Единственное пространство, в котором мы должны работать, это само число. У нас даже недостаточно места, чтобы умножить на 5 или взять квадрат, не говоря уже о обоих.

Идея teukon о том, как ее решить ( изначально размещена здесь ):

Регулярное выражение представлено строкой вида ^x*$, пусть z будет его длиной. Проверьте, является ли z одним из первых нескольких чисел Фибоначчи от руки (до 21 должно подойти). Если это не так:

1. Прочитайте пару чисел a <b, чтобы b было не больше 2a.
   
2. Используйте прогнозные прогнозы для построения ² , ab и b ² .
   
3. Утвердите, что либо 5a ² + 4, либо 5a ² - 4 - идеальный квадрат (поэтому a должно быть F _n-1 для некоторого n).
   
4. Утвердите, что либо 5b ² + 4, либо 5b ² + 4 - идеальный квадрат (поэтому b должно быть F _n ).
   
5. Проверьте, что z = F _{2n + 3} или z = F _{2n + 4} , используя ранее построенные a ² , ab и b ² и тождества:
   
   • F _2n-1 = F _n ² + F _n-1 ²
     
   • F _2n = (2F _n-1 + F _n ) F _n
     

Вкратце: эти тождества позволяют нам уменьшить проблему проверки того, что заданное число - это число Фибоначчи, до проверки того, что пара гораздо меньших чисел - это число Фибоначчи. Маленькая алгебра покажет, что для достаточно большого n (n = 3 должно), F _{2n + 3} > F _n + 5F _n ² + 4, поэтому всегда должно быть достаточно места.

А вот макет алгоритма на C, который я написал в качестве теста перед его реализацией в регулярном выражении.

Так что без дальнейших церемоний, вот регулярное выражение:

^((?=(x*).*(?=x{4}(x{5}(\2{5}))(?=\3*$)\4+$)(|x{4})(?=xx(x*)(\6x?))\5(x(x*))(?=(\8*)\9+$)(?=\8*$\10)\8*(?=(x\2\9+$))(x*)\12)\7\11(\6\11|\12)|x{0,3}|x{5}|x{8}|x{21})$

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

И довольно напечатанная, закомментированная версия:

^(
  (?=
    (x*)                   # \2+1 = potential number for which 5*(\2+1)^2 ± 4
                           # is a perfect square; this is true iff \2+1 is a Fibonacci
                           # number. Outside the surrounding lookahead block, \2+1 is
                           # guaranteed to be the largest number for which this is true
                           # such that \2 + 5*(\2+1)^2 + 4 fits into the main number.
    .*
    (?=                    # tail = (\2+1) * (\2+1) * 5 + 4
      x{4}
      (                    # \3 = (\2+1) * 5
        x{5}
        (\2{5})            # \4 = \2 * 5
      )
      (?=\3*$)
      \4+$
    )
    (|x{4})                # \5 = parity - determined by whether the index of Fibonacci
                           #               number \2+1 is odd or even
    (?=xx (x*)(\6 x?))     # \6 = arithmetic mean of (\2+1) * (\2+1) * 5 and \8 * \8,
                           #      divided by 2
                           # \7 = the other half, including remainder
    \5
    # require that the current tail is a perfect square
    (x(x*))                # \8 = potential square root, which will be the square root
                           #      outside the surrounding lookahead; \9 = \8-1
    (?=(\8*)\9+$)          # \10 = must be zero for \8 to be a valid square root
    (?=\8*$\10)
    \8*
    (?=(x\2\9+$))          # \11 = result of multiplying \8 * (\2+1), where \8 is larger
    (x*)\12                # \12 = \11 / 2; the remainder will always be the same as it
                           #       is in \7, because \8 is odd iff \2+1 is odd
  )
  \7\11
  (
    \6\11
  |
    \12
  )
|
  x{0,3}|x{5}|x{8}|x{21}   # The Fibonacci numbers 0, 1, 2, 3, 5, 8, 21 cannot be handled
                           # by our main algorithm, so match them here; note, as it so
                           # happens the main algorithm does match 13, so that doesn't
                           # need to be handled here.
)$

Алгоритм умножения не объясняется в этих комментариях, но вкратце объясняется в абзаце моего регулярного выражения с многочисленными числами .

Я поддерживал шесть различных версий регулярного выражения Фибоначчи: четыре, которые ускоряют от самой короткой длины до самой быстрой скорости и используют алгоритм, описанный выше, и две другие, которые используют другой, намного более быстрый, но гораздо более длинный алгоритм, который, как я обнаружил, может на самом деле вернуть индекс Фибоначчи как совпадение (объяснение того, что алгоритм здесь выходит за рамки этого поста, но объясняется в оригинальном обсуждении Gist ). Я не думаю, что снова поддержу столько очень похожих версий регулярного выражения, потому что в то время я проводил все свои тесты в PCRE и Perl, но мой движок регулярных выражений достаточно быстрый, так что проблемы со скоростью уже не так важны (и если конкретная конструкция вызывает узкое место, я могу добавить оптимизацию для нее) - хотя я, вероятно, снова поддержу одну самую быструю версию и одну самую короткую версию, если разница в скорости были достаточно большими.

Версия «верните индекс Фибоначчи минус 1 как матч» (не в гольфе):

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

Все версии находятся на github с полной историей коммитов оптимизации гольфа:

регулярное выражение для сопоставления чисел Фибоначчи - короткий, скорость 0.txt (самый короткий, но самый медленный, как в этом посте)
регулярное выражение для сопоставления чисел Фибоначчи - короткий, скорость 1.txt
регулярное выражение для сопоставления чисел Фибоначчи - короткий, скорость 2.txt
регулярное выражение для сопоставление чисел Фибоначчи - короткие, скоростные регулярные
выражения 3.txt для сопоставления чисел Фибоначчи - регулярное выражение fastest.txt
для сопоставления чисел Фибоначчи - возвращение index.txt

Python 3 , 48 байт

lambda n:0in((5*n*n+4)**.5%1,abs(5*n*n-4)**.5%1)

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

Python 2, 48 44 байта

f=lambda n,a=0,b=1:n>a and f(n,b,a+b)or n==a

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

_{Спасибо Джонатану Аллану за сохранение 4 байта}

05AB1E , 8 7 байт

>ÅF¹å¹m

Объяснение:

>ÅF       # Generate Fibbonacci numbers up to n+1
   ¹å     # 0 if original isn't in the list, 1 if it is
     ¹m   # 0**0 = 1 if input was 0 (hotfix for 0).
          # or 0**n if not fibb / 1**n if it is a fibb.

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

-1 спасибо Джонатану Аллану за обходной путь числа 0-не-Фибоначчи.

Perl 6 , 23 байта

{$_∈(0,1,*+*...*>$_)}

Серьезно , 3 байта

,fu

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

Возвращает индекс +1 в списке чисел Фибоначчи, если верно, в противном случае возвращает ложь.

Объяснение:

,fu
,   read input
 f  0-indexed index of that number in the fibonacci sequence (-1 if not in the sequence)
  u increment. (Makes the -1 value falsy and the 0-value truthy)

Желе ,  8 7  6 байт

-r‘ÆḞċ

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

Как?

-r‘ÆḞċ - Link: non negative number, n
-      - literal -1      = -1
 r     - inclusive range = [-1,0,1,2,3,4,5,...,n]
  ‘    - increment n     = [ 0,1,2,3,4,5,6,...,n+1]
   ÆḞ  - Fibonacci       = [ 0,1,1,2,3,5,8,...,fib(n+1)]
     ċ - count occurrences of n (1 if n is a Fibonacci number, 0 otherwise)

Примечания:

• ‘требуется увеличение, так , чтобы это работало для 2 и 3 , поскольку они являются 3- ^м и 4- ^м числами Фибоначчи - за пределами 3 все числа Фибоначчи больше, чем их индекс.
• -нужен (а не только ‘R) , так что это работает для 0 , начиная с 0 является 0 - ^го числа Фибоначчи;

ZX81 BASIC 180 151 100 ~ 94 токенов BASIC

Благодаря Moggy на форумах SinclairZXWorld, есть гораздо более аккуратное решение, которое экономит больше байтов.

 1 INPUT I
 2 FOR F=NOT PI TO VAL "1E9"
 3 LET R=INT (VAL ".5"+(((SQR VAL "5"+SGN PI)/VAL "2")**I)/SQR VAL "5")
 4 IF R>=I THEN PRINT F=R
 5 IF R<I THEN NEXT F

Это выведет 1, если введено число Фибоначчи, или ноль, если нет. Хотя это экономит байты, это намного медленнее, чем в старых решениях ниже. Для скорости (но больше ОСНОВНЫХ байтов) удалите VALобертки вокруг строковых литералов. Вот старые (er) решения с некоторыми пояснениями:

 1 INPUT A$
 2 LET A=SGN PI
 3 LET B=A
 4 LET F=VAL A$
 5 IF F>SGN PI THEN FOR I=NOT PI TO VAL "1E9"
 6 LET C=A+B
 7 LET A=B
 8 LET B=C
 9 IF B>=F THEN GOTO CODE "£"
10 IF F THEN NEXT I
12 PRINT STR$(SGN PI*(B=F OR F<=SGN PI)) AND F>=NOT PI;"0" AND F<NOT PI

Вышеуказанные поправки экономят дополнительные байты BASIC для сведения IFоператоров в один PRINTв строке 12; другие байты были сохранены с использованием VALключевого слова и, и с использованием GOTO CODE "£", которое в наборе символов ZX81 равно 12. Строки сохраняют больше байтов по числам, так как все числовые значения хранятся как числа с плавающей запятой, поэтому занимают больше места в стеке VAR.

C #, 109 байт

bool f(int n){int[]i=new[]{0,1,0};while(i[0]<n||i[1]<n){i[i[2]%2]=i[0]+i[1];i[2]++;}return n==i[0]||n==i[1];}

Определенно можно улучшить, но у меня не было времени.

> <> , 21 19 + 3 = 24 22 байта

i1\{=n;
?!\:@+:{:}(

Ожидается, что ввод будет в стеке при запуске программы, поэтому +3 байта для -vфлага.

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

Это работает путем генерации чисел Фибоначчи до тех пор, пока они не будут больше или равны входному номеру, а затем проверка последнего сгенерированного числа на равенство с входным. Выходы1 если это было число Фибоначчи, в 0противном случае.

Для того , чтобы 0правильно обрабатывались, семя -1 1- первое число , генерируемое будет , 0а не1 .

Спасибо @cole за указание на то, что iможно использовать для-1 в стек, когда STDIN пуст. Очень умно!

Предыдущая версия:

01-1\{=n;
}(?!\:@+:{:

Mathematica, 37 байт

!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&

-4 байта от @ngenisis

MATL (16 байт)

2^5*4-t8+hX^tk=s

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

Не самое удачное решение, но хотелось использовать прямой метод проверки, является ли "5 * x ^ 2 +/- 4" идеальным квадратом .

Объяснение:

2^5*    % 5 times the input squared
4-      % push the above minus 4
t8+     % push the above plus 8 (+4 overall)
hX^     % concatenate them into an array and then take the sqrt().
tk      % push a copy of the array that is rounded using floor().
=       % test if the sqrt's were already integers
s       % sum the results, returns 0 if neither was a perfect square.

Примечание:

В случае «0» он возвращает «2», потому что и 4, и -4 являются идеальными квадратами, то же самое с 1, который выдает «1 1». Считайте любой ненулевой вывод «правдивым», а 0 - «ложным».

Пари / ГП , 32 байта

n->!prod(x=0,n+1,fibonacci(x)-n)

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

PHP , 44 байта

for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;

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

PHP , 58 байт

for($x=0,$y=1;$x<$argn;$x=$y,$y=$t)$t=$x+$y;echo$x==$argn;

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

Java, 72 69 68 63 59 55 50 49 байт

n->{int a=0,b=1;for(;a<n;a=b-a)b+=a;return a==n;}

Попробуйте сами!

Альтернатива (еще 49 байтов)

n->{int a=0,b=1;for(;a<n;b=a+(a=b));return a==n;}

Не очень оригинально: это простая и базовая итерационная версия.

Это работает для чисел до 1,836,311,903 (47 число Фибоначчи) включены. Кроме того, результат не определен (включая потенциальный бесконечный цикл).

Спасибо Кевину Круйссену и Дэвиду Конраду за помощь в игре в гольф :)

C # (.NET Core) , 51 байт

bool f(int n,int a=0,int b=1)=>a<n?f(n,b,a+b):a==n;

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

-6 байт благодаря @Oliver!

Это решение использует довольно простую рекурсивную функцию.

• Переменная n- это число для проверки.
• Переменные aи b2 самые последние числа в последовательности.
• Проверяет, меньше ли первое из двух последних чисел, чем введено. В этом случае выполняется рекурсивный вызов следующих номеров в серии.
• В противном случае проверьте, равно ли первое число входному значению, и верните результат.

Ссылка TIO демонстрирует эту работу для 1134903170, которая превышает максимальное значение, требуемое для задачи.

Алхимик , 205 134 байта

^{Большое спасибо только ASCII за довольно умное объединение состояний, экономя 71 байт !!}

_->In_x+c+u
u+b->u+a+d
u+0b->v
v+c->v+b+d
v+0c->w
w+a+x->w+y
w+0a+0x->Out_"1"
w+a+0x->Out_"0"
w+0a+x+y->w+2x
w+0a+0y+d->w+c
w+0d+0a->u

Попробуйте онлайн или подтвердите пакетно!

Ungolfed

# read input, initialize (c = 1)
_ -> In_x + c + s0

# a,d <- b
s0 +  b -> s0 + a + d
s0 + 0b -> s1

# b,d <- c
s1 +  c -> s1 + b + d
s1 + 0c -> s2

s2 +  a +  x -> s2 + y            # y <- min(a,x)
s2 + 0a + 0x -> Out_"1"           # if (a == x): was Fibonacci
s2 +  a + 0x -> Out_"0"           # if (a >  x): stop (we exceeded target)
s2 + 0a +  x +  y -> s2 + 2x      # if (a <  x): x += a (since y = a) / restore x
s2 + 0a      + 0y +  d -> s2 + c  # once that's done; c <- d
s2 + 0a           + 0d->s0        # and finally loop

Желе , 5 байт

ȷḶÆḞi

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

Возвращает 0 для не-числа Фибоначчи и 1-индексированное положение числа в последовательности Фибоначчи для чисел Фибоначчи.

Объяснение:

ȷḶÆḞi
ȷ        The literal number 1000
 Ḷ       Range [0,1,...,999]
  ÆḞ     Get the ith Fib number; vectorizes [1,1,2,3,5,...,<1000th Fib number>]
    i    Get the first index of element in list, or 0 if not found

Дьялог АПЛ, 17 байт

0∊1|.5*⍨4 ¯4+5××⍨

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

R, 43 40 байт

pryr::f(x%in%DescTools::Fibonacci(0:45))  

pryr::f создает функцию:

function (x) 
x %in% DescTools::Fibonacci(0:45)

Используется DescTools::Fibonacciдля создания первых x+1чисел Фибоначчи и проверок на включение. x+1потому что третий фибнум 2, и этого было бы недостаточно, чтобы проверить наличие 3.

К счастью Desctools::Fibonacci(0)=0, это хорошая халява.

-3 байта благодаря MickyT

Haskell , 31 байт

f=0:scanl(+)1f
(`elem`take 45f)

Попробуйте онлайн! Это использует тот факт, что входные данные будут находиться в диапазоне от 0 до 1 000 000 000, поэтому нам нужно проверить только первые 45 чисел Фибоначчи. f=0:scanl(+)1fгенерирует бесконечный список чисел Фибоначчи, take 45fсписок первых 45 чисел Фибоначчи иelem проверяет, есть ли входные данные в этом списке.

Неограниченная версия: 36 байт

f=0:scanl(+)1f
g n=n`elem`take(n+3)f

Попробуйте онлайн! Для любого n, взяв первые n+3числа Фибоначчи, мы гарантируем, что nони будут в этом списке, если это число Фибоначчи.

Обратите внимание, что этот подход невероятно неэффективен для больших чисел, которые не являются числами Фибоначчи, потому что все n+3числа Фибоначчи должны быть вычислены.

Javascript (ES6 без оператора **), 44 байта

f=(x,c=x*(Math.sqrt(5)-1)/2%1)=>x*(c-c*c)<.5

Полагается на соотношение между последовательными числами Фибоначчи, приближающимися к золотому сечению. Значение c - это дробная часть входных данных, деленная на золотое сечение - если входное значение равно Фибоначчи, то оно будет очень близко к 1, а значение c-c² будет очень маленьким.

Не так коротко, как некоторые другие ответы JS, но выполняется за O (1) раз.

Юлия 0,4 , 29 байт

!m=in(0,sqrt(5*m*m+[4,-4])%1)

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

Если это не то, как вы ответите Джулии, дайте мне знать. Я не уверен, как работает ввод на TIO.

R, 32 31 байт

Принимает ввод из стандартного ввода, возвращает TRUEили, FALSEв зависимости от ситуации.

any(!(5*scan()^2+-1:1*4)^.5%%1)

Common Lisp, 61 54 байта

(defun f(x)(do((a 0 b)(b 1(+ a b)))((>= a x)(= a x))))

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

Уменьшение размера относительно предыдущей версии:

(defun f(x)(do((a 0 b)(b 1 c)(c 1(+ b c)))((>= a x)(= a x))))

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

Mathematica, 33 байта

AtomQ@*InverseFunction[Fibonacci]

JS (ES6), 57 байт

n=>(y=y=>((5*(n**2)+y)**0.5),~~y(4)==y(4)|~~y(-4)==y(-4))

Использует метод carusocomputing . Много гольф, чем мой другой ответ .

Ungolfed

n=>{
    y=y=>((5*(n**2)+y)**0.5);//carusocomputing's method in a function
    return ~~y(4) === y(4) || ~~y(-4) === y(-4);//~~x === Math.floor(x)
}