Todos conhecemos a famosa sequência de Fibonacci , que começa com 0
e 1
, e cada elemento é a soma dos dois anteriores. Aqui estão os primeiros termos (OEIS A000045 ):
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584
Dado um número inteiro positivo , retorne o número mais próximo da sequência de Fibonacci, sob estas regras:
O número de Fibonacci mais próximo é definido como o número de Fibonacci com a menor diferença absoluta com o número inteiro especificado. Por exemplo,
34
é o número de Fibonacci mais próximo de30
, porque|34 - 30| = 4
, que é menor que o segundo mais próximo21
, para o qual|21 - 30| = 9
.Se o número inteiro pertencer à sequência de Fibonacci, o número mais próximo de Fibonacci será exatamente ele mesmo. Por exemplo, o número mais próximo de Fibonacci
13
é exatamente13
.Em caso de empate, você pode optar por gerar um dos números de Fibonacci mais próximos da entrada ou apenas gerar os dois. Por exemplo, se a entrada for
17
, todos os seguintes são válidos:21
,13
ou21, 13
. Caso você devolva os dois, mencione o formato.
Aplicam-se lacunas padrão . Você pode receber e fornecer saída através de qualquer método padrão . Seu programa / função deve lidar apenas com valores até 10 8 .
Casos de teste
Entrada -> Saída 1 -> 1 3 -> 3 4 -> 3 ou 5 ou 3, 5 6 -> 5 7 -> 8 11 -> 13 17 -> 13 ou 21 ou 13, 21 63 -> 55 101 -> 89 377 -> 377 467 -> 377 500 -> 610 1399 -> 1597
Pontuação
Isso é código-golfe , então o código mais curto em bytes em todos os idiomas vence!
n
Número inteiro positivo implican ≥ 1
.Respostas:
Python 2 , 43 bytes
Experimente online!
Iera através de pares de números consecutivos de Fibonacci
(a,b)
até atingir um onde a entradan
é menor que o ponto médio(a+b)/2
e depois retornaa
.Escrito como um programa (47 bytes):
Mesmo comprimento :
fonte
Neim , 5 bytes
Explicação:
Na versão mais recente do Neim, isso pode ser aumentado para 3 bytes:
Como listas infinitas foram retrabalhadas para atingir apenas seu valor máximo.
Experimente online!
fonte
Python ,
5552 bytesExperimente online!
fonte
R ,
7067646260 bytes-2 bytes graças a djhurio!
-2 bytes a mais graças a djhurio (menino, ele pode jogar golfe!)
Como só precisamos lidar com valores de até
10^8
, isso funciona.Experimente online!
Lê
n
de stdin. owhile
loop gera os números de fibonacci emF
(em ordem decrescente); em caso de empate, o maior é retornado. Isso acionará uma série de avisos, porquewhile(F<1e8)
apenas avalia a instrução do primeiro elemento doF
com um avisoOriginalmente eu usei
F[which.min(abs(F-n))]
, a abordagem ingênua, mas o @djhurio sugeriu,(F-n)^2
já que o pedido será equivalente, eorder
nãowhich.min
.order
retorna uma permutação de índices para colocar sua entrada em ordem crescente, portanto, precisamos[1]
no final obter apenas o primeiro valor.versão mais rápida:
armazena apenas os dois últimos números de fibonacci
fonte
F=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1]
F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1]
F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]
numbers::fibonacci(x<-scan(),T)
JavaScript (ES6), 41 bytes
Arredonda por preferência.
fonte
f=(n,x=0,y=1)=>x*(2*n<x+y)||f(n,y,x+y)
Como você não precisa trabalhar com 0, pode jogar um pouco mais.Gelatina ,
97 bytes-2 bytes graças a @EriktheOutgolfer
Experimente online!
Dicas de golfe são bem-vindas :). Pega um int para entrada e retorna uma lista de int.
fonte
µḢ
.Mathematica, 30 bytes
Experimente online!
fonte
Código da máquina x86-64, 24 bytes
Os bytes de código acima definem uma função no código de máquina x86 de 64 bits que localiza o número Fibonacci mais próximo do valor de entrada especificado
n
.A função segue a convenção de chamada do System V AMD64 (padrão nos sistemas Gnu / Unix), de modo que o único parâmetro (
n
) seja passado noEDI
registro e o resultado seja retornado noEAX
registro.Mnemônicos de montagem não destruídos:
Experimente online!
O código basicamente se divide em três partes:
EAX
está definido como 0 eEDX
está definido como 1.A próxima parte é um loop que calcula iterativamente os números de Fibonacci em ambos os lados do valor de entrada
n
. Este código é baseado na minha implementação anterior de Fibonacci com subtração , mas ... um ... não é com subtração. :-) Em particular, ele usa o mesmo truque para calcular o número de Fibonacci usando duas variáveis - aqui, esses são os registradoresEAX
eEDX
. Essa abordagem é extremamente conveniente aqui, porque nos fornece números adjacentes de Fibonacci. O candidato potencialmente menor que on
retidoEAX
, enquanto o candidato potencialmente maior quen
retidoEDX
. Estou bastante orgulhoso de quão forte eu fui capaz de tornar o código dentro desse loop (e ainda mais agradado por ter o descoberto de forma independente, e só depois percebi o quão semelhante era à resposta de subtração vinculada acima).Uma vez que tenhamos disponíveis os valores candidatos de Fibonacci em
EAX
eEDX
, é uma questão conceitualmente simples de descobrir qual deles está mais próximo (em termos de valor absoluto)n
. Realmente tomando um valor absoluto custaria maneira demasiados bytes, então apenas fazer uma série de subtrações. O comentário à direita da penúltima instrução de movimentação condicional explica adequadamente a lógica aqui. Isso se moveEDX
para dentroEAX
ou saiEAX
sozinho, de modo que, quando a função éRET
executada, o número Fibonacci mais próximo é retornadoEAX
.No caso de empate, o menor dos dois valores candidatos é retornado, pois usamos em
CMOVG
vez deCMOVGE
fazer a seleção. É uma mudança trivial, se você preferir o outro comportamento. Retornar ambos os valores é um não iniciador; apenas um resultado inteiro, por favor!fonte
nasm foo.asm -l /dev/stdout | cut -b -28,$((28+12))-
aparar algumas colunas entre o código da máquina e a fonte em uma resposta recente.xor eax,eax
/cdq
/inc edx
. Assim, você pode criar uma versão de convenção de chamada personalizada de 32 bits que salve um byte.cdq
muito nas respostas do código-golfe. Uma convenção de chamada personalizada não é necessária. Eu costumo usar a__fastcall
convenção de chamada da Microsoft para código de 32 bits. O bom disso é que ele é suportado pelo GCC com uma anotação, para que você ainda possa usar o serviço TIO que todos desejam ver.edi
/esi
forlodsb
/stosb
, e apenas o x86-64 SysV faz isso (fato interessante: de propósito por esse motivo, porque algumas funções transmitem seus argumentos para memset / memcpy, e acho que o gcc na época gostou para operações de sequência em linha).PowerShell ,
8074 bytes(Experimente online! Temporariamente sem resposta)
Solução iterativa. Aceita entrada
$n
, define$a,$b
como1,0
e, em seguida, faz loop com Fibonacci até que$a
seja maior que a entrada. Nesse ponto, indexamos com($b,$a)
base no booleano se a diferença entre o primeiro elemento e$n
é maior que entre$n
e o segundo elemento. Isso é deixado no pipeline, a produção está implícita.fonte
JavaScript (ES6), 67 bytes
Casos de teste
Mostrar snippet de código
fonte
JavaScript (Nó Babel) , 41 bytes
Baseado na impressionante resposta Python do ovs
Experimente online!
Ungolfed
fonte
0
(não que ele precise; eu só quero): #f=(n,i=1,j=1)=>n+n<i+j?i:f(n,j,j+i)
Python, 74 bytes
Experimente online!
Como funciona
Para todos k ≥ 0, uma vez que | φ - k / √5 | <1/2, F k = φ k / √5 + φ - k / √5 = arredondado (φ k / √5). Portanto, o valor de retorno muda de F k - 1 para F k exatamente onde k = log φ ( n ⋅2√5) - 1, ou n = φ k + 1 / (2√5), que está dentro de 1/4 de F k + 1/2 = ( F k - 1 + F k ) / 2.
fonte
05AB1E , 6 bytes
Experimente online!
fonte
C (gcc) ,
86858376 bytesExperimente online!
fonte
Java (OpenJDK 8) ,
605756 bytesExperimente online!
-1 byte graças a @Neil
fonte
Python 3 , 103 bytes
Experimente online!
Infelizmente, tive que usar um def em vez de lambda ... Provavelmente há muito espaço para melhorias aqui.
Resposta original (incorreta):
Python 3 , 72 bytesExperimente online!
Minha primeira submissão PPCG. Em vez de calcular números de Fibonacci recursivamente ou tê-los predefinidos, este código usa como o n-ésimo número de Fibonacci é o número inteiro mais próximo da n-ésima potência da proporção áurea dividida pela raiz de 5.
fonte
nearest_fib_PM2R
função que eu vinculei no meu comentário à pergunta.Táxi, 2321 bytes
Experimente online!
Experimente online com comentários!
Sem jogar golfe com comentários:
fonte
Python 3 , 84 bytes
Experimente online!
Pode funcionar, mas certamente não é rápido ...
Saídas em
True
vez de1
, mas em Python são equivalentes.fonte
dc, 52 bytes
Experimente online!
Recebe entrada na execução usando?
Editado para assumir o topo da pilha como valor de entrada, -1 byte.
A entrada é armazenada no registro
i
. Em seguida, colocamos 1 e 1 na pilha para iniciar a sequência de Fibonacci e geramos a sequência até atingirmos um valor maior quei
. Neste ponto, temos dois números na sequência de Fibonacci na pilha: um que é menor ou igual ai
e outro que é maior quei
. Nós os convertemos em suas respectivas diferençasi
e depois comparamos as diferenças. Finalmente, reconstruímos o número de Fibonacci adicionando ou subtraindo a diferença parai
.Ops, eu estava carregando dois registros na ordem errada e depois trocando-os, desperdiçando um byte.
fonte
C # (.NET Core) ,
6356 bytes-1 byte graças a @Neil
-6 bytes graças a @Nevay
Experimente online!
fonte
for(;b<n;a=b,b+=c)c=a;
salvar um byte?c
usandob+=a,a=b-a
(deve salvar 6 bytes).Q / KDB +, 51 bytes
fonte
Hexagonia , 37 bytes
Experimente online!
ungolfed:
Quebrado:
Como alguns outros pôsteres, percebi que quando o ponto médio de last e curr é maior que o alvo, o menor dos dois é o mais próximo ou o mais próximo.
O ponto médio está em (última + corrente) / 2. Podemos encurtar isso, porque next já é o último + curr e, se multiplicarmos nosso número inteiro alvo por 2, precisamos verificar apenas que (próximo - 2 * destino)> 0, e retornar por último.
fonte
Braquilog , 22 bytes
Experimente online!
Realmente, tudo o que fiz aqui foi colar o clássico de Fatalize. Retorne a solução mais próxima de números primos e a minha. Sou um número de Fibonacci? solução. Felizmente, este último já opera na variável de saída; infelizmente, ele também inclui um corte necessário que deve ser isolado por +2 bytes; portanto, o único ponto de escolha que ele descarta é
ⁱ
deixar≜
intacto.fonte
Japonês
-g
, 8 bytesTente
fonte
Java 7,
244234 bytesfonte
static
lo se quiser manter o Java 7.r>c&&s<c
deveria serr>=c&&s<=c
,s-c
deveria serc-s
). Você pode remover espaços em branco não necessários, usarint f(int i){return i<2?i:f(--i)+f(--i);}
, usar uma única declaração de retorno com o operador ternário em c e remover o tratamento especial,c-s==r-c
pois o retorno de qualquer valor é permitido.Pyke , 6 bytes
Experimente online!
fonte
Lisp comum, 69 bytes
Experimente online!
fonte
Perl 6 , 38 bytes
Teste-o
Para uma potencial aceleração, adicione
.tail(2)
antes.sort(…)
.No caso de empate, ele sempre retornará o menor dos dois valores, porque
sort
é uma classificação estável. (dois valores que classificariam o mesmo manterão sua ordem)fonte
Pitão, 19 bytes
Experimente aqui
Explicação
fonte
Haskell, 48 bytes
Experimente online!
fonte