Encontre o número de Fibonacci mais próximo

30

Todos conhecemos a famosa sequência de Fibonacci , que começa com 0e 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 de 30, porque |34 - 30| = 4, que é menor que o segundo mais próximo 21, 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é exatamente 13.

  • 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, 13ou 21, 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 é , então o código mais curto em bytes em todos os idiomas vence!

Mr. Xcoder
fonte
Sandbox .
Mr. Xcoder
FWIW, aqui estão alguns códigos Python no SO para fazer isso com eficiência em entradas grandes, junto com um script que pode ser usado para cronometrar vários algoritmos.
PM 2Ring
0 é considerado como um número inteiro positivo?
Alix Eisenhardt
@AlixEisenhardt Não .n Número inteiro positivo implica n ≥ 1.
Mr. Xcoder

Respostas:

21

Python 2 , 43 bytes

f=lambda n,a=0,b=1:a*(2*n<a+b)or f(n,b,a+b)

Experimente online!

Iera através de pares de números consecutivos de Fibonacci (a,b)até atingir um onde a entrada né menor que o ponto médio(a+b)/2 e depois retorna a.

Escrito como um programa (47 bytes):

n=input()
a=b=1
while 2*n>a+b:a,b=b,a+b
print a

Mesmo comprimento :

f=lambda n,a=0,b=1:b/2/n*(b-a)or f(n,b,a+b)
xnor
fonte
15

Neim , 5 bytes

f𝐖𝕖S𝕔

Explicação:

f       Push infinite Fibonacci list
 𝐖                     93
  𝕖     Select the first ^ elements
        This is the maximum amount of elements we can get before the values overflow
        which means the largest value we support is 7,540,113,804,746,346,429
   S𝕔   Closest value to the input in the list

Na versão mais recente do Neim, isso pode ser aumentado para 3 bytes:

fS𝕔

Como listas infinitas foram retrabalhadas para atingir apenas seu valor máximo.

Experimente online!

Okx
fonte
Como são esses 5 bytes quando existem 2 caracteres? E qual é a diferença entre a primeira e a segunda solução?
caird coinheringaahing
11
Você está contando bytes ou caracteres? Parece que o primeiro tem 15 bytes e o segundo, 7 bytes.
Nateowami
Provavelmente, isso tem algum tipo de página de código própria, na qual cada caractere é próprio byte, o que significa que o primeiro tem 5 bytes e o segundo, 3 bytes. A diferença entre os dois é que o primeiro seleciona os primeiros 93 elementos manual, enquanto o segundo snipet em uma versão mais recente seleciona automaticamente o valor mais alto possível que o idiomas tamanho int pode lidar
Roman Gräf
11
@cairdcoinheringaahing Eu sempre tive problemas com pessoas que não podiam ver meus programas. Captura de tela
Okx 20/07/19
11
@ Ok Ok, interessante, eu não teria adivinhado.
Nateowami 20/07
8

R , 70 67 64 62 60 bytes

-2 bytes graças a djhurio!

-2 bytes a mais graças a djhurio (menino, ele pode jogar golfe!)

F=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]

Como só precisamos lidar com valores de até 10^8, isso funciona.

Experimente online!

nde stdin. o whileloop gera os números de fibonacci em F(em ordem decrescente); em caso de empate, o maior é retornado. Isso acionará uma série de avisos, porque while(F<1e8)apenas avalia a instrução do primeiro elemento doF com um aviso

Originalmente eu usei F[which.min(abs(F-n))], a abordagem ingênua, mas o @djhurio sugeriu, (F-n)^2já que o pedido será equivalente, e ordernão which.min. orderretorna 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:

F=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][‌​1]

armazena apenas os dois últimos números de fibonacci

Giuseppe
fonte
11
Agradável. -2 bytesF=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1]
djhurio
11
E a versão mais rápida com o mesmo número de bytesF=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1]
djhurio
11
@djhurio nice! Muito obrigado.
19717 Giuseppe
11
Eu gosto disso. -2 bytes novamenteF=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]
djhurio
O uso de um builtin para gerar os fibnums é mais curto:numbers::fibonacci(x<-scan(),T)
JAD
6

JavaScript (ES6), 41 bytes

f=(n,x=0,y=1)=>y<n?f(n,y,x+y):y-n>n-x?x:y
<input type=number min=0 value=0 oninput=o.textContent=f(this.value)><pre id=o>0

Arredonda por preferência.

Neil
fonte
Quase idêntico à versão em que estava trabalhando. Pelo menos você não usou os mesmos nomes de variáveis ​​ou eu ficaria assustado.
Grax32
@ Grax Huh, agora que você mencionou, o Business Cat me venceu ...
Neil
(Bem, quase ... Eu fiz a minha versão trabalho com a 0, porque por que não?)
Neil
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.
Alix Eisenhardt
6

Gelatina , 9 7 bytes

-2 bytes graças a @EriktheOutgolfer

‘RÆḞạÐṂ

Experimente online!

Dicas de golfe são bem-vindas :). Pega um int para entrada e retorna uma lista de int.

            ' input -> 4
‘           ' increment -> 5
 R          ' range -> [1,2,3,4,5]
  ÆḞ        ' fibonacci (vectorizes) -> [1,1,2,3,5,8]
     ÐṂ     ' filter and keep the minimum by:
    ạ       ' absolute difference -> [3,3,2,1,1,4]
            ' after filter -> [3,5]
nmjcman101
fonte
Você pode remover µḢ.
Erik the Outgolfer
@EriktheOutgolfer como em: "Existe uma maneira de fazer isso se você pensar sobre isso", ou como em "Se você literalmente apenas retroceder o espaço, ele ainda funciona"?
nmjcman101
Como em "é permitido pelas regras". : P
Erik the Outgolfer
Ah Obrigado! (Texto de preenchimento)
nmjcman101
5

Código da máquina x86-64, 24 bytes

31 C0 8D 50 01 92 01 C2 39 FA 7E F9 89 D1 29 FA 29 C7 39 D7 0F 4F C1 C3

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 no EDIregistro e o resultado seja retornado no EAXregistro.

Mnemônicos de montagem não destruídos:

; unsigned int ClosestFibonacci(unsigned int n);
    xor    eax, eax        ; initialize EAX to 0
    lea    edx, [rax+1]    ; initialize EDX to 1

  CalcFib:
    xchg   eax, edx        ; swap EAX and EDX
    add    edx, eax        ; EDX += EAX
    cmp    edx, edi
    jle    CalcFib         ; keep looping until we find a Fibonacci number > n

    mov    ecx, edx        ; temporary copy of EDX, because we 'bout to clobber it
    sub    edx, edi
    sub    edi, eax
    cmp    edi, edx
    cmovg  eax, ecx        ; EAX = (n-EAX > EDX-n) ? EDX : EAX
    ret

Experimente online!

O código basicamente se divide em três partes:

  • A primeira parte é muito simples: apenas inicializa nossos registros de trabalho. EAXestá definido como 0 e EDXestá 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 registradores EAXe EDX. Essa abordagem é extremamente conveniente aqui, porque nos fornece números adjacentes de Fibonacci. O candidato potencialmente menor que o n retido EAX, enquanto o candidato potencialmente maior que n 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 EAXe EDX, é 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 move EDXpara dentro EAXou sai EAXsozinho, de modo que, quando a função é RETexecutada, o número Fibonacci mais próximo é retornado EAX.

No caso de empate, o menor dos dois valores candidatos é retornado, pois usamos em CMOVGvez de CMOVGEfazer 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!

Cody Gray
fonte
As listagens NASM são ótimas para respostas de codegolf, pois elas misturam os bytes de código de máquina com a fonte comentada original de maneira um tanto compacta. Costumava 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.
Peter Cordes
11
No código de 32 bits, você pode obter eax = 0 e edx = 1 em apenas 4 bytes em vez de 5, com 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.
Peter Cordes
Eu costumava fazer isso, @ Peter, mas há muita confusão aqui sobre as submissões estarem em "assembly" ou "código de máquina". Aparentemente, alguns dos usuários experientes afirmam que há uma diferença e se opõem à minha contagem dos bytes do código da máquina para obter uma resposta que é apresentada usando mnemônicos de montagem. Naturalmente, acho isso estúpido, porque "assembly" é apenas uma representação mnemônica dos bytes da máquina, mas fui derrotado. Eu descobri que a apresentação separada cria menos atrito, mesmo que eu pessoalmente não goste também.
Cody Gray
O outro truque é bom - obrigado. Eu deveria ter pensado nisso, uso cdqmuito nas respostas do código-golfe. Uma convenção de chamada personalizada não é necessária. Eu costumo usar a __fastcallconvençã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.
Cody Gray
Ah, sim, qualquer convenção antiga de registro de chamadas funciona para você. Minha resposta mais recente sobre codegolf precisava de ponteiros em edi/ esifor lodsb/ 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).
22617 Peter Cordes
4

PowerShell , 80 74 bytes

param($n)for($a,$b=1,0;$a-lt$n;$a,$b=$b,($a+$b)){}($b,$a)[($b-$n-gt$n-$a)]

(Experimente online! Temporariamente sem resposta)

Solução iterativa. Aceita entrada $n, define $a,$bcomo 1,0e, em seguida, faz loop com Fibonacci até que $aseja 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 $ne o segundo elemento. Isso é deixado no pipeline, a produção está implícita.

AdmBorkBork
fonte
4

JavaScript (ES6), 67 bytes

f=(n,k,y)=>(g=k=>x=k>1?g(--k)+g(--k):k)(k)>n?x+y>2*n?y:x:f(n,-~k,x)

Casos de teste

Arnauld
fonte
4

JavaScript (Nó Babel) , 41 bytes

f=(n,i=1,j=1)=>j<n?f(n,j,j+i):j-n>n-i?i:j

Baseado na impressionante resposta Python do ovs

Experimente online!

Ungolfed

f=(n,i=1,j=1)=> // Function f: n is the input, i and j are the most recent two Fibonacci numbers, initially 1, 1
 j<n?           // If j is still less than n
  f(n,j,j+i)    //  Try again with the next two Fibonacci numbers
 :              // Else:
  j-n>n-i?i:j   //  If n is closer to i, return i, else return j
Gato de negócios
fonte
Isso foi comentado na minha resposta, mas faria com que parasse de funcionar 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)
Neil
4

Python, 74 bytes

import math
r=5**.5
p=r/2+.5
lambda n:round(p**int(math.log(n*2*r,p)-1)/r)

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.

Anders Kaseorg
fonte
Porra, eu sabia que algo assim tinha que ser possível. Bem feito! (+1)
SteamyRoot
3

C (gcc) , 86 85 83 76 bytes

f(n){n=n<2?:f(n-1)+f(n-2);}i,j,k;g(n){for(;k<n;j=k,k=f(i++));n=k-n<n-j?k:j;}

Experimente online!

cleblanc
fonte
3

Python 3 , 103 bytes

import math
def f(n):d=5**.5;p=.5+d/2;l=p**int(math.log(d*n,p))/d;L=[l,p*l];return round(L[2*n>sum(L)])

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 bytes

lambda n:r(p**r(math.log(d*n,p))/d)
import math
d=5**.5
p=.5+d/2
r=round

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

SteamyRoot
fonte
Bom trabalho! Bem-vindo ao PPCG :)
musicman523
Para calcular de maneira justa a contagem de bytes do seu código, acho que você precisa atribuir o lambda, conforme mostrado nas outras respostas do Python. No entanto, esse algoritmo nem sempre funciona corretamente para n no intervalo (1, 1 + 10 ** 8). Por exemplo, n = 70 retorna 89, mas deve retornar 55. Aqui estão os n valores <120 que ele fornece respostas erradas para: (27, 44, 70, 71, 114, 115, 116). Para fins de teste, você pode usar a nearest_fib_PM2Rfunção que eu vinculei no meu comentário à pergunta.
PM 2Ring
@ PM2Ring Você está certo, cometi um erro estúpido ... Agora tenho uma solução correta, mas com muito mais bytes. Quanto ao lambda, acredito que você está errado. Acredito que as respostas que atribuem o lambda apenas o fazem porque eles usam recursão. As outras respostas do Python 3 não atribuem o primeiro lambda, por exemplo.
SteamyRoot
3

Táxi, 2321 bytes

Go to Post Office:w 1 l 1 r 1 l.Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 1 r.Pickup a passenger going to Trunkers.Go to Trunkers:n 1 l 1 l.0 is waiting at Starchild Numerology.1 is waiting at Starchild Numerology.Go to Starchild Numerology:w 1 l 2 l.Pickup a passenger going to Bird's Bench.Pickup a passenger going to Cyclone.Go to Cyclone:w 1 r 4 l.[a]Pickup a passenger going to Rob's Rest.Pickup a passenger going to Magic Eight.Go to Bird's Bench:n 1 r 2 r 1 l.Go to Rob's Rest:n.Go to Trunkers:s 1 l 1 l 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:w 2 r.Pickup a passenger going to Trunkers.Pickup a passenger going to Magic Eight.Go to Zoom Zoom:n.Go to Trunkers:w 3 l.Go to Magic Eight:e 1 r.Switch to plan "b" if no one is waiting.Pickup a passenger going to Firemouth Grill.Go to Firemouth Grill:w 1 r.Go to Rob's Rest:w 1 l 1 r 1 l 1 r 1 r.Pickup a passenger going to Cyclone.Go to Bird's Bench:s.Pickup a passenger going to Addition Alley.Go to Cyclone:n 1 r 1 l 2 l.Pickup a passenger going to Addition Alley.Pickup a passenger going to Bird's Bench.Go to Addition Alley:n 2 r 1 r.Pickup a passenger going to Cyclone.Go to Cyclone:n 1 l 1 l.Switch to plan "a".[b]Go to Trunkers:w 1 l.Pickup a passenger going to Cyclone.Go to Bird's Bench:w 1 l 1 r 1 l.Pickup a passenger going to Cyclone.Go to Rob's Rest:n.Pickup a passenger going to Cyclone.Go to Cyclone:s 1 l 1 l 2 l.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to What's The Difference.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 1 l.Pickup a passenger going to Magic Eight.Go to Sunny Skies Park:e 1 r 1 l.Go to Cyclone:n 1 l.Pickup a passenger going to Sunny Skies Park.Pickup a passenger going to What's The Difference.Go to Sunny Skies Park:n 1 r.Pickup a passenger going to What's The Difference.Go to What's The Difference:n 1 r 1 l.Pickup a passenger going to Magic Eight.Go to Magic Eight:e 1 r 2 l 2 r.Switch to plan "c" if no one is waiting.Go to Sunny Skies Park:w 1 l 1 r.Pickup a passenger going to The Babelfishery.Go to Cyclone:n 1 l.Switch to plan "d".[c]Go to Cyclone:w 1 l 2 r.[d]Pickup a passenger going to The Babelfishery.Go to The Babelfishery:s 1 l 2 r 1 r.Pickup a passenger going to Post Office.Go to Post Office:n 1 l 1 r.

Experimente online!
Experimente online com comentários!

Sem jogar golfe com comentários:

[ Find the Fibonacci number closest to the input ]
[ Inspired by: https://codegolf.stackexchange.com/q/133365 ]


[ n = STDIN ]
Go to Post Office: west 1st left 1st right 1st left.
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 1st right.
Pickup a passenger going to Trunkers.
Go to Trunkers: north 1st left 1st left.


[ Initialize with F0=0 and F1=1 ]
0 is waiting at Starchild Numerology.
1 is waiting at Starchild Numerology.
Go to Starchild Numerology: west 1st left 2nd left.
Pickup a passenger going to Bird's Bench.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 1st right 4th left.


[ For (i = 1; n > F(i); i++) { Store F(i) at Rob's Rest and F(i-1) at Bird's Bench } ]
[a]
Pickup a passenger going to Rob's Rest.
Pickup a passenger going to Magic Eight.
Go to Bird's Bench: north 1st right 2nd right 1st left.
Go to Rob's Rest: north.
Go to Trunkers: south 1st left 1st left 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: west 2nd right.
Pickup a passenger going to Trunkers.
Pickup a passenger going to Magic Eight.
Go to Zoom Zoom: north.
Go to Trunkers: west 3rd left.
Go to Magic Eight: east 1st right.
Switch to plan "b" if no one is waiting.

[ n >= F(i) so iterate i ]
Pickup a passenger going to Firemouth Grill.
Go to Firemouth Grill: west 1st right.
Go to Rob's Rest: west 1st left 1st right 1st left 1st right 1st right.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: south.
Pickup a passenger going to Addition Alley.
Go to Cyclone: north 1st right 1st left 2nd left.
Pickup a passenger going to Addition Alley.
Pickup a passenger going to Bird's Bench.
Go to Addition Alley: north 2nd right 1st right.
Pickup a passenger going to Cyclone.
Go to Cyclone: north 1st left 1st left.
Switch to plan "a".


[b]
[ F(i) > n which means n >= F(i-1) and we need to figure out which is closer and print it]
Go to Trunkers: west 1st left.
Pickup a passenger going to Cyclone.
Go to Bird's Bench: west 1st left 1st right 1st left.
Pickup a passenger going to Cyclone.
Go to Rob's Rest: north.
Pickup a passenger going to Cyclone.
Go to Cyclone: south 1st left 1st left 2nd left.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to What's The Difference.
Pickup a passenger going to What's The Difference.
[ Passengers:n, n, F(i-1) ]
Go to What's The Difference: north 1st left.
Pickup a passenger going to Magic Eight.
[ Passengers:n, n-F(i-1) ]
Go to Sunny Skies Park: east 1st right 1st left.
Go to Cyclone: north 1st left.
Pickup a passenger going to Sunny Skies Park.
Pickup a passenger going to What's The Difference.
[ Passengers: n-F(i-1), F(i-1), F(i) ]
Go to Sunny Skies Park: north 1st right.
Pickup a passenger going to What's The Difference.
[ Passengers: n-F(i-1), F(i), n ]
Go to What's The Difference: north 1st right 1st left.
[ Passengers: n-F(i-1), F(i)-n ]
Pickup a passenger going to Magic Eight.
Go to Magic Eight: east 1st right 2nd left 2nd right.
Switch to plan "c" if no one is waiting.

[ If no one was waiting, then {n-F(i-1)} < {F(i)-n} so we return F(i-1) ]
Go to Sunny Skies Park: west 1st left 1st right.
Pickup a passenger going to The Babelfishery.
Go to Cyclone: north 1st left.
Switch to plan "d".

[c]
[ Otherwise {n-F(i-1)} >= {F(i)-n} so we return F(i) ]
[ Note: If we didn't switch to plan c, we still pickup F(i) but F(i-1) will be the *first* passenger and we only pickup one at The Babelfishery ]
[ Note: Because of how Magic Eight works, we will always return F(i) in the event of a tie ]
Go to Cyclone: west 1st left 2nd right.
[d]
Pickup a passenger going to The Babelfishery.
Go to The Babelfishery: south 1st left 2nd right 1st right.
Pickup a passenger going to Post Office.
Go to Post Office: north 1st left 1st right.
Engenheiro Toast
fonte
2

Python 3 , 84 bytes

lambda k:min(map(f,range(2*k)),key=lambda n:abs(n-k))
f=lambda i:i<3or f(i-1)+f(i-2)

Experimente online!

Pode funcionar, mas certamente não é rápido ...

Saídas em Truevez de 1, mas em Python são equivalentes.

notjagan
fonte
2

dc, 52 bytes

si1d[dsf+lfrdli>F]dsFxli-rlir-sdd[lild-pq]sDld<Dli+p

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 que i. Neste ponto, temos dois números na sequência de Fibonacci na pilha: um que é menor ou igual a ie outro que é maior que i. Nós os convertemos em suas respectivas diferenças ie 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.

brhfl
fonte
Funções são permitidas.
CalculatorFeline
Obrigado, perdi várias vezes isso no texto do desafio.
Brhfl
2

C # (.NET Core) , 63 56 bytes

-1 byte graças a @Neil

-6 bytes graças a @Nevay

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

Experimente online!

jkelm
fonte
Será que for(;b<n;a=b,b+=c)c=a;salvar um byte?
Neil
Você pode remover cusando b+=a,a=b-a(deve salvar 6 bytes).
Nevay 19/07
2

Q / KDB +, 51 bytes

{w where l=min l:abs neg[x]+w:{x,sum -2#x}/[x;0 1]}
aodNap
fonte
2
Bem-vindo ao PPCG!
Martin Ender
2

Hexagonia , 37 bytes

?\=-${&"*.2}+".|'=='.@.&}1.!_|._}$_}{

Experimente online!

ungolfed:

   ? \ = - 
  $ { & " * 
 . 2 } + " .
| ' = = ' . @
 . & } 1 . !
  _ | . _ }
   $ _ } { 

Quebrado:

start:
? { 2 ' * //set up 2*target number
" ' 1     //initialize curr to 1

main loop:
} = +     //next + curr + last
" -       //test = next - (2*target)
branch: <= 0 -> continue; > 0 -> return

continue:
{ } = &   //last = curr
} = &     //curr = next


return:
{ } ! @   //print last

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.

Brigmor
fonte
2

Braquilog , 22 bytes

;I≜-.∧{0;1⟨t≡+⟩ⁱhℕ↙.!}

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.

String não relacionada
fonte
1

Java 7, 244 234 bytes

 String c(int c){for(int i=1;;i++){int r=f(i);int s=f(i-1);if(r>c && s<c){if(c-s == r-c)return ""+r+","+s;else if(s-c > r-c)return ""+r;return ""+s;}}} int f(int i){if(i<1)return 0;else if(i==1)return 1;else return f(i-2)+f(i-1);}
0x45
fonte
Por que você não usa o Java 8 e transforma isso em um lambda? Você também pode removê- staticlo se quiser manter o Java 7.
Okx 19/07/19
Você tem dois erros no seu código ( r>c&&s<cdeveria ser r>=c&&s<=c, s-cdeveria ser c-s). Você pode remover espaços em branco não necessários, usar int 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-cpois o retorno de qualquer valor é permitido.
Nevay 19/07/19
@Nevay Não vejo o erro, testei-o sem falhas
0x45 20/07/19
1

Pyke , 6 bytes

}~F>R^

Experimente online!

}      -    input*2
 ~F    -   infinite list of the fibonacci numbers
   >   -  ^[:input]
    R^ - closest_to(^, input)
Azul
fonte
1

Lisp comum, 69 bytes

(lambda(n)(do((x 0 y)(y 1(+ x y)))((< n y)(if(<(- n x)(- y n))x y))))

Experimente online!

Renzo
fonte
1

Perl 6 , 38 bytes

{(0,1,*+*...*>$_).sort((*-$_).abs)[0]}

Teste-o

{   # bare block lambda with implicit parameter 「$_」

  ( # generate Fibonacci sequence

    0, 1,  # seed the sequence
    * + *  # WhateverCode lambda that generates the rest of the values
    ...    # keep generating until
    * > $_ # it generates one larger than the original input
           # (that larger value is included in the sequence)

  ).sort(           # sort it by
    ( * - $_ ).abs  # the absolute difference to the original input
  )[0]              # get the first value from the sorted list
}

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)

Brad Gilbert b2gills
fonte
1

Pitão, 19 bytes

JU2VQ=+Js>2J)hoaNQJ

Experimente aqui

Explicação

JU2VQ=+Js>2J)hoaNQJ
JU2                  Set J = [0, 1].
   VQ=+Js>2J)        Add the next <input> Fibonacci numbers.
              oaNQJ  Sort them by distance to <input>.
             h       Take the first.

fonte