Самые низкие начальные числа в последовательности, подобной Фибоначчи

22

Учитывая положительный целочисленный ввод 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
Стьюи Гриффин
источник
Если a>=0и a<bесть когда - либо несколько решений?
Джонатан Аллан
Я не могу гарантировать, что есть или нет несколько решений. И то 1,4и другое 2,3дадут 5, и они имеют одинаковое значение. Я предполагаю, что можно найти случаи, подобные этому, где это самые низкие средние значения. Если вы можете показать / доказать, что не существует нескольких решений, вам не нужно проверять это условие.
Стьюи Гриффин
2
полностью вдохновлен codegolf.stackexchange.com/q/147200/67961
J42161217
3
Соответствующая последовательность OEIS для наименьшего возможного среднего, A249783 , имеет дикий вид графика .
Питер Кейджи
1
@ ØrjanJohansen Я добавил в свой ответ доказательство отсутствия дублирующих решений (поскольку мой ответ зависел от него).
картонная

Ответы:

8

Шелуха , 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)?
H.PWiz
источник
Я уверен, что попробовал это ...
H.PWiz
8

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.

картонная коробка
источник
1
77 байтов
Нейл
@Neil Это минимизирует, bа не минимизирует a+b, и, следовательно, ваше решение дает, f(27) = [3,7]но оптимальное решение есть f(27)=[0,9]. После отмены критических изменений мы сократили до 83 байтов.
картонная
1
Я думаю, что вы можете сохранить другой байт, используя b-~aвместо a+b+1.
Нил
1
Во втором случае a2 >= a1 + b1есть небольшая ошибка: не правильно, когда k1-k0=1. Вместо этого вы можете использовать a2 >= b1 > a0и b2 >= a1+b1 = a0+b0, а затем остальное следует.
Орджан Йохансен
8

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 выбирает первый элемент (хит) в понимании.
Орджан Йохансен
источник
8

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

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

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

o/⍨k∊¨+\∘⌽⍣{k≤⊃⍺}¨oa/⍨</¨a←,⍉|-21+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там, где применяется предыдущая проверка

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

Уриэль
источник
5

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, то это значение возвращается. Поскольку возможные решения подсчитываются в порядке «размера» (отсортированного по среднему значению, а затем по минимальному значению), первое найденное решение всегда будет наименьшим, как требует запрос.
FlipTack
источник
3

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.
отметка
источник
1
160 байт - в общем, вы должны сохранять байты везде, где можете, поэтому сохранение 4 байтов путем удаления хороших имен не только приемлемо или поощряется, но в некотором смысле требуется для code-golf . Несмотря на это, хороший ответ +1.
Джузеппе
1

Желе , 19 байт

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

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

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

Эрик Аутгольфер
источник
... ведущее увеличение должно разрешить наблюдение @ StewieGriffin.
Джонатан Аллан
У меня есть чувство, что вы можете бросить
Джонатан Аллан
1
Нам нужно только найти начальное число, которое делает ввод xпоследним. Если бы он x был найден в третьем индексе для множественного числа, то он работает 0,xи, следовательно, будет работать либо в 1,(x-1)/2( xнечетном), либо 2,x/2-1( xчетном), после чего xв результате появится позже, так что этого не произойдет. Для более позднего столкновения среднее значение может быть таким же, только если третьи слагаемые тоже одинаковы, но тогда нужно иметь меньшую разницу между начальными слагаемыми (иначе они будут одинаковыми) и, следовательно, будет xнайдено по более позднему индексу , Таким образом, мы можем ṫ-Sṭµ¡i³¶ḶŒcÇÐṀсэкономить четыре байта.
Джонатан Аллан
... упс, плюс прирост:ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
Джонатан Аллан
@StewieGriffin Этого тестового примера не было, когда я ответил: p
Эрик Outgolfer
1

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
FedeWar
источник
Попробуйте онлайн!
Орджан Йохансен,
0

Пакетное, 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%
Нил
источник
Это (также) дает 3 7на входе 27. Правильное решение есть 0 9.
картонная
@cardboard_box Все еще не вижу, где вопрос требует этого ...
Нил
В первом предложении: «с минимально возможным средним значением».
картонная
@cardboard_box Ах, извините, это было слишком легко пропустить.
Нил
1
@cardboard_box OK должен быть исправлен.
Нил