Найти ближайший номер Фибоначчи

30

Мы все знакомы со знаменитой последовательностью Фибоначчи , которая начинается с 0и 1, и каждый элемент является суммой двух предыдущих. Вот первые несколько терминов (OEIS A000045 ):

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584

Если задано положительное целое число , верните ближайшее число последовательности Фибоначчи по следующим правилам:

  • Ближе число Фибоначчи определяется как число Фибоначчи с наименьшим абсолютной разности с заданным числом. Например, 34является ближайшим числом Фибоначчи 30, потому что |34 - 30| = 4, которое меньше второго ближайшего 21, для которого |21 - 30| = 9.

  • Если данное целое число принадлежит последовательности Фибоначчи, то ближайшее число Фибоначчи является само собой. Например, самое близкое число Фибоначчи к 13точно 13.

  • В случае ничьей, вы можете выбрать либо одно из чисел Фибоначчи, которые оба ближе всего к входу, либо просто вывести их оба. Например, если на входе 17, все следующие соотношения: 21, 13или 21, 13. Если вы вернете их оба, укажите формат.

Применяются стандартные лазейки . Вы можете получить ввод и обеспечить вывод любым стандартным методом . Ваша программа / функция должна обрабатывать только значения до 10 8 .


Тестовые случаи

Вход -> Выход

1 -> 1
3 -> 3
4 -> 3 или 5 или 3, 5
6 -> 5
7 -> 8
11 -> 13
17 -> 13 или 21 или 13, 21
63 -> 55
101 -> 89
377 -> 377
467 -> 377
500 -> 610
1399 -> 1597

счет

Это , поэтому выигрывает самый короткий код в байтах на каждом языке !

Мистер Xcoder
источник
Песочница .
г-н Xcoder
Кстати, вот некоторый код Python для SO для эффективного выполнения этого для больших входных данных, а также сценарий, который можно использовать для синхронизации различных алгоритмов.
PM 2Ring
0 считается положительным целым числом?
Аликс
@AlixEisenhardt Нет. Положительное целое числоn означает n ≥ 1.
г-н Xcoder

Ответы:

21

Python 2 , 43 байта

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

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

Перебирает пары последовательных чисел Фибоначчи, (a,b)пока не достигнет единицы, где входное значение nменьше их средней точки (a+b)/2, затем вернется a.

Написано как программа (47 байт):

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

Одинаковая длина :

f=lambda n,a=0,b=1:b/2/n*(b-a)or f(n,b,a+b)
XNOR
источник
15

Нейм , 5 байт

f𝐖𝕖S𝕔

Объяснение:

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

В новейшей версии Neim это может быть занято до 3 байтов:

fS𝕔

Поскольку бесконечные списки были переработаны, чтобы подняться только до их максимального значения.

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

Okx
источник
Как это 5 байтов, когда там 2 символа? И в чем разница между первым и вторым решением?
Caird Coneheringaahing
1
Вы считаете байты или символы? Похоже, первый составляет 15 байтов, а второй 7 байтов.
Натеовами,
Это, вероятно, имеет какую-то собственную кодовую страницу, в которой каждый символ является собственным байтом, что означает, что первый - 5 байтов, а второй - 3 байта. Разница между ними заключается в том, что первый выбирает руководство для первых 93 элементов, а второй фрагмент в более новой версии автоматически выбирает максимально возможное значение, с которым могут работать языки int size
Roman Gräf
1
@cairdcoinheringaahing У меня часто были проблемы с людьми, которые не могли видеть мои программы. Снимок экрана
Okx,
1
@Okx Да ладно, интересно, я бы не догадался.
Натеовами,
8

R , 70 67 64 62 60 байт

-2 байта благодаря джурио!

Еще 2 байта благодаря Джурио (мальчик может он в гольф!)

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

Поскольку нам нужно обрабатывать только значения 10^8, это работает.

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

Читает nсо стандартного ввода. whileцикл генерирует чисел Фибоначчи в F(в порядке убывания); в случае ничьей возвращается большее. Это вызовет ряд предупреждений, потому чтоwhile(F<1e8) вычисляет только оператор для первого элемента Fс предупреждением

Первоначально я использовал F[which.min(abs(F-n))]наивный подход, но @djhurio предложил, (F-n)^2так как порядок будет эквивалентен, а orderне which.min. orderвозвращает перестановку индексов, чтобы поместить свой ввод в возрастающем порядке, поэтому нам нужно[1] в конце получить только первое значение.

более быстрая версия:

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

хранит только последние два числа Фибоначчи

Giuseppe
источник
1
Хороший. -2 байтаF=1:0;n=scan();while(n>F)F=c(F[1]+F[2],F);F[order((F-n)^2)][1]
джурио
1
И быстрая версия с таким же количеством байтовF=1:0;n=scan();while(n>F)F=c(sum(F),F[1]);F[order((F-n)^2)][1]
djhurio
1
@djhurio приятно! большое спасибо вам.
Джузеппе
1
Мне это нравится. Снова -2 байтаF=1:0;while(F<1e8)F=c(F[1]+F[2],F);F[order((F-scan())^2)][1]
Джурио
Использование встроенной функции для генерации мышц короче:numbers::fibonacci(x<-scan(),T)
JAD
6

JavaScript (ES6), 41 байт

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

Округляется по предпочтению.

Нил
источник
Почти идентична версии, над которой я работал. По крайней мере, вы не использовали одни и те же имена переменных, иначе я был бы в шоке.
Grax32
@ Грэкс Да, теперь вы упомянули об этом, Business Cat победил меня в этом ...
Нил
(Ну, почти ... Я заставил свою версию работать с 0, потому что почему бы и нет?)
Нил
f=(n,x=0,y=1)=>x*(2*n<x+y)||f(n,y,x+y)Поскольку вам не нужно работать с 0, вы можете играть в гольф немного больше.
Аликс Айзенхардт
6

Желе , 9 7 байт

-2 байта благодаря @EriktheOutgolfer

‘RÆḞạÐṂ

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

Гольф советы приветствуются :). Принимает int для ввода и возвращает 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
источник
Вы можете удалить µḢ.
Эрик Аутгольфер
@EriktheOutgolfer как в: «Есть способ сделать это, если вы думаете об этом», или как в «Если вы буквально просто отодвигаете их, это все еще работает»?
nmjcman101
Как в «это разрешено правилами». : P
Эрик Outgolfer
Ах. Спасибо! (Текст наполнителя)
nmjcman101
5

Машинный код x86-64, 24 байта

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

Вышеуказанные байты кода определяют функцию в 64-битном машинном коде x86, которая находит ближайшее число Фибоначчи к указанному входному значению, n .

Функция соответствует соглашению о вызовах AMD64 System V (стандартно для систем Gnu / Unix), так что единственный параметр ( n) передается в EDIрегистр, а результат возвращается вEAX регистр.

Неуправляемая сборка мнемоники:

; 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

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

Код в основном делится на три части:

  • Первая часть очень проста: она просто инициализирует наши рабочие регистры. EAXустановлен в 0, иEDX установлен на 1.
  • Следующая часть представляет собой цикл , который итеративно вычисляет число Фибоначчи по обе стороны от входного значения, n. Этот код основан на моей предыдущей реализации Фибоначчи с вычитанием , но ... гм ... не с вычитанием. :-) В частности, он использует тот же трюк вычисления чисел Фибоначчи с использованием двух переменных, здесь, они являются EAXи EDXрегистры. Этот подход чрезвычайно удобен здесь, потому что он дает нам смежные числа Фибоначчи. Кандидат потенциально меньше, чем n удерживается, в EAXто время как кандидат потенциально больше, чем n удерживается вEDX, Я весьма горжусь тем, насколько плотно я смог создать код внутри этого цикла (и еще более удивительно, что я открыл его самостоятельно, и только позже понял, насколько он похож на ответ вычитания, связанный выше).

  • Как только у нас есть доступные значения Фибоначчи в EAXи EDX, это концептуально простой вопрос выяснения, к какому из них ближе (в терминах абсолютного значения) n. На самом деле принимать абсолютное значение будет стоить путем слишком много байт, поэтому мы просто делаем серию вычитаний. Комментарий справа от предпоследней инструкции условного перемещения удачно объясняет здесь логику. Это либо перемещается EDXв EAXили листах EAXсам по себе, так что , когда функции RETурны, ближайшее число Фибоначчей возвращаются в EAX.

В случае связи возвращается меньшее из двух значений-кандидатов, так как мы использовали CMOVGвместо CMOVGEвыбора. Это тривиальное изменение, если вы предпочитаете другое поведение. Возврат обоих значений не является началом; только одно целое число, пожалуйста!

Коди Грей
источник
Списки NASM хороши для ответов Codegolf, так как они смешивают байты машинного кода с оригинальным закомментированным источником несколько компактно. В nasm foo.asm -l /dev/stdout | cut -b -28,$((28+12))-недавнем ответе я использовал обрезку некоторых столбцов между машинным кодом и исходным кодом.
Питер Кордес
1
В 32-битном коде вы можете получить eax = 0 и edx = 1 только в 4 байтах вместо 5, используя xor eax,eax/ cdq/ inc edx. Таким образом, вы можете создать 32-битную версию соглашения о вызовах, которая сохранит байт.
Питер Кордес
Раньше я это делал, @Peter, но здесь много путаницы из-за того, что представления находятся в «сборке» или «машинном коде». По-видимому, некоторые опытные пользователи утверждают, что есть разница, и возражают против того, чтобы я подсчитывал байты машинного кода для ответа, который представляется с использованием мнемоники сборки. Естественно, я думаю, что это глупо, потому что «сборка» - это всего лишь мнемоническое представление байтов машины, но я остался без голосования. Я обнаружил, что отдельная презентация создает меньше трения, хотя лично мне это тоже не нравится.
Коди Грей,
Другой трюк хорош - спасибо. Я должен был подумать об этом, я cdqчасто использую ответы на вопросы по коду. Пользовательское соглашение о вызовах не требуется. Я обычно использую __fastcallсоглашение о вызовах Microsoft для 32-битного кода. Приятно то, что он поддерживается GCC с аннотацией, поэтому вы все еще можете использовать службу TIO, которую все хотят видеть.
Коди Грей,
Ах да, любое старое соглашение о вызовах регистров работает для вас. В моем последнем ответе на Codegolf требовались указатели в edi/ esiдля lodsb/stosb , и только SysV делает это (забавный факт: специально по этой причине, потому что некоторые функции передают свои аргументы в memset / memcpy, и я думаю, что gcc в то время нравился встроить строку ops).
Питер Кордес
4

PowerShell , 80 74 байта

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

(Попробуйте онлайн! Временно не отвечает)

Итеративное решение. Принимает ввод $n, устанавливает $a,$bзначение be 1,0, а затем $aвыполняет цикл с Фибоначчи, пока не станет больше, чем ввод. В этот момент мы индексируем на ($b,$a)основе логического значения, является ли разница между первым элементом и $nбольше, чем между $nвторым элементом. Это осталось на конвейере, вывод неявный.

AdmBorkBork
источник
4

JavaScript (ES6), 67 байт

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)

Контрольные примеры

Arnauld
источник
4

JavaScript (Babel Node) , 41 байт

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

Основанный на удивительном Python-ответе ovs

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

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
Бизнес Кот
источник
Это было прокомментировано на мой ответ, но это заставило бы его перестать работать 0(не то, что это нужно; я просто хочу, чтобы это):f=(n,i=1,j=1)=>n+n<i+j?i:f(n,j,j+i)
Нейл
4

Python, 74 байта

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

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

Как это работает

Для всех k ≥ 0, так как | φ - k / √5 | <1/2, F k = φ k / √5 + φ - k / √5 = round (φ k / √5). Таким образом, возвращаемое значение переключается с F k - 1 на F k именно там, где k = log φ ( n √2√5) - 1 или n = φ k + 1 / (2√5), что находится в пределах 1/4 от F k + 1/2 = ( F k - 1 + F k ) / 2.

Андерс Касеорг
источник
Черт, я знал, что что-то подобное должно быть возможным. Отлично сработано! (+1)
SteamyRoot
3

Python 3 , 103 байта

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

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

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

Оригинальный (неверный) ответ:

Python 3 , 72 байта

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

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

Моя первая подача PPCG. Вместо рекурсивного вычисления чисел Фибоначчи или их предопределения в этом коде используется то, как n-е число Фибоначчи является ближайшим целым числом к ​​n-й степени золотого сечения, деленного на корень из 5.

SteamyRoot
источник
Хорошая работа! Добро пожаловать в PPCG :)
musicman523
Чтобы правильно рассчитать количество байтов вашего кода, я думаю, что вам нужно назначить лямбду, как показано в других ответах Python. Однако этот алгоритм не всегда работает правильно для n в диапазоне (1, 1 + 10 ** 8). Например, n = 70 возвращает 89, но должно возвращать 55. Вот значения n <120, на которые он дает неправильные ответы: (27, 44, 70, 71, 114, 115, 116). В целях тестирования вы можете использовать nearest_fib_PM2Rфункцию, на которую я ссылался в своем комментарии к вопросу.
PM 2Ring
@ PM2Ring Вы правы, я сделал глупую ошибку ... Теперь у меня есть правильное решение, но с гораздо большим количеством байтов. Что касается лямбды, я считаю, что вы не правы. Я считаю, что ответы, присваивающие лямбду, делают это только потому, что используют рекурсию Другие ответы Python 3, например, не назначают первую лямбду.
SteamyRoot
3

Такси, 2321 байт

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.

Попробуйте онлайн!
Попробуйте онлайн с комментариями!

Без гольфа с комментариями:

[ 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.
Инженер Тост
источник
2

Python 3 , 84 байта

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)

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

Это может работать, но это, конечно, не быстро ...

Выходы Trueвместо 1, но в Python они эквивалентны.

notjagan
источник
2

постоянный ток, 52 байта

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

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

Принимает ввод при запуске, используя ?

Отредактировано, чтобы принять верхнюю часть стека в качестве входного значения, -1 байт.

Ввод сохраняется в реестре i. Затем мы помещаем 1 и 1 в стек, чтобы запустить последовательность Фибоначчи, и мы генерируем последовательность, пока не достигнем значения больше, чем i. На данный момент у нас есть два числа в последовательности Фибоначчи в стеке: одно меньше или равно i, а другое больше чем i. Мы преобразуем их в соответствующие различия, iа затем сравниваем различия. Наконец, мы восстанавливаем число Фибоначчи, добавляя или вычитая разницу в i.

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

brhfl
источник
Функции разрешены.
CalculatorFeline
Спасибо, я неоднократно пропускал это в тексте задачи.
brhfl
2

C # (.NET Core) , 63 56 байт

-1 байт благодаря @Neil

-6 байт благодаря @Nevay

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

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

jkelm
источник
Сохраняет ли for(;b<n;a=b,b+=c)c=a;байт?
Нил
Вы можете удалить cс помощью b+=a,a=b-a(следует сохранить 6 байтов).
Невай
2

Q / KDB +, 51 байт

{w where l=min l:abs neg[x]+w:{x,sum -2#x}/[x;0 1]}
aodNap
источник
2
Добро пожаловать в PPCG!
Мартин Эндер,
2

Гексагония , 37 байт

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

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

ungolfed:

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

Сломано:

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

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

Средняя точка находится в (last + curr) / 2. Мы можем сократить это, поскольку next - это уже last + curr, и если вместо этого мы умножим целевое целое число на 2, нам нужно только проверить, что (next - 2 * target)> 0, а затем вернуть last.

Brigmor
источник
2

Брахилог , 22 байта

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

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

На самом деле все, что я здесь сделал, это приклеил вместе классическое решение Fatalize. Вернуть ближайшее решение простых чисел и мое собственное. Являюсь ли я числом Фибоначчи? решение. К счастью, последний уже работает с выходной переменной; к сожалению, он также включает в себя необходимый отрезок, который должен быть изолирован для +2 байта, поэтому единственная точка выбора, которую он отбрасывает, - это оставить без изменений.

Несвязанная строка
источник
1

Java 7, 244 234 байта

 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
источник
Почему бы вам не использовать Java 8 и не превратить это в лямбду? Вы также можете удалить, staticесли хотите придерживаться Java 7.
Okx
У вас есть две ошибки в вашем коде ( r>c&&s<cдолжно быть r>=c&&s<=c, s-cдолжно быть c-s). Вы можете удалить ненужные пробелы, использовать int f(int i){return i<2?i:f(--i)+f(--i);}, использовать один оператор return с троичным оператором в c и удалить специальную обработку для c-s==r-cвозврата любого значения.
Nevay
@ Наверное, я не вижу ошибки, я проверял ее без
сбоев
1

Perl 6 , 38 байт

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

Попробуй это

{   # 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
}

Для потенциального ускорения добавьте .tail(2)раньше .sort(…).

В случае связи, он всегда будет возвращать меньшее из двух значений, потому что sortэто стабильная сортировка. (два значения, которые будут сортироваться одинаково, сохраняют свой порядок)

Брэд Гилберт b2gills
источник
1

Pyth, 19 байт

JU2VQ=+Js>2J)hoaNQJ

Попробуй здесь

объяснение

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.

источник