Najniższe liczby początkowe w sekwencji podobnej do Fibonacciego

22

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
Stewie Griffin
źródło
Czy a>=0i a<bczy kiedykolwiek istnieje wiele rozwiązań?
Jonathan Allan
Nie mogę zagwarantować, że istnieje wiele rozwiązań. Oba 1,4i 2,3dawałyby 5, i mają ten sam środek. Wydaje mi się, że można znaleźć przypadki podobne do tego, w których są to najniższe wartości średnie. Jeśli możesz pokazać / udowodnić, że nie ma wielu rozwiązań, nie musisz sprawdzać tego warunku.
Stewie Griffin
2
całkowicie zainspirowany codegolf.stackexchange.com/q/147200/67961
J42161217
3
Odpowiednia sekwencja OEIS dla najniższej możliwej wartości, A249783 , ma dziko wyglądający wykres .
Peter Kagey,
1
@ ØrjanJohansen Dodałem dowód do mojej odpowiedzi, że nie ma duplikatów rozwiązań (ponieważ moja odpowiedź zależała od tego).
cardboard_box

Odpowiedzi:

8

Ł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)?
H.PWiz
źródło
Jestem pewien, że próbowałem ...
H.PWiz
8

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.

pudełko kartonowe
źródło
1
77 bajtów
Neil,
@ Neil To minimalizuje bzamiast minimalizować a+b, a zatem twoje rozwiązanie daje, f(27) = [3,7]ale optymalnym rozwiązaniem jest f(27)=[0,9]. Po cofnięciu przełomowych zmian zmniejszamy się do 83 bajtów.
cardboard_box
1
Myślę, że możesz zapisać kolejny bajt, używając b-~azamiast a+b+1.
Neil,
1
W twoim drugim przypadku a2 >= a1 + b1jest mały błąd: nie jest poprawny, kiedy k1-k0=1. Zamiast tego możesz użyć a2 >= b1 > a0i b2 >= a1+b1 = a0+b0, a następnie reszta nastąpi.
Ørjan Johansen
8

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,bb>=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.
Ørjan Johansen
źródło
8

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≤⊃⍺}¨oa/⍨</¨a←,⍉|-21+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.

Uriel
źródło
5

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.
FlipTack
źródło
3

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.
znak
źródło
1
160 bajtów - ogólnie rzecz biorąc, powinieneś zapisywać bajty gdziekolwiek możesz, więc oszczędzanie 4 bajtów przez usunięcie ładnej nazwy jest nie tylko dopuszczalne lub zalecane, ale w pewnym sensie wymagane przez code-golfa . Mimo to fajna odpowiedź, +1.
Giuseppe,
1

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!

J42161217
źródło
1

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.

Erik the Outgolfer
źródło
... wiodący przyrost powinien rozwiązać obserwację @ StewieGriffin.
Jonathan Allan
Mam wrażenie, że możesz upuścić
Jonathan Allan
1
Musimy tylko znaleźć ziarno, które sprawia, że ​​dane wejściowe xpojawiają się najpóźniej. Jeśli x zostaną znalezione przy trzecim indeksie dla wielu, to działa dla 0,xi dlatego też będzie działał w 1,(x-1)/2( xnieparzystym) lub 2,x/2-1( xparzystym), po czym xpojawiłby się później w wyniku, aby tak się nie stało. W przypadku późniejszej kolizji średnia może być taka sama, jeśli trzecie warunki też są takie same, ale wtedy trzeba mieć mniejszą różnicę między początkowymi warunkami (w przeciwnym razie byłyby takie same), a zatem można xznaleźć przy późniejszym indeksie . Jako taki możemy ṫ-Sṭµ¡i³¶ḶŒcÇÐṀzaoszczędzić cztery bajty.
Jonathan Allan,
... ups, plus przyrost:ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
Jonathan Allan,
@StewieGriffin Ten przypadek testowy nie istniał, gdy odpowiedziałem: p
Erik the Outgolfer
1

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
FedeWar
źródło
Wypróbuj online!
Ørjan Johansen
0

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%
Neil
źródło
To (także) daje 3 7na wejściu 27. Prawidłowe rozwiązanie to 0 9.
cardboard_box
@cardboard_box Nadal nie widzę, gdzie pytanie wymaga, aby ...
Neil,
W pierwszym zdaniu: „o najniższej możliwej wartości średniej”.
cardboard_box
@cardboard_box Ach, przepraszam, to było zbyt łatwe do przeoczenia.
Neil,
1
@ cardboard_box OK powinien zostać teraz naprawiony.
Neil,