Biorąc pod uwagę dodatnią liczbę całkowitą wejściową N , wyślij dwie liczby nieujemne, a i b , gdzie a <b , z najniższą możliwą wartością średnią, która spowoduje, że liczba N będzie częścią powtarzającej się sekwencji relacji:

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

W przypadku, gdy istnieje więcej niż jedno rozwiązanie, w którym średnia a i b jest minimalna, powinieneś wypisać jedno z najniższym b .

Możesz założyć, że N jest w reprezentatywnym zakresie liczb całkowitych w twoim języku / systemie.

Przypadki testowe

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

Łuska , 19 18 16 14 13 15 bajtów

Dzięki Zgarb za uratowanie 1 bajtu.

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

Wypróbuj online!

Wyjaśnienie:

Oświadczenie: Naprawdę nie rozumiem ȯƒẊ++części kodu.

Edycja: Wygląda na to, że tłumaczy się na Haskell fix.(mapad2(+).).(++), gdzie mapad2jest stosowana funkcja do wszystkich sąsiednich par na liście. (Chociaż znając Husk, w kontekście tego programu może to oznaczać coś innego)

            Θḣ⁰    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 bajtów

-3 bajty -1 bajt dzięki ThePirateBay

-8 -9 bajtów dzięki Neilowi.

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]

Wypróbuj online!

Uwaga: to rozwiązanie polega na tym, że nigdy nie ma wielu minimalnych rozwiązań.

Dowód, że nigdy nie ma wielu rozwiązań:

Niech FIB(a,b,k)będzie sekwencją Fibonacciego zaczynającą się od 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)

Lemat 1

Różnica między sekwencjami podobnymi do Fibonacciego jest sama w sobie podobna do Fibonacciego, tj FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k) . Dowód pozostawiono czytelnikowi.

Lemat 2

Na n >= 5roztwór a,bistnieje spełniającycha+b < n :

jeśli njest nawetFIB(0,n/2,3) = n

jeśli njest dziwne,FIB(1,(n-1)/2,3) = n

Dowód

Przypadki, w których n < 5można dokładnie sprawdzić.

Załóżmy, że mamy dwa rozwiązania minimalne n >= 5, a0,b0a a1,b1z a0 + b0 = a1 + b1a a0 != a1.

Potem istnieją k0,k1takie, że FIB(a0,b0,k0) = FIB(a1,b1,k1) = n.

• Przypadek 1: k0 = k1

  Założono WLOG b0 < b1(i dlategoa0 > a1 )

  Niech DIFF(k)będzie różnica między sekwencjami podobnymi do Fibonnaci zaczynającymi się od a1,b1i a0,b0:

  DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k) (Lemat 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

  Gdy sekwencja podobna do Fibonnaci ma 2 dodatnie wyrażenia, wszystkie kolejne wyrażenia są dodatnie.

  Zatem jedynym momentem DIFF(k) = 0jest kiedy k = 2, więc jedynym wyborem k0 = k1jest2 .

  W związku z tym n = FIB(a0,b0,2) = a0 + b0 = a1 + b1

  Minimalność tych rozwiązań stoi w sprzeczności z Lemat 2.

• Przypadek 2 k0 != k1:

  Założono WLOG k0 < k1.

  Mamy FIB(a1,b1,k1) = n

  Pozwolić a2 = FIB(a1,b1,k1-k0)

  Pozwolić b2 = FIB(a1,b1,k1-k0+1)

  Następnie FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0)(ćwiczenie dla czytelnika)

  Ponieważ FIB(a1,b1,k)nie jest ujemny k >= 0, nie zmniejsza się.

  To daje nam a2 >= b1 > a0i b2 >= a1+b1 = a0+b0.

  Więc pozwól DIFF(k) = FIB(a2,b2,k) - FIB(a0,b0,k) = FIB(a2-a0,b2-b0,k)(Lemma 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

  Jeszcze raz DIFFma 2 pozytywne warunki, a zatem wszystkie kolejne warunki są pozytywne.

  Tak więc, tylko czas, kiedy jest to możliwe, że DIFF(k) = 0jest k = 1, więc jedynym wyborem k0jest 1.

  FIB(a0,b0,1) = n

  b0 = n

  Jest to sprzeczne z Lemma 2.

Haskell , 76 72 74 bajty

EDYTOWAĆ:

• -4 bajty: @ H.PWiz sugeruje użycie /zamiast div, chociaż wymaga to użycia liczb ułamkowych.
• +2 bajty: Naprawiono błąd z Enumzakresami poprzez dodanie -1.

fprzyjmuje wartość Doublelub Rationaltyp i zwraca krotkę tego samego. Doublepowinien wystarczyć dla wszystkich wartości, które nie są wystarczająco duże, aby powodować błędy zaokrąglania, podczas gdy Rationaljest teoretycznie nieograniczony.

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

Wypróbuj online! (z korektami nagłówka H.PWiz na wejściu / wyjściuRational w formacie liczb całkowitych)

Jak to działa

• ?jest lokalnie zagnieżdżonym operatorem w zakresie f. a?brekurencyjnie przechodzi przez sekwencję podobną do Fibonacciego, zaczynając od, a,baż b>=n, zwracając Trueiff trafia ndokładnie.
• W rozumieniu listy:
  • siteruje wszystkie liczby od 1góry, reprezentując sumę ai b.
  • aiteruje liczby od 0do s/2-1. (Jeśli sjest nieparzysty, koniec zakresu zaokrągla w górę.)
  • a?(s-a)sprawdza, czy sekwencja zaczyna się od a,s-atrafień n. Jeśli tak, lista zawiera krotkę (a,s-a). (To znaczy, b=s-achociaż było zbyt krótkie, aby warto było je nazwać.)
  • !!0 wybiera pierwszy element (trafienie) w zrozumieniu.

APL (Dyalog) , 75 71 64 59 53 48 44 43 bajty

2 bajty zapisane dzięki @ Adám

12 bajtów zapisanych dzięki @ngn

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

Wypróbuj online!

Zastosowania ⎕IO←0.

W jaki sposób? To oszalało.

k←⎕ - przypisz wejście do k

⍳2⍴1+k←⎕- Kartezjański produkt z zakresu 0do ksiebie

|-\¨ - odejmij każdy prawy element pary od lewej i uzyskaj wartości bezwzględne

a←,⍉ - transponuj, spłaszcz i przypisz do a

o←a/⍨</¨a - trzymaj tylko pary, w których lewy element jest mniejszy niż prawy, i przypisz do o

oteraz zawiera listę wszystkich par a < b, uporządkowanych według ich średniej arytmetycznej

+\∘⌽⍣{k≤⊃⍺}¨o- dla każdej pary ozastosuj fibonacciego (odwróć parę i sumę) aż do osiągnięcia klub wyższej wartości

k∊¨- następnie zdecyduj, czy kjest to ostatni termin (co oznacza, że ​​jest zawarty w sekwencji)

o/⍨- i trzymaj pary otam, gdzie ma zastosowanie poprzednia kontrola

⊃ - zwróć pierwszy wynik.

Python 2 , 127 109 107 bajtów

-2 bajty dzięki ovs (zmiana andna *)

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

Wypróbuj online!

Jakieś punkty bonusowe n,a,s-a?

Wyjaśnienie:

• W pierwszym wierszu deklarowana jest rekurencyjna lambda, gktóra weryfikuje, czy a, brozwinięta jako sekwencja Fibonacciego osiągnie x. Sprawdza również, czy jest to a <= bjedno z kryteriów pytania. (Pozwoliłoby to na przypadki gdzie a == b, ale w takim przypadku 0, azostałyby już odkryte i zwrócone).
  • Łańcuchowa nierówność a<=b<xwykonuje jednocześnie dwa przydatne zadania: weryfikację a <= bi tob < x .
  • Jeśli b < xdaje True, funkcja wywołuje się ponownie z następnymi dwoma liczbami w sekwencji Fibonacciego:b, a+b . Oznacza to, że funkcja będzie opracowywać nowe warunki, dopóki ...
  • Jeśli dajemy b < xplony False, osiągnęliśmy punkt, w którym musimy sprawdzić, czy b==x. Jeśli tak, to wróci True, co oznacza, że ​​początkowa para w a, bkońcu osiągnie x. W przeciwnym razie, jeśli b > xpara jest nieprawidłowa.
• Druga linia deklaruje inną rekurencyjną lambda f, która znajduje rozwiązanie dla danej wartości n. Rekurencyjnie wypróbowuje nowe pary początkowe a, b, aż do g(n, a, b)uzyskania wyników True. To rozwiązanie jest następnie zwracane.
  • Funkcja rekurencyjnie zlicza początkowe pary Fibonacciego za pomocą dwóch zmiennych, s(początkowo 1) i a(początkowo 0). Przy każdej iteracji ajest zwiększana i a, s-ajest używana jako pierwsza para. Jednak po atrafienius jest resetowane z powrotem do 0 i sjest zwiększane. Oznacza to, że pary są zliczane według następującego wzoru:

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

    Oczywiście zawiera kilka nieprawidłowych par, jednak są one eliminowane natychmiast po przekazaniu do g(patrz pierwszy punkt).
  • Gdy wartości ai szostaną znalezione g(n, a, s-a) == True, to ta wartość jest zwracana. Ponieważ możliwe rozwiązania są zliczane w kolejności według „wielkości” (posortowane według wartości, a następnie wartości minimalnej), pierwsze znalezione rozwiązanie będzie zawsze najmniejsze, zgodnie z żądaniem wyzwania.

R , 183 bajtów 160 bajtów

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

Wypróbuj online!

Dzięki Giuseppe za grę w golfa przy 23 bajtach

Wyjaśnienie kodu

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 bajtów

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

Wypróbuj online!

Galaretka , 19 bajtów

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

Wypróbuj online!

Dzięki -1 bajt dowodu przez cardboard_box . W przypadku odrzucenia możesz dołączyć UṂṚna końcu drugiej linii łącznie 22 bajty.

GolfScript - 88 77 bajtów

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

Nie sprawdziłem wielu rozwiązań dzięki kartonowi!

Wyjaśnienie

~: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

Partia, 160 158 bajtów

@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%