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
a>=0
ia<b
czy kiedykolwiek istnieje wiele rozwiązań?1,4
i2,3
dawałyby5
, 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.Odpowiedzi:
Łuska ,
191816141315 bajtówDzięki Zgarb za uratowanie 1 bajtu.
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(+).).(++)
, gdziemapad2
jest 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)źródło
JavaScript (Node.js) ,
92 90 89 91 8382 bajtów-3 bajty-1 bajt dzięki ThePirateBay-8-9 bajtów dzięki Neilowi.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ę oda,b
: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 >= 5
roztwóra,b
istnieje spełniającycha+b < n
:jeśli
n
jest nawetFIB(0,n/2,3) = n
jeśli
n
jest dziwne,FIB(1,(n-1)/2,3) = n
Dowód
Przypadki, w których
n < 5
można dokładnie sprawdzić.Załóżmy, że mamy dwa rozwiązania minimalne
n >= 5
,a0,b0
aa1,b1
za0 + b0 = a1 + b1
aa0 != a1
.Potem istnieją
k0,k1
takie, żeFIB(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ę oda1,b1
ia0,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) = 0
jest kiedyk = 2
, więc jedynym wyboremk0 = k1
jest2
.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 ujemnyk >= 0
, nie zmniejsza się.To daje nam
a2 >= b1 > a0
ib2 >= 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
DIFF
ma 2 pozytywne warunki, a zatem wszystkie kolejne warunki są pozytywne.Tak więc, tylko czas, kiedy jest to możliwe, że
DIFF(k) = 0
jestk = 1
, więc jedynym wyboremk0
jest1
.FIB(a0,b0,1) = n
b0 = n
Jest to sprzeczne z Lemma 2.
źródło
b
zamiast minimalizowaća+b
, a zatem twoje rozwiązanie daje,f(27) = [3,7]
ale optymalnym rozwiązaniem jestf(27)=[0,9]
. Po cofnięciu przełomowych zmian zmniejszamy się do 83 bajtów.b-~a
zamiasta+b+1
.a2 >= a1 + b1
jest mały błąd: nie jest poprawny, kiedyk1-k0=1
. Zamiast tego możesz użyća2 >= b1 > a0
ib2 >= a1+b1 = a0+b0
, a następnie reszta nastąpi.Haskell ,
76 7274 bajtyEDYTOWAĆ:
/
zamiastdiv
, chociaż wymaga to użycia liczb ułamkowych.Enum
zakresami poprzez dodanie-1
.f
przyjmuje wartośćDouble
lubRational
typ i zwraca krotkę tego samego.Double
powinien wystarczyć dla wszystkich wartości, które nie są wystarczająco duże, aby powodować błędy zaokrąglania, podczas gdyRational
jest teoretycznie nieograniczony.Wypróbuj online! (z korektami nagłówka H.PWiz na wejściu / wyjściu
Rational
w formacie liczb całkowitych)Jak to działa
?
jest lokalnie zagnieżdżonym operatorem w zakresief
.a?b
rekurencyjnie przechodzi przez sekwencję podobną do Fibonacciego, zaczynając od,a,b
ażb>=n
, zwracającTrue
iff trafian
dokładnie.s
iteruje wszystkie liczby od1
góry, reprezentując sumęa
ib
.a
iteruje liczby od0
dos/2-1
. (Jeślis
jest nieparzysty, koniec zakresu zaokrągla w górę.)a?(s-a)
sprawdza, czy sekwencja zaczyna się oda,s-a
trafieńn
. Jeśli tak, lista zawiera krotkę(a,s-a)
. (To znaczy,b=s-a
chociaż było zbyt krótkie, aby warto było je nazwać.)!!0
wybiera pierwszy element (trafienie) w zrozumieniu.źródło
APL (Dyalog) ,
7571645953484443 bajty2 bajty zapisane dzięki @ Adám
12 bajtów zapisanych dzięki @ngn
Wypróbuj online!
Zastosowania
⎕IO←0
.W jaki sposób? To oszalało.
k←⎕
- przypisz wejście dok
⍳2⍴1+k←⎕
- Kartezjański produkt z zakresu0
dok
siebie|-\¨
- odejmij każdy prawy element pary od lewej i uzyskaj wartości bezwzględnea←,⍉
- transponuj, spłaszcz i przypisz doa
o←a/⍨</¨a
- trzymaj tylko pary, w których lewy element jest mniejszy niż prawy, i przypisz doo
o
teraz zawiera listę wszystkich para < b
, uporządkowanych według ich średniej arytmetycznej+\∘⌽⍣{k≤⊃⍺}¨o
- dla każdej paryo
zastosuj fibonacciego (odwróć parę i sumę) aż do osiągnięciak
lub wyższej wartościk∊¨
- następnie zdecyduj, czyk
jest to ostatni termin (co oznacza, że jest zawarty w sekwencji)o/⍨
- i trzymaj paryo
tam, gdzie ma zastosowanie poprzednia kontrola⊃
- zwróć pierwszy wynik.źródło
Python 2 ,
127109107 bajtów-2 bajty dzięki ovs (zmiana
and
na*
)Wypróbuj online!
Jakieś punkty bonusowe
n,a,s-a
?Wyjaśnienie:
g
która weryfikuje, czya, b
rozwinięta jako sekwencja Fibonacciego osiągniex
. Sprawdza również, czy jest toa <= b
jedno z kryteriów pytania. (Pozwoliłoby to na przypadki gdziea == b
, ale w takim przypadku0, a
zostałyby już odkryte i zwrócone).a<=b<x
wykonuje jednocześnie dwa przydatne zadania: weryfikacjęa <= b
i tob < x
.b < x
dajeTrue
, 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 ...b < x
plonyFalse
, osiągnęliśmy punkt, w którym musimy sprawdzić, czyb==x
. Jeśli tak, to wróciTrue
, co oznacza, że początkowa para wa, b
końcu osiągniex
. W przeciwnym razie, jeślib > x
para jest nieprawidłowa.f
, która znajduje rozwiązanie dla danej wartościn
. Rekurencyjnie wypróbowuje nowe pary początkowea, b
, aż dog(n, a, b)
uzyskania wynikówTrue
. To rozwiązanie jest następnie zwracane.s
(początkowo 1) ia
(początkowo 0). Przy każdej iteracjia
jest zwiększana ia, s-a
jest używana jako pierwsza para. Jednak poa
trafienius
jest resetowane z powrotem do 0 is
jest zwiększane. Oznacza to, że pary są zliczane według następującego wzoru: Oczywiście zawiera kilka nieprawidłowych par, jednak są one eliminowane natychmiast po przekazaniu dog
(patrz pierwszy punkt).a
is
zostaną znalezioneg(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ódło
R ,
183 bajtów160 bajtówWypróbuj online!
Dzięki Giuseppe za grę w golfa przy 23 bajtach
Wyjaśnienie kodu
źródło
Mathematica, 117 bajtów
Wypróbuj online!
źródło
Galaretka , 19 bajtów
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.źródło
Ḣ
x
pojawiają się najpóźniej. Jeślix
zostaną znalezione przy trzecim indeksie dla wielu, to działa dla0,x
i dlatego też będzie działał w1,(x-1)/2
(x
nieparzystym) lub2,x/2-1
(x
parzystym), po czymx
pojawił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żnax
znaleźć przy późniejszym indeksie . Jako taki możemyṫ-Sṭµ¡i³¶ḶŒcÇÐṀ
zaoszczędzić cztery bajty.ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
GolfScript -
8877 bajtówNie sprawdziłem wielu rozwiązań dzięki kartonowi!
Wyjaśnienie
źródło
Partia,
160158 bajtówźródło
3 7
na wejściu27
. Prawidłowe rozwiązanie to0 9
.