Sua tarefa:

Escreva um programa ou função para verificar se um número inserido é um número de Fibonacci . Um número de Fibonacci é um número contido na sequência de Fibonacci.

A sequência de Fibonacci é definida como: F(n) = F(n - 1) + F(n - 2)

Com as sementes sendo F(0) = 0e F(1) = 1.

Entrada:

Um número inteiro não negativo entre 0 e 1.000.000.000 que pode ou não ser um número de Fibonacci.

Resultado:

Um valor de verdade / falsidade indicando se a entrada é ou não um número de Fibonacci.

Exemplos:

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

Pontuação:

Isso é código-golfe , menor número de bytes ganhos.

Neim , 2 bytes

f𝕚

Explicação:

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

Funciona da mesma forma que minha resposta É quadril para ser quadrada , mas usa uma lista infinita diferente: fpara fibonacci.

Tente!

JavaScript (ES6), 34 bytes

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

Gera recursivamente a sequência de Fibonacci até encontrar um item maior ou igual à entrada e, em seguida, retorna o item == input.

Retina , 23 bytes

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

Experimente online!

Entrada em unário, saídas 0ou 1.

Explicação

A sequência de Fibonacci é um bom candidato para uma solução com referências futuras, ou seja, uma "referência anterior" que se refere a um grupo circundante ou a um que aparece posteriormente no regex (neste caso, estamos realmente usando os dois). Ao combinar números como esse, precisamos descobrir uma expressão recursiva para a diferença entre os elementos da sequência. Por exemplo, para combinar números triangulares, geralmente correspondemos ao segmento anterior mais um. Para corresponder números quadrados (cujas diferenças são os números ímpares), correspondemos ao segmento anterior mais dois.

Como obtemos os números de Fibonacci adicionando o penúltimo elemento ao último, as diferenças entre eles também são apenas os números de Fibonacci. Então, precisamos combinar cada segmento como a soma dos dois anteriores. O núcleo do regex é este:

(         # 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.
)*

Agora isso acaba adicionando os números de Fibonacci a partir de 1 , ou seja, 1, 1, 2, 3, 5, ... . Aqueles adicionar até 1, 2, 4, 7, 12, ... . Ou seja, eles são um a menos que os números de Fibonacci, então adicionamos um 1no final. O único caso que isso não cobre é zero, então temos a ^$alternativa no começo para cobrir isso.

Regex (sabor ECMAScript), 392 358 328 224 206 165 bytes

As técnicas que precisam entrar em jogo para combinar os números de Fibonacci com um regex ECMAScript (em unário) estão muito distantes de como é feito melhor na maioria dos outros sabores de regex. A falta de referências ou recursões avançadas / aninhadas significa que é impossível contar diretamente ou manter um total em execução de qualquer coisa. A falta de atenção faz com que muitas vezes seja um desafio ter espaço suficiente para trabalhar.

Muitos problemas devem ser abordados de uma perspectiva totalmente diferente e parecem insolúveis até a chegada de algumas informações importantes. Obriga você a lançar uma rede muito mais ampla para descobrir quais propriedades matemáticas dos números com os quais você está trabalhando podem ser usadas para tornar um problema específico solucionável.

Em março de 2014, foi o que aconteceu com os números de Fibonacci. Olhando para a página da Wikipedia, inicialmente não consegui descobrir uma maneira, embora uma propriedade em particular parecesse tentadoramente próxima. Então o matemático teukon delineou um método que deixou bem claro que seria possível fazer isso, usando essa propriedade junto com outra. Ele estava relutante em realmente construir o regex. Sua reação quando fui em frente e fiz isso:

Você é louco! ... Eu pensei que você poderia fazer isso.

Como nas minhas outras postagens de regex matemática unária do ECMAScript, darei um aviso: eu recomendo aprender como resolver problemas matemáticos unários no regex do ECMAScript. Foi uma jornada fascinante para mim, e não quero estragá-la para quem potencialmente queira experimentá-la, especialmente aqueles interessados ​​na teoria dos números. Consulte essa publicação para obter uma lista de problemas recomendados consecutivamente identificados por spoilers para resolver um por um.

Portanto , não leia mais, se não quiser que você estrague uma mágica de expressões regulares unárias . Se você quiser tentar descobrir essa mágica, eu recomendo começar resolvendo alguns problemas no regex ECMAScript, conforme descrito no post acima.

O desafio que enfrentei inicialmente: Um número inteiro positivo x é um número de Fibonacci se e somente se 5x ² + 4 e / ou 5x ² - 4 é um quadrado perfeito. Mas não há espaço para calcular isso em uma regex. O único espaço em que temos que trabalhar é o próprio número. Nem sequer temos espaço suficiente para multiplicar por 5 ou pegar o quadrado, quanto mais os dois.

A idéia da teukon sobre como resolvê-lo ( originalmente publicada aqui ):

O regex é apresentado com uma string do formulário ^x*$, seja z o seu comprimento. Verifique se z é ou não um dos primeiros números de Fibonacci à mão (até 21 devem fazer). Se não é:

1. Leia alguns números, a <b, de modo que b não seja maior que 2a.
   
2. Use previsões futuras para criar a ² , ab e b ² .
   
3. Afirme que 5a ² + 4 ou 5a ² - 4 é um quadrado perfeito (portanto, deve ser F _n-1 para alguns n).
   
4. Afirme que 5b ² + 4 ou 5b ² + 4 é um quadrado perfeito (então b deve ser F _n ).
   
5. Verifique se z = F _{2n + 3} ou z = F _{2n + 4} usando o anteriormente criado a ² , ab e b ² , e as identidades:
   
   • F _2n-1 = F _n ² + F _n-1 ²
     
   • F _2n = (2F _n-1 + F _n ) F _n
     

Em resumo: essas identidades nos permitem reduzir o problema de verificar se um determinado número é Fibonacci e verificar se um par de números muito menores é Fibonacci. Um pouco de álgebra mostrará que para n grande o suficiente (n = 3 deve funcionar), F _{2n + 3} > F _n + 5F _n ² + 4, portanto sempre deve haver espaço suficiente.

E aqui está uma maquete do algoritmo em C que escrevi como teste antes de implementá-lo em regex.

Portanto, sem mais delongas, aqui está o regex:

^((?=(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})$

Experimente online!

E a versão comentada e bem impressa:

^(
  (?=
    (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.
)$

O algoritmo de multiplicação não é explicado nesses comentários, mas é brevemente explicado em um parágrafo dos meus abundantes números regex post .

Eu mantinha seis versões diferentes do regex de Fibonacci: quatro que aumentam do menor para a velocidade mais rápida e usam o algoritmo explicado acima, e outras duas que usam um algoritmo diferente, muito mais rápido, mas muito mais longo, que, como eu descobri, pode realmente retornar o índice de Fibonacci como uma correspondência (explicando que o algoritmo aqui está além do escopo deste post, mas é explicado na discussão original Gist ). Eu não acho que manteria tantas versões muito semelhantes de um regex novamente, porque na época eu estava fazendo todos os meus testes no PCRE e Perl, mas meu mecanismo de regex é rápido o suficiente para que as preocupações com a velocidade não sejam mais tão importantes (e se uma construção específica estiver causando um gargalo, posso adicionar uma otimização) - embora eu provavelmente mantenha novamente uma versão mais rápida e uma versão mais curta, se a diferença em velocidade eram grandes o suficiente.

A versão "retorne o índice de Fibonacci menos 1 como uma correspondência" (não muito golfe):

Experimente online!

Todas as versões estão no github com o histórico completo de consolidação das otimizações de golfe:

regex para correspondência de números de Fibonacci - curto, velocidade 0.txt (o menor, mas mais lento, como neste post)
regex para correspondência de números de Fibonacci - curto, velocidade 1.txt
regex para correspondência de números de Fibonacci - curto, velocidade 2.txt
regex para números Fibonacci correspondentes - curto, velocidade 3.txt
regex para números Fibonacci correspondentes - mais rápido.txt
regex para números Fibonacci correspondentes - retorno index.txt

Python 3 , 48 bytes

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

Experimente online!

Python 2, 48 44 bytes

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

Experimente online

_{Agradecimentos a Jonathan Allan por salvar 4 bytes}

05AB1E , 8 7 bytes

>ÅF¹å¹m

Explicação:

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

Experimente online!

-1 graças a Jonathan Allan pela solução alternativa do número 0 não-fibonacci.

Perl 6 , 23 bytes

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

Sério , 3 bytes

,fu

Experimente online!

Retorna o índice +1 na lista de números de Fibonacci, se for verdade, caso contrário, retornará falso.

Explicação:

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

Gelatina ,  8 7  6 bytes

-r‘ÆḞċ

Experimente online!

Quão?

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

Notas:

• o incremento, ‘, é necessária para que isso funciona para 2 e 3 , uma vez que são o 3 ^rd e 4 ^th números de Fibonacci - além de 3 todos os números de Fibonacci são maiores do que seu índice.
• o -é necessária (e não apenas ‘R) para isso funciona para 0 desde 0 é a 0 ^º número de Fibonacci;

ZX81 BASIC 180 151 100 ~ 94 bytes BASIC tokenizados

Com os agradecimentos a Moggy nos fóruns do SinclairZXWorld, aqui está uma solução muito mais limpa que economiza mais bytes.

 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

Isso produzirá 1 se um número de Fibonacci for inserido ou zero, se não. Embora isso economize bytes, é muito mais lento que as soluções antigas abaixo. Para velocidade (mas mais bytes BASIC), remova os VALinvólucros ao redor dos números literais da string. Aqui estão as soluções antigas com algumas explicações:

 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

As alterações acima economizam mais bytes BASIC para condensar as IFinstruções em uma única PRINTna linha 12; outros bytes foram salvos usando a VALpalavra - chave e, e using GOTO CODE "£", que no conjunto de caracteres ZX81 é 12. As seqüências de caracteres salvam mais bytes sobre os números, pois todos os valores numéricos são armazenados como flutuadores, portanto, ocupam mais espaço na pilha VAR.

C #, 109 bytes

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

Definitivamente poderia ser melhorado, mas não tive tempo.

> <> , 21 19 + 3 = 24 22 bytes

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

A entrada deve estar na pilha no início do programa, portanto, +3 bytes para o -vsinalizador.

Experimente online!

Isso funciona gerando números de Fibonacci até que sejam maiores ou iguais ao número de entrada e, em seguida, verificando o último número gerado quanto à igualdade com a entrada. Saída 1se fosse um número de Fibonacci, 0caso contrário.

Para garantir que isso 0seja tratado corretamente, a semente é -1 1- o primeiro número gerado será em 0vez de 1.

Obrigado a @cole por apontar que ipode ser usado para empurrar -1a pilha quando STDIN estiver vazio. Muito esperto!

Versão anterior:

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

Mathematica, 37 bytes

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

-4 bytes de @ngenisis

MATL (16 bytes)

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

Experimente online!

Não é a solução mais eficiente, mas queria usar o método direto de verificar se "5 * x ^ 2 +/- 4" é um quadrado perfeito .

Explicação:

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.

Nota:

No caso "0", retorna "2" porque 4 e -4 são quadrados perfeitos, o mesmo com 1 que produz "1 1". Considere qualquer saída diferente de zero como "verdade" e 0 como "falso".

Pari / GP , 32 bytes

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

Experimente online!

PHP , 44 bytes

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

Experimente online!

PHP , 58 bytes

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

Experimente online!

Java, 72 69 68 63 59 55 50 49 bytes

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

Teste você mesmo!

Alternativa (ainda 49 bytes)

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

Não é muito original: é a versão iterativa simples e básica.

Isso funciona para números de até 1.836.311.903 (47º número de fibonacci) incluídos. Acima disso, o resultado é indefinido (incluindo um potencial loop infinito).

Agradecimentos a Kevin Cruijssen e David Conrad por ajudarem no golfe :)

C # (.NET Core) , 51 bytes

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

Experimente online!

-6 bytes graças a @Oliver!

Esta solução usa uma função recursiva bastante direta.

• A variável né o número a ser testado.
• As variáveis ae bsão os 2 números mais recentes na sequência.
• Verifica se o primeiro dos 2 números mais recentes é menor que a entrada. Nesse caso, é feita uma chamada recursiva para os próximos números da série.
• Caso contrário, verifique se o primeiro número é igual à entrada e retorne o resultado.

O link TIO demonstra esse trabalho para 1134903170, que excede o valor máximo exigido pelo desafio.

Alquimista , 205 134 bytes

^{Muito obrigado ao ASCII-only pela fusão inteligente de estados, economizando 71 bytes !!}

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

Experimente online ou verifique em lote!

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

Gelatina , 5 bytes

ȷḶÆḞi

Experimente online!

Retorna 0 para números não Fibonacci e a posição indexada em 1 do número na sequência Fibonacci para números Fibonacci.

Explicação:

ȷḶÆḞ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

Dyalog APL, 17 bytes

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

Experimente online!

R, 43 40 bytes

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

pryr::f cria uma função:

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

Usa DescTools::Fibonaccipara criar os primeiros x+1números de fibonacci e verifica a inclusão. x+1porque o terceiro fibnum é 2 e isso não seria suficiente para verificar a inclusão de 3.

Felizmente Desctools::Fibonacci(0)=0, esse é um bom freebee.

-3 bytes graças ao MickyT

Haskell , 31 bytes

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

Experimente online! Isso explora o fato de que a entrada estará no intervalo de 0 a 1.000.000.000, portanto, precisamos verificar apenas os 45 primeiros números de Fibonacci. f=0:scanl(+)1fgera uma lista infinita de números de Fibonacci, take 45fé a lista dos primeiros 45 números de Fibonacci e elemverifica se a entrada está nesta lista.

Versão irrestrita: 36 bytes

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

Experimente online! Para qualquer um n, pegar os primeiros n+3números de Fibonacci garantirá que nestará nesta lista se for um número de Fibonacci.

Observe que essa abordagem é incrivelmente ineficiente para números altos que não são números de Fibonacci, porque todos os n+3números de Fibonacci precisam ser calculados.

Javascript (ES6 sem o operador **), 44 bytes

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

Baseia-se na proporção entre números sucessivos de Fibonacci que se aproximam da proporção áurea. O valor de c é a parte fracionária da entrada dividida pela proporção áurea - se a entrada for Fibonacci, isso será muito próximo de 1 e o valor de c-c² será muito pequeno.

Não é tão curto quanto algumas das outras respostas JS, mas é executado no tempo O (1).

Julia 0.4 , 29 bytes

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

Experimente online!

Se não é assim que você responde Julia, me avise. Não tenho certeza de como a entrada funciona no TIO.

R, 32 31 bytes

Recebe informações de stdin, retorna TRUEou FALSEconforme apropriado.

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

Lisp comum, 61 54 bytes

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

Experimente online!

A redução no tamanho em relação à versão anterior:

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

foi desencadeado pela idéia de que, para gerar a sequência dos números de Fibonacci, apenas duas variáveis ​​são necessárias, e não três.

Mathematica, 33 bytes

AtomQ@*InverseFunction[Fibonacci]

JS (ES6), 57 bytes

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

Usa o método de carusocomputing . Muito mais golfista do que minha outra resposta .

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