Introdução
Todos nós conhecemos e amamos nossa sequência de Fibonacci e já vimos uma infinidade de desafios aqui. No entanto, ainda não temos um caso muito simples que esta resposta forneça: Fibonacci invertido! Então, dado o F_n
seu trabalho é encontrar n
.
Especificação
Entrada
Sua entrada será um número inteiro não negativo, que é garantido como parte da sequência de fibonacci.
Saída
A saída também deve ser um número inteiro não negativo.
O que fazer?
A introdução já dizia: Dado um número de fibonacci, produza seu índice. O número de Fiboancci é definido como F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
e você recebe F(n)
e deve retornar n
.
Casos de canto em potencial
0 é uma entrada e saída válida.
Se for fornecido "1" como entrada, você poderá enviar "1" ou "2", como preferir.
Você sempre pode assumir que sua entrada é realmente um número de fibonacci.
Você pode assumir que a entrada é representável como um número inteiro assinado de 32 bits.
Quem ganha?
Isso é código-golfe, então a resposta mais curta em bytes vence!
Regras padrão se aplicam, é claro.
Casos de teste
0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46
Respostas:
Na verdade, 1 byte
Sim, existe um construído para isso, desde 16 de novembro de 2015 .
Experimente online
Por diversão, sem o builtin, são 9 bytes:
Experimente online!
Explicação:
fonte
Mathematica, 25 bytes
Função. Bastante auto-explicativo, se você me perguntar.
fonte
Python,
363432 bytesVersões prévias:
Explicação
A idéia central é inverter a fórmula
o que nos diz que
para obter
As otimizações de golfe são:
len(str(n))
para calcular a base de log 10 sem importarlog
(versão antiga usada.bit_length()
para calcular a base de log 2)n
a um poder, para que a aproximação do logaritmo possa distinguir entre números sucessivos de FibonacciEm seguida, o divisor foi truncado com a menor precisão possível e o multiplicador escolhido para fornecer os resultados corretos para todos os números de fibonacci de 32 bits.
fonte
f=
não é contado.lambda n:~-len(`66*n**6`)//1.24
deve funcionar.05AB1E , 3 bytes
Código:
Explicação:
Usa a codificação CP-1252 . Experimente online! .
fonte
Geléia,
1411 bytesExperimente online!
Esta é a minha primeira resposta Jelly! Isso usa o algoritmo da resposta MATL . Agradecimentos a Dennis por eliminar 3 bytes!
Explicação:
Esta é a resposta certa, agora só precisamos lidar com o caso especial de '0'. Com '0' como argumento, obtemos
-infinity
, então retornamosfonte
Julia,
272618 bytesIsso usa o inverso da fórmula de Binet , com precisão suficiente para números inteiros de 32 bits; na verdade, funciona até F (153) = 42.230.279.526.998.466.217.810.220.532.898> 2 105 .
Experimente online!
Como funciona
A fórmula de Binet afirma o seguinte.
Restringindo F ao conjunto de Fibonacci, o mapa n → F n tem um inverso direito F → n F .
Nós temos isso
e tudo o que resta a fazer é lidar com o caso 0 .
Como a entrada é restrita a números inteiros de 32 bits, podemos usar literais decimais curtos em vez das constantes na fórmula.
log φ = 0,481211825059603447… ≈ 0,48
Infelizmente, 0,5 não é suficientemente preciso.
√5 = 2,2360679774997896964… ≈ 3
Pode parecer uma aproximação terrível à primeira vista, mas estamos usando logaritmos e, como log 3 - log √5 = 0,29389333245105… , o resultado antes do arredondamento será desativado por um pequeno fator constante.
0,5 ± 0,7
Devido ao excesso da aproximação anterior, poderíamos realmente omitir esse termo completamente e ainda assim obter resultados corretos para F> 0 . No entanto, se F = 0 , o logaritmo será indefinido. 0,7 acabou sendo o menor valor que estende nossa fórmula para F = 0 .
fonte
JavaScript,
5450695042 bytesCertamente não vai ganhar, apenas por diversão :)
Ok, verificar zero consome 19 bytes. WTF?Estúpido-eu.Demo! Para ver o último caso de teste, você precisa rolar um pouco o console.
Obrigado @edc pela redução de 8 bytes.
fonte
b=>{for(j=1,i=c=0;b-i;c++)i=j+(j=i);return c}
45, golfedb=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c
42.Perl 6
33 3027 bytesTente
Explicação:
Teste:
fonte
first *==$_
por justfirst $_
, porque um número é um correspondente inteligente válido....
operador em vez defirst
Geléia , 8 bytes
Experimente online! Observe que essa abordagem é muito ineficiente para o último caso de teste.
Como funciona
fonte
Pyke, 5 bytes
Experimente aqui!
fonte
Python, 29 bytes
Divide recursivamente a entrada pela proporção áurea 1,61 até ficar abaixo de 0,7 e gera o número de divisões.
Para 0, o código gera
False
, igual a 0 em Python . Isso pode ser evitado por 2 bytesfonte
JavaScript (ES6),
3933 bytesMesmo com o ES7, a fórmula inversa do Binet leva 47 bytes:
fonte
log
e precompute todas as constantes ...f(n,k,j+k)
inclua a atribuiçãof=
e conte-a como +2 bytes . A regra para lambdas sem nome não deve se aplicar aqui.Sábio, 49 bytes
Agradecemos a TuukkaX pela sugestão sobre
sqrt(5)
como economizars
alguns bytes.Experimente online .
Essa abordagem usando uma inversa da fórmula de Binet oferece várias melhorias em relação à abordagem anterior: é mais rápida (tempo constante versus tempo quadrático), na verdade funciona para entradas maiores e é mais curta!
Os usuários de Python podem se perguntar por que estou usando, e
sqrt(5)
não o menor5**.5
- é porque5**.5
é calculado com apow
função de C e perde precisão devido a problemas de ponto flutuante. Muitas funções matemáticas (incluindosqrt
elog
) são sobrecarregadas no Sage para retornar um valor simbólico exato, que não perde precisão.fonte
sqrt(5)
em uma variável e usá-lo duas vezes, em vez de digitarsqrt(5)
duas vezes?MATL , 14 bytes
Experimente online!
Isso usa uma inversa da fórmula de Binet e, portanto, é muito rápido.
Seja F denotado o n- ésimo número de Fibonacci e φ a proporção áurea . Então
O código usa essa fórmula com duas modificações:
Como isso é feito
fonte
O1G:"yy+]vGmfq
t?17L&YlXkQ
5X^*
. ( Eu já fiz isso antes .) E não conheço o MATL o suficiente para continuar melhorando.Python, 38 bytes
Teste em Ideone .
fonte
JavaScript, 22 bytes
fonte
-Infinity|0
está0
em JavaScript. Vai saber.-Infinity = FFF00000 00000000
. Fiquei feliz em descobrir, ele poupa 3 bytes por não ter que preceder um teste de zero explícito comon&&
. Além disso, o principal objetivo de|0
é um substituto paraMath.trunc()
(como÷
em Julia).C,
6258 bytesDetalhado
fonte
Java 7, 70 bytes
https://ideone.com/I4rUC5
fonte
int c(int n){int a=0,b=1,c=0,t;for(;a<n;t=b,b+=a,a=t)c++;return c;}
(não testada)int c(int n){int a=0,b=1,c=0;while(a<n){c++;b+=a;a=b-a;}return c;}
(não testada)int c(int n){int a=0,b=1,c=0;for(;a<n;b+=a,a=b-a)c++;return c;}
(não testada)TSQL, 143 bytes
A entrada entra
@n
como emDECLARE @n INT = 1836311903;
fonte
Haskell, 45 bytes
fonte
Sesos , 28 bytes
Hexdump:
Experimente online!
(Tempo exponencial porque, no Sesos, a cópia de um número precisa de tempo exponencial.)
Assembly usado para gerar o arquivo binário:
fonte
Java 8 61 bytes
O mesmo que a resposta @dainichi foi reduzida, usando o Java 8 lambdas. A resposta é uma expressão válida de rvalue.
Ungolfed:
fonte
Pitão, 13 bytes
Suíte de teste.
Aproximação em Python 2:
abordagem alternativa, 18 bytes
Suíte de teste.
Isso usa
.I
para inverso.fonte
Java 7, 89 bytes
Inspirado pela explicação da @Adnan resposta 05AB1E 's .
Casos não testados e de teste:
Experimente aqui. (O limite de tempo foi excedido para o último caso de teste, mas funciona em cerca de 30 a 45 segundos no meu PC.)
Saída:
fonte
Perl 5.10, 48 bytes
Basicamente, procurando o certo
n
para issoF(n) = input
.-a
switch adiciona um byte.Experimente aqui!
fonte
J,
322717 bytesCalcula os primeiros n números de Fibonacci e localiza o índice de n nessa lista.
Uso
Comandos extras são usados para formatar várias entradas / saídas. O último caso de teste é omitido, pois exigirá muito mais tempo para calcular.
Explicação
fonte
Mathematica, 30 bytes
Função pura; retorna 2 se a entrada for 1.
Não supera a outra entrada do Mathematica, mas mostra um método incomum: é um fato (muito legal) que o número N-ésimo de Fibonacci seja o número inteiro mais próximo de [1 / sqrt (5) vezes a N-ésima potência da proporção áurea] (" Fórmula de Binet ").
Portanto, a função inversa será o logaritmo base- [proporção áurea] de [sqrt (5) vezes o número de Fibonacci em questão]. O
.8+
é um truque para garantir que não aceitemos o logaritmo de 0, sem estragar os outros valores.fonte
Japonês , 10 bytes
Experimente online!
Explicação
fonte
Braquilog , 14 bytes
Experimente online!
Leva a entrada através da variável de saída e sai através da variável de entrada.
Não sei ao certo por que
≜
é necessário.fonte
Javascript (usando biblioteca externa) (84 bytes)
Link para lib: https://github.com/mvegh1/Enumerable
Explicação do código: A biblioteca possui um método estático que cria uma sequência até o predicado ter um valor de retorno indefinido. O predicado possui uma assinatura de ("i" ndex, corrente interna "a" gerada). A cada iteração, verificamos se o último elemento da matriz interna é igual à entrada, n. Caso contrário, retorne o próximo valor na sequência fib. Caso contrário, o predicado terá um resultado indefinido que encerra a geração da sequência. Em seguida, retornamos o comprimento da sequência (e subtraímos 1 para cumprir com a base 0, como visto no OP
fonte
n=>{a=c=t=0,b=1;while(a<n){c++;t=b;b+=a;a=t}return c}
Experimente online!