Учитывая положительный целочисленный ввод N , выведите два неотрицательных числа a и b , где a <b , с наименьшим возможным средним значением, которое приведет к тому, что число N будет частью повторяющейся последовательности отношений:

f(0) = a
f(1) = b
f(n) = f(n-2)+f(n-1)

Если существует более одного решения, где среднее значение a и b минимально, вы должны вывести решение с наименьшим b .

Вы можете предположить, что N находится в репрезентативном диапазоне целых чисел в вашем языке / системе.

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

N = 1
a = 0, b = 1

N = 15
a = 0, b = 3

N = 21
a = 0, b = 1

N = 27
a = 0, b = 9   <- Tricky test case. [3, 7] is not optimal and [4, 3] is not valid

N = 100
a = 4, b = 10

N = 101
a = 1, b = 12

N = 102
a = 0, b = 3

N = 1000
a = 2, b = 10

Шелуха , 19 18 16 14 13 15 байт

Спасибо Згарбу за сохранение 1 байта.

ḟö£⁰ƒẊ++ÖΣṖ2Θḣ⁰

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

Объяснение:

Отказ от ответственности: я действительно не понимаю ȯƒẊ++раздел кода.

Редактировать: По-видимому, это переводит на Haskell fix.(mapad2(+).).(++), где mapad2применяется функция для всех смежных пар в списке. (Хотя, зная Husk, в контексте этой программы это может означать нечто иное)

            Θḣ⁰    Create the list [0..input]
          Ṗ2       Generate all possible sublists of length 2
        ÖΣ         Sort them on their sums
ḟ                  Find the first element that satisfies the following predicate.
    ƒẊ++             Given [a,b], magically generate the infinite Fibonacci-like
                     sequence from [a,b] without [a,b] at the start.
 ö£⁰                 Is the input in that list (given that it is in sorted order)?

JavaScript (Node.js) , 92 90 89 91 83 82 байта

-3 байта -1 байт благодаря ThePirateBay

-8 -9 байт благодаря Нейлу.

f=(n,a=1,b=0,c=(a,b)=>b<n?c(a+b,a):b>n)=>c(a,b)?b+2<a?f(n,a-1,b+1):f(n,b-~a):[b,a]

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

Примечание: это решение основано на том факте, что никогда не бывает нескольких минимальных решений.

Доказательство того, что никогда не бывает нескольких решений:

Позвольте FIB(a,b,k)быть Fibonacci-как последовательность, начинающаяся с a,b:

FIB(a,b,0) = a
FIB(a,b,1) = b
FIB(a,b,k) = FIB(a,b,k-1) + FIB(a,b,k-2)

Лемма 1

Разница между Фибоначчи-подобных последовательностей сама по себе Фибоначчи , как, например FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k). Доказательство оставлено читателю.

Лемма 2

Для n >= 5существует решение, a,bудовлетворяющее a+b < n:

если nдаже,FIB(0,n/2,3) = n

если nстранно,FIB(1,(n-1)/2,3) = n

доказательство

Случаи, когда n < 5можно проверить исчерпывающе.

Предположим, у нас есть два минимальных решения для n >= 5, a0,b0и a1,b1с a0 + b0 = a1 + b1и a0 != a1.

Тогда существуют k0,k1такие, что FIB(a0,b0,k0) = FIB(a1,b1,k1) = n.

• Случай 1: k0 = k1

  WLOG предполагает b0 < b1(и, следовательно, a0 > a1)

  Позвольте DIFF(k)быть разница между Fibonnaci-как последовательности, начиная с a1,b1и a0,b0:

  DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k) (Лемма 1)

  DIFF(0) = a1 - a0 < 0

  DIFF(1) = b1 - b0 > 0

  DIFF(2) = (a1+b1) - (a0+b0) = 0

  DIFF(3) = DIFF(1) + DIFF(2) = DIFF(1) > 0

  DIFF(4) = DIFF(2) + DIFF(3) = DIFF(3) > 0

  Как только последовательность, подобная Фибоначчи, имеет 2 положительных члена, все последующие члены являются положительными.

  Таким образом, единственный раз DIFF(k) = 0, когда k = 2, так что единственный выбор для k0 = k1это 2.

  Следовательно n = FIB(a0,b0,2) = a0 + b0 = a1 + b1

  Минимальность этих решений противоречит лемме 2.

• Случай 2 k0 != k1:

  Предположим, WLOG k0 < k1.

  У нас есть FIB(a1,b1,k1) = n

  Позволять a2 = FIB(a1,b1,k1-k0)

  Позволять b2 = FIB(a1,b1,k1-k0+1)

  Тогда FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0)(упражнение для читателя)

  Поскольку FIB(a1,b1,k)неотрицателен для k >= 0, он также не убывает.

  Это дает нам a2 >= b1 > a0и b2 >= a1+b1 = a0+b0.

  Тогда пусть DIFF(k) = FIB(a2,b2,k) - FIB(a0,b0,k) = FIB(a2-a0,b2-b0,k)(лемма 1)

  DIFF(0) = a2 - a0 > 0

  DIFF(1) = b2 - b0 >= (a0 + b0) - b0 = a0 >= 0

  DIFF(2) = DIFF(0) + DIFF(1) >= DIFF(0) > 0

  DIFF(3) = DIFF(1) + DIFF(2) >= DIFF(2) > 0

  Еще раз, DIFFимеет 2 положительных условия и, следовательно, все последующие условия являются положительными.

  Таким образом, единственный раз , когда это возможно , что DIFF(k) = 0это k = 1, так что единственный выбор для k0это 1.

  FIB(a0,b0,1) = n

  b0 = n

  Это противоречит лемме 2.

Haskell , 76 72 74 байта

РЕДАКТИРОВАТЬ:

• -4 байта: @ H.PWiz предложил использовать /вместо div, хотя для этого требуется использовать тип дробного числа.
• +2 байта: исправлена ​​ошибка с Enumдиапазонами при добавлении -1.

fпринимает значение Doubleили Rationalтип и возвращает кортеж с таким же. Doubleдолжно быть достаточно для всех значений, которые недостаточно велики, чтобы вызвать ошибки округления, хотя Rationalтеоретически не ограничены.

f n|let a?b=b==n||b<n&&b?(a+b)=[(a,s-a)|s<-[1..],a<-[0..s/2-1],a?(s-a)]!!0

Попробуйте онлайн! (с корректировками заголовка H.PWiz для ввода / вывода Rationals в целочисленном формате)

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

• ?является локально вложенным оператором в области f. a?bрекурсивная шаги через Фибоначчи, как последовательность , начиная с a,bдо b>=n, возвращаясь Trueтогда и только тогда она попадает nточно.
• В списке понимания:
  • sперебирает все числа 1сверху вниз, представляя сумму aи b.
  • aперебирает числа от 0до s/2-1. (Если sнечетно, конец диапазона округляется.)
  • a?(s-a)проверяет, если последовательность начинается с a,s-aпопаданий n. Если это так, понимание списка включает в себя кортеж (a,s-a). (То есть, b=s-aхотя он был слишком коротким, чтобы его можно было назвать.)
  • !!0 выбирает первый элемент (хит) в понимании.

APL (Dyalog) , 75 71 64 59 53 48 44 43 байта

2 байта сохранены благодаря @ Adám

12 байтов сохранено благодаря @ngn

⊃o/⍨k∊¨+\∘⌽⍣{k≤⊃⍺}¨o←a/⍨</¨a←,⍉|-\¨⍳2⍴1+k←⎕

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

Использует ⎕IO←0.

Как? Это сошло с ума.

k←⎕ - назначить вход для k

⍳2⍴1+k←⎕- декартово произведение диапазона 0на kсам с собой

|-\¨ - вычесть каждый элемент правой пары слева и получить абсолютные значения

a←,⍉ - транспонировать, выравнивать и присваивать a

o←a/⍨</¨a - сохранить только пары, где левый элемент меньше правого, и назначить o

oтеперь содержит список всех пар a < b, упорядоченных по их среднему арифметическому

+\∘⌽⍣{k≤⊃⍺}¨o- для каждой пары oприменять фибоначчи (поменять местами пару и сперму), пока не kбудет достигнут или более высокий срок

k∊¨- затем решите, kявляется ли этот последний термин (имеется в виду, что он содержится в последовательности)

o/⍨- и держите пары oтам, где применяется предыдущая проверка

⊃ - вернуть первый результат.

Python 2 , 127 109 107 байт

-2 байта благодаря ovs (меняется andна *)

g=lambda x,a,b:a<=b<x and g(x,b,a+b)or b==x
f=lambda n,s=1,a=0:g(n,a,s-a)*(a,s-a)or f(n,s+(a==s),a%s+(a<s))

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

Есть ли бонусные баллы за n,a,s-a?

Объяснение:

• Первая строка объявляет рекурсивную лямбду, gкоторая проверяет, a, bдостигнет ли расширение как последовательность Фибоначчи x. Это также проверяет a <= b, один из критериев вопроса. (Это позволило бы случаи, когда a == b, но в таком случае 0, aуже были бы обнаружены и возвращены).
  • Цепное неравенство a<=b<xвыполняет сразу две полезные задачи: проверка a <= bи так далее b < x.
  • Если b < xдоходность True, то функция вызывает себя снова следующих двух чисел в последовательности Фибоначчи: b, a+b. Это означает, что функция будет продолжать разрабатывать новые условия, пока ...
  • Если b < xдает False, то мы достигли точки, где мы должны проверить, если b==x. Если это так, это вернется True, означая, что начальная пара в a, bконечном итоге достигнет x. В противном случае, если b > xпара недействительна.
• Вторая строка объявляет другую рекурсивную лямбду, fкоторая находит решение для данного значения n. Он рекурсивно пробует новые начальные пары a, b, пока не g(n, a, b)получит True. Это решение затем возвращается.
  • Функция рекурсивно подсчитывает исходные пары Фибоначчи, используя две переменные s(первоначально 1) и a(первоначально 0). На каждой итерации aувеличивается и a, s-aиспользуется в качестве первой пары. Однако при aпопадании sон сбрасывается обратно в 0 и sувеличивается. Это означает, что пары подсчитываются по следующей схеме:

    s = 1 (0, 1) (1, 0)
    s = 2 (0, 2) (1, 1) (2, 0)
    s = 3 (0, 3) (1, 2), (2, 1), (3, 0)
    

    Очевидно, что он содержит несколько недопустимых пар, однако они мгновенно удаляются при передаче g(см. Первый пункт маркированного списка).
  • Когда значения так aи sнайдены таковы g(n, a, s-a) == True, то это значение возвращается. Поскольку возможные решения подсчитываются в порядке «размера» (отсортированного по среднему значению, а затем по минимальному значению), первое найденное решение всегда будет наименьшим, как требует запрос.

R , 183 байт 160 байт

n=scan();e=expand.grid(n:0,n:0);e=e[e[,2]>e[,1],];r=e[mapply(h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),n,e[,1],e[,2]),];r[which.min(rowSums(r)),]

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

Спасибо Джузеппе за игру в гольф на 23 байта

Объяснение кода

n=scan()                        #STDIO input
e=expand.grid(n:0,n:0)          #full outer join of integer vector n to 0
e=e[e[,2]>e[,1],]               #filter so b > a
r=e[mapply(
  h<-function(n,a,b,r=a+b)switch(sign(n-r)+2,F,T,h(n,b,r)),
                                #create a named recursive function mid-call 
                                #(requires using <- vs = to denote local variable creation 
                                #rather than argument assignment
  n,e[,1],e[,2]),]              #map n, a and b to h() which returns a logical
                                #which is used to filter the possibilities
r[which.min(rowSums(r)),]       #calculate sum for each possibility, 
                                #get index of the minimum and return
                                #because each possibility has 2 values, the mean and 
                                #sum will sort identically.

Mathematica, 117 байт

If[#==1,{0,1},#&@@SortBy[(S=Select)[S[Range[0,s=#]~Tuples~2,Less@@#&],!FreeQ[LinearRecurrence[{1,1},#,s],s]&],Mean]]&

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

Желе , 19 байт

ṫ-Sṭµ¡³e
0rŒcÇÐfSÐṂ

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

-1 байт благодаря доказательства по cardboard_box . В случае, если это опровергнуто, вы можете добавить UṂṚв конец второй строки в общей сложности 22 байта.

GolfScript - 88 77 байт

~:N[,{1+:a,{[.;a]}/}/][{[.~{.N<}{.@+}while\;N=]}/]{)1=\;},{(\;~+}$(\;);~~' '\

Я не проверял множественные решения, благодаря картонная коробка!

объяснение

~:N                           # Reads input
[,{1+:a,{[.;a]}/}/]           # Creates an array of pairs [a b]
[{[.~{.N<}{.@+}while\;N=]}/]  # Compute solutions
{)1=\;},         # Pairs that are not solutions are discarded
{(\;~+}$         # Sorts by mean
(\;);~~' '\      # Formats output

Пакетное, 160 158 байт

@set/aa=b=0
:g
@if %a% geq %b% set/ab-=~a,a=0
@set/ac=a,d=b
:l
@if %c% lss %1 set/ad+=c,c=d-c&goto l
@if %c% gtr %1 set/aa+=1,b-=1&goto g
@echo %a% %b%