Я число Фибоначчи?

49

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

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

Последовательность Фибоначчи определяется как: 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
Используемый язык программирования поддерживает только числа до 9999 (Geometry Dash). Это нормально, если я предполагаю, что он поддерживает цифры до 1000000, теоретически?
MilkyWay90

Ответы:

36

Нейм , 2 байта

f𝕚

Объяснение:

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

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

Попробуй!

Okx
источник
1
Вау! Впечатляющий балл.
Грифон - Восстановить Монику
2
Это здорово, но не 2 байта. В UTF-8 он представлен как «66 F0 9D 95 9A»
sm4rk0
10
@ sm4rk0 Отлично, но ты не прав. Neim использует пользовательскую кодовую страницу , так что байтовое представление этого66 D5
Okx
Разве этот цикл не существует вечно, если входных данных нет в списке? Если так, это считается как ложь?
Энрико Борба
@EnricoBorba Нейм знает, что n-й элемент в этом бесконечном списке всегда будет равен или меньше, чем n + 1-й элемент в списке. Следовательно, он может поймать себя и не будет работать вечно. Вы пробовали программу это? : P
Okx
18

JavaScript (ES6), 34 байта

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

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

ETHproductions
источник
NB: наивный рекурсивный расчет последовательности Фибоначчи: O (Fib (n)) - приблизительно O (1.6 ^ n)
Альнитак,
f = n => n? n> 2? f (n-1) + f (n-2): 1: 0 28 байт
jackkav
@jackkav Спасибо, но задача состоит в том, чтобы определить , если вход является числом Фибоначчи.
ETHproductions
12

Сетчатка , 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в конце. Единственный случай, который не покрывает это ноль, поэтому у нас есть ^$альтернатива, чтобы покрыть это.

Мартин Эндер
источник
2
Очень элегантный! Для полноты ^$|^(^1|\2?+(\1))*1$
картины
1
@Deadcode Я очень скучаю по ним в .NET;)
Мартин Эндер
Сохраните 1 байт, удалив ненужную секунду ^.
Нил
12

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

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

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

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

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

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

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

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

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

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

  1. Прочитайте пару чисел a <b, чтобы b было не больше 2a.
  2. Используйте прогнозные прогнозы для построения 2 , ab и b 2 .
  3. Утвердите, что либо 5a 2 + 4, либо 5a 2 - 4 - идеальный квадрат (поэтому a должно быть F n-1 для некоторого n).
  4. Утвердите, что либо 5b 2 + 4, либо 5b 2 + 4 - идеальный квадрат (поэтому b должно быть F n ).
  5. Проверьте, что z = F 2n + 3 или z = F 2n + 4 , используя ранее построенные a 2 , ab и b 2 и тождества:
    • F 2n-1 = F n 2 + F n-1 2
    • F 2n = (2F n-1 + F n ) F n
Вкратце: эти тождества позволяют нам уменьшить проблему проверки того, что заданное число - это число Фибоначчи, до проверки того, что пара гораздо меньших чисел - это число Фибоначчи. Маленькая алгебра покажет, что для достаточно большого n (n = 3 должно), F 2n + 3 > F n + 5F n 2 + 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

Deadcode
источник
9

Python 3 , 48 байт

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

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

Деннис
источник
1
Будучи Python, он не должен работать при достаточных ресурсах для произвольно больших входов?
Джонатан Аллан
2
У меня всегда было впечатление, что мы можем использовать любой алгоритм, какой захотим, до тех пор, пока он работает на практике, если вычисления соответствуют типу данных и теоретически дают бесконечную точность. Конечно, использование only только intустановит планку выше (все еще не произвольно большой), но мы также не заставляем ответы C использовать 64-битные целые числа (или 128-битные с gcc). В любом случае, разрешено использовать один и тот же алгоритм на одном языке, но не на другом, кажется бессмысленным.
Деннис
Алгоритмическое представление имеет смысл (я всегда думал, что именно входная область диктовала критерии «соответствия типу данных»). Единственное, на что нужно обратить внимание - это серая область между идеей алгоритма и его реализацией. Здесь можно проверить, являются ли одно из целых чисел квадратными, без приведения к числам с плавающей точкой. Я предполагаю, что внутреннее приведение в качестве побочного эффекта приемлемо, если оно является частью законного, работающего алгоритма (... и я почти уверен, что алгоритм, который полагался на приведение, не был бы приемлемым).
Джонатан Аллан
@JonathanAllan Поскольку максимальное значение для обработки - 1e9, я не думаю, что произвольно большие входные данные будут проблемой.
JAD
1
@JarkoDubbeldam да, эта деталь фактически изменилась после того, как был сделан мой комментарий.
Джонатан Аллан
7

Python 2, 48 44 байта

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

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

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

mbomb007
источник
Это может быть 47 байтов, если истинные значения могут быть Falseи ложными значениями True: TIO !
г-н Xcoder
Можно также использовать n-aвместо n==aи иметь -1 и 0 в качестве возвращаемых значений.
Волшебная Урна Осьминога
@carusocomputing У меня было это в моей истории редактирования, но это не работает, потому что для больших тестовых значений вы могли бы иметь -101или какой-то другой результат вместо -1.
mbomb007
@ Mr.Xcoder Вы действительно думаете, что сохранение 1 байта стоит здравомыслия каждого?
frarugi87
1
@ frarugi87 Сохранение байта всегда стоит
Mr. Xcoder,
7

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-не-Фибоначчи.

Урна волшебного осьминога
источник
На самом деле, не будет обновляться до 6 байтов. Не могу поверить, что НЕТ способа добавить 0 в список до 3 байтов.
Волшебная урна осьминога
@JonathanAllan «функция генерации фиббоначи» в 05AB1E не содержит 0.
Урна магического осьминога
@JonathanAllan Теперь я понимаю, хорошая идея. Мне понадобилась минутка, чтобы понять, что на самом деле там происходит.
Волшебная Урна Осьминога
Разве этого недостаточно для генерации upto n(сохранения байта), как ÅFэто включено и ¹åприведет в 0любом случае для n=0?
Эминья
0AF = []. 1AF = [1,1]. Так что, видимо, нет.
Волшебная Урна Осьминога
5

Perl 6 , 23 байта

{$_∈(0,1,*+*...*>$_)}
Шон
источник
{(0,1,*+*...^*>$_).tail==$_}было то, что я собирался изначально опубликовать. Возможно, я наконец-то нашел операторы Set .
Брэд Гилберт b2gills
5

Серьезно , 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)
Товарищ Спаркл Пони
источник
9
Серьезно грубо ^^
Джонатан Аллан
5

Желе ,  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 - го числа Фибоначчи;
Джонатан Аллан
источник
Хм, это слишком похоже на мой ответ ...
Эрик Outgolfer
О, я отдал свой гольф твоему, кроме моих работ 3:)
Джонатан Аллан
Ой ой ... Фибоначчи странный. (кстати удалил мой ответ тогда, если ты так говоришь)
Эрик Outgolfer
Ты уверен насчет последней записки? Когда я запускаю атом Фибоначчи в списке, начиная с 0, в вывод включается 0.
разброс
1
По-видимому, это не имеет отношения к формулировке задачи, но если вы используете счетный атом с 1 в качестве аргумента в списке чисел Фибоначчи, результатом будет 2 (а не 1).
FryAmTheEggman
5

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.

введите описание изображения здесь

Шон Бебберс
источник
На самом деле, я мог бы сохранить еще 6 байтов BASIC, удалив строку 6 и изменив строку 5 на 5 IF R<F THEN NEXT I- мой плохой!
Шон Бебберс
4

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

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

Кайто Кид
источник
Добро пожаловать в PPCG!
Мартин Эндер
1
Я написал свой ответ только для того, чтобы понять, что он такой же, как ваш. Вы можете использовать лямбда-выражения и простые переменные, чтобы получить это: n=>{int a=0,b=1,c=0;while(a<n&b<n)if(++c%2>0)a=a+b;else b=a+b;return a==n|b==n;}(всего 80 байт). Попробуйте онлайн!
Чарли
1
@CarlosAlejo Сохраните еще 2 байта для этого с a+=bвместо a=a+bи b+=aвместо b=a+b.
TheLethalCoder
4

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

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

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

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

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

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

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

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

01-1\{=n;
}(?!\:@+:{:
Sok
источник
Теперь я чувствую себя глупо, тратя байты, постоянно проверяя каждое сгенерированное число по пути. Красиво сделано!
Эминья
1
22 байта , используя iвместо 01-.
Коул
@cole конечно, используя , iкак , -1когда нет входа STDIN, я бы не считал , что. Красиво сделано!
Сок
3

Mathematica, 37 байт

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

-4 байта от @ngenisis

J42161217
источник
Fibonacci[0]дает 0, так что вы можете сохранить 4байты, включив 0в Tableдиапазон. Вы можете сохранить еще один байт, используя инфиксную запись для Table:!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&
ngenisis
3

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 - «ложным».

DrQuarius
источник
3

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;

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

Йорг Хюльсерманн
источник
2
Golfed больше: for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;.
user63956
@ user63956 Спасибо за усилия по обучению с назначением переменных цепочки
Jörg Hülsermann
3

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 число Фибоначчи) включены. Кроме того, результат не определен (включая потенциальный бесконечный цикл).

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

Оливье Грегуар
источник
1
Хороший подход. Кстати, вы можете сыграть в байт, изменив n==0на n<1. В вопросе говорится: « Неотрицательное целое число от 0 до 1 000 000 000 ».
Кевин Круйссен
1
@KevinCruijssen Я играл в гольф не 1, а 5 байтов с этим предложением! :-P Спасибо, я этого не заметил.
Оливье Грегуар
2
Вам не нужна временная переменная для последовательности Фибоначчи. Вы можете рассчитать последовательные пары сb+=a;a=b-a;
Дэвид Конрад
1
Ты занимаешься черной магией, @DavidConrad! Я говорю вам! Черная магия! :)
Оливье Грегуар
3

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, которая превышает максимальное значение, требуемое для задачи.

Dana
источник
Приятно видеть решения C # в последнее время :) - Я думаю, что вы можете просто проверить, если a<nдля 51 байтов
Оливер
Спасибо! И хороший совет :)
Дана
3

Алхимик , 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
ბიმო
источник
Wip: tio.run/##JcpBCsMgFATQvcfIdhCsB8i@qx5BjD/…
только для ASCII
139 . Вы можете удалить некоторые 0проверки на меньшее количество байтов за счет недетерминизма
только ASCII
129
Только для ASCII
@ Только для ASCII: Это очень мило! Сбой на 0, но без добавления b-atom при инициализации исправляет его (и сохраняет 2 байта): D Спасибо
ბიმო
2

Желе , 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
разброс
источник
Не работает на 0.
Okx
@ComradeSparklePony Вы уверены? Это подходит для меня.
разброс
1
Не работает на 0 или что - нибудь большее , чем 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875.
Эрик Outgolfer
1
@ Mr.Xcoder По общему мнению, вы должны уметь обрабатывать то, что поддерживает ваш естественный тип данных, а Jelly поддерживает целые числа произвольной точности.
Эрик Outgolfer
1
Тем не менее не работает ни на что над 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626.
Эрик Outgolfer
2

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

JAD
источник
-1:x+1сэкономит вам байт, но 0:45сэкономит вам три и покроет необходимый диапазон
MickyT
@ MickyT О, я, должно быть, пропустил требуемую спецификацию диапазона. Спасибо :)
JAD
Альтернативный подход, только 36 байт: pryr::f(any(!(5*n^2+c(-4,4))^.5%%1)).
rturnbull
Я получил его до 32 байтов, смотрите здесь .
rturnbull
Я не очень знаком с правилами гольф-кода - имеет ли смысл неосновные пакеты? Я мог бы написать произвольный код R в пакет, установить его и запустить так же, как вы запускали функцию изpryr .
mb7744
2

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числа Фибоначчи должны быть вычислены.

Laikoni
источник
2

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) раз.

HP Williams
источник
Вы уверены, что это точно?
Петер говорит восстановить Монику
Не работает для числа Фибоначчи 16558014
Черная Сова Кай
2

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

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

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


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

Урна волшебного осьминога
источник
1
Вы должны сделать это регулярной функцией (считая !m=) или лямбда (считая m->). Что еще более важно, это терпит неудачу для 0 как есть.
Деннис
2

R, 32 31 байт

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

any(!(5*scan()^2+-1:1*4)^.5%%1)
rturnbull
источник
2

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

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

Renzo
источник
1

Mathematica, 33 байта

AtomQ@*InverseFunction[Fibonacci]
J42161217
источник
Вы можете сохранить пару байтов с @*(и затем отбросить финал @#&)
Мартин Эндер
1

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

источник