Bei einer positiven Ganzzahleingabe N geben Sie die beiden nicht-negativen Zahlen a und b aus , wobei a <b ist und der kleinstmögliche Mittelwert vorliegt, der zur Folge hat, dass die Zahl N Teil der wiederkehrenden Beziehungsfolge ist:
f(0) = a
f(1) = b
f(n) = f(n-2)+f(n-1)
Falls es mehr als eine Lösung gibt, bei der der Mittelwert von a und b minimal ist, sollten Sie die mit dem niedrigsten b ausgeben .
Sie können davon ausgehen, dass N innerhalb des repräsentativen Bereichs von ganzen Zahlen in Ihrer Sprache / Ihrem System liegt.
Testfälle
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
unda<b
gibt es jemals mehrere Lösungen?1,4
und2,3
würde geben5
, und sie haben den gleichen Mittelwert. Ich denke, es ist möglich, Fälle zu finden, die denen ähneln, bei denen es sich um die niedrigsten Mittelwerte handelt. Wenn Sie nachweisen können, dass es nicht mehrere Lösungen gibt, müssen Sie diese Bedingung nicht überprüfen.Antworten:
Schale ,
191816141315 BytesDanke Zgarb für das Speichern von 1 Byte.
Probieren Sie es online!
Erläuterung:
Haftungsausschluss: Ich verstehe den
ȯƒẊ++
Abschnitt des Codes wirklich nicht .Bearbeiten: Es scheint sich um die Haskell zu handeln
fix.(mapad2(+).).(++)
, bei dermapad2
die Funktion auf alle benachbarten Paare in einer Liste angewendet wird. (Obwohl, wenn man Husk kennt, im Kontext dieses Programms etwas anderes bedeuten könnte)quelle
JavaScript (Node.js) ,
92 90 89 91 8382 Byte-3 Bytes-1 Bytes dank ThePirateBay-8-9 Bytes dank Neil.Probieren Sie es online!
Hinweis: Diese Lösung beruht auf der Tatsache, dass es niemals mehrere Minimallösungen gibt.
Beweise, dass es nie mehrere Lösungen gibt:
Sei
FIB(a,b,k)
die Fibonacci-ähnliche Sequenz beginnend mita,b
:Lemma 1
Der Unterschied zwischen Fibonacci-ähnlichen Sequenzen ist selbst Fibonacci-ähnlich, dh
FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k)
. Der Beweis bleibt dem Leser überlassen.Lemma 2
Denn es
n >= 5
gibt eine Lösung,a,b
die erfüllta+b < n
:wenn gerade
n
ist,FIB(0,n/2,3) = n
wenn
n
ungerade ist,FIB(1,(n-1)/2,3) = n
Beweis
Fälle, in denen umfassend
n < 5
geprüft werden kann.Angenommen , wir haben zwei minimale Lösungen für
n >= 5
,a0,b0
unda1,b1
mita0 + b0 = a1 + b1
unda0 != a1
.Dann gibt es
k0,k1
so etwasFIB(a0,b0,k0) = FIB(a1,b1,k1) = n
.Fall 1:
k0 = k1
WLOG annehmen
b0 < b1
(und dahera0 > a1
)Sei
DIFF(k)
der Unterschied zwischen den Fibonnaci-ähnlichen Sequenzen beginnend mita1,b1
unda0,b0
:DIFF(k) = FIB(a1,b1,k) - FIB(a0,b0,k) = FIB(a1-a0,b1-b0,k)
(Lemma 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
Sobald eine Fibonnaci-ähnliche Sequenz 2 positive Terme hat, sind alle nachfolgenden Terme positiv.
Somit ist die einzige Zeit
DIFF(k) = 0
ist , wennk = 2
, so dass die einzige Wahl fürk0 = k1
ist2
.Deshalb
n = FIB(a0,b0,2) = a0 + b0 = a1 + b1
Die Minimalität dieser Lösungen widerspricht Lemma 2.
Fall 2
k0 != k1
:WLOG annehmen
k0 < k1
.Wir haben
FIB(a1,b1,k1) = n
Lassen
a2 = FIB(a1,b1,k1-k0)
Lassen
b2 = FIB(a1,b1,k1-k0+1)
Dann
FIB(a2,b2,k0) = FIB(a1,b1,k1) = FIB(a0,b0,k0)
(Übung für den Leser)Da
FIB(a1,b1,k)
es für nicht negativ istk >= 0
, ist es auch nicht abnehmend.Das gibt uns
a2 >= b1 > a0
undb2 >= a1+b1 = a0+b0
.Dann lass
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
Hat wieder
DIFF
2 positive Ausdrücke und daher sind alle nachfolgenden Ausdrücke positiv.Wenn also die einzige Zeit , möglich ist es , das
DIFF(k) = 0
istk = 1
, so dass die einzige Wahl fürk0
ist1
.FIB(a0,b0,1) = n
b0 = n
Dies widerspricht Lemma 2.
quelle
b
anstatt zu minimierena+b
, und somit gibt deine Lösungf(27) = [3,7]
doch die optimale Lösungf(27)=[0,9]
. Nachdem wir die Änderungen rückgängig gemacht haben, sind wir auf 83 Bytes gesunken.b-~a
anstelle von verwendena+b+1
.a2 >= a1 + b1
nicht , wenn korrigieren wirdk1-k0=1
. Stattdessen können Siea2 >= b1 > a0
und verwendenb2 >= a1+b1 = a0+b0
, und dann folgt der Rest.Haskell ,
76 7274 BytesBEARBEITEN:
/
anstelle vondiv
, obwohl dies die Verwendung eines Typs mit gebrochenen Zahlen erfordert.Enum
Bereichen durch Hinzufügen wurde behoben-1
.f
Nimmt einen Wert vonDouble
oderRational
Typ und gibt ein Tupel desselben zurück.Double
sollte für alle Werte ausreichen, die nicht groß genug sind, um Rundungsfehler zu verursachen, während sieRational
theoretisch unbegrenzt sind.Probieren Sie es online!(mit H.PWiz's Header Anpassungen an Input / Output
Rational
s im Integer Format)Wie es funktioniert
?
ist ein lokal verschachtelter Operator im Bereich vonf
.a?b
Durchläuft rekursiv die Fibonacci-ähnliche Sequenz, beginnend mita,b
bisb>=n
, und kehrt zurückTrue
iff" wenn sien
genau trifft .s
Durchläuft alle Zahlen von1
oben nach unten und repräsentiert die Summe vona
undb
.a
durchläuft die Zahlen von0
biss/2-1
. (Obs
ungerade ist, wird das Bereichsende aufgerundet.)a?(s-a)
testet, ob die Sequenz mita,s-a
Treffern beginntn
. Wenn ja, enthält das Listenverständnis das Tupel(a,s-a)
. (Das ist,b=s-a
obwohl es zu kurz war, um es zu nennen.)!!0
Wählt das erste Element (Treffer) im Verständnis aus.quelle
APL (Dyalog) ,
7571645953484443 Bytes2 Bytes gespart dank @ Adám
Dank @ngn werden 12 Bytes gespeichert
Probieren Sie es online!
Verwendet
⎕IO←0
.Wie? Das war echt verrückt geworden.
k←⎕
- Eingang zuordnen zuk
⍳2⍴1+k←⎕
- Kartesisches Produkt der Reihe0
bisk
mit sich|-\¨
- subtrahiere jedes rechte Paarelement von dem linken und erhalte absolute Wertea←,⍉
- transponieren, abflachen und zuweisena
o←a/⍨</¨a
- Behalten Sie nur Paare bei, bei denen das linke Element kleiner als das rechte ist, und weisen Sie es zuo
o
enthält nun eine Liste aller Paare mita < b
, geordnet nach ihrem arithematischen Mittelwert+\∘⌽⍣{k≤⊃⍺}¨o
-o
Wenden Sie für jedes Paar in Fibonacci an (vertauschen Sie das Paar und Cumsum), bis einek
höhere Laufzeit erreicht istk∊¨
- Entscheide dann, obk
es sich um den letzten Begriff handelt (dh, er ist in der Sequenz enthalten)o/⍨
- und bewahren Sie Paare dort auf,o
wo die vorherige Überprüfung zutrifft⊃
- das erste Ergebnis zurückgeben.quelle
Python 2 ,
127109107 Bytes-2 Bytes dank ovs (ändern
and
auf*
)Probieren Sie es online!
Irgendwelche Bonuspunkte für
n,a,s-a
?Erläuterung:
g
das überprüft, ob esa, b
als Fibonacci-Sequenz expandiert wirdx
. Es überprüft auch, dassa <= b
eines der Kriterien der Frage. (Dies würde Fälle ermöglichen, in denena == b
aber in einem solchen Fall0, a
bereits entdeckt und zurückgegeben worden wäre).a<=b<x
führt zwei nützliche Aufgaben gleichzeitig aus: Verifizierena <= b
und dasb < x
.b < x
ergibtTrue
, ruft sich die Funktion erneut mit den nächsten beiden Zahlen in der Fibonacci-Folge auf:b, a+b
. Dies bedeutet, dass die Funktion so lange neue Begriffe ausarbeitet, bis ...b < x
RenditenFalse
, dann haben wir den Punkt erreicht, an dem wir prüfen müssen, obb==x
. In diesemTrue
Fall wird dies zurückgegeben , was bedeutet, dass das ursprüngliche Paara, b
schließlich erreicht wirdx
. Andernfalls istb > x
das Paar ungültig.f
das die Lösung für einen bestimmten Wert findetn
. Es versucht rekursiv neue Anfangspaarea, b
, bis sichg(n, a, b)
ergibtTrue
. Diese Lösung wird dann zurückgegeben.s
(anfänglich 1) unda
(anfänglich 0). Bei jeder Iterationa
wird inkrementiert unda, s-a
als erstes Paar verwendet. Wenn jedocha
triffts
wird es jedoch auf 0 zurückgesetzt unds
inkrementiert. Dies bedeutet, dass die Paare nach folgendem Muster hochgezählt werden: Offensichtlich enthält dies einige ungültige Paare, diese werden jedoch sofort gelöscht, wenn sie an übergeben werdeng
(siehe ersten Aufzählungspunkt).a
unds
so gefunden werden,g(n, a, s-a) == True
wird dieser Wert zurückgegeben. Da die möglichen Lösungen in der Reihenfolge "Größe" (sortiert nach Mittelwert und anschließend nach Mindestwert) hochgezählt werden, ist die zuerst gefundene Lösung immer die kleinste, da die Herausforderung dies erfordert.quelle
R ,
183 Bytes160 BytesProbieren Sie es online!
Danke an Giuseppe für das Golfen mit 23 Bytes
Code Erklärung
quelle
Mathematica, 117 Bytes
Probieren Sie es online!
quelle
Jelly , 19 Bytes
Probieren Sie es online!
-1 Byte dank des Proofs von cardboard_box . Falls dies widerlegt wird, können Sie
UṂṚ
insgesamt 22 Byte an das Ende der zweiten Zeile anhängen .quelle
Ḣ
x
und der als letztes angezeigt wird. Wennx
es beim dritten Index für multiple gefunden würde, dann funktioniert es für0,x
und würde daher auch entweder1,(x-1)/2
(x
ungerade) oder2,x/2-1
(x
gerade) funktionieren, woraufhinx
später im Ergebnis erscheint, so dass es nicht passieren wird. Für eine spätere Kollision kann der Mittelwert nur derselbe sein, wenn auch die dritten Terme gleich sind, aber dann muss ein geringerer Unterschied zwischen den anfänglichen Terms bestehen (ansonsten wären sie gleich) und werden daherx
bei einem späteren Index gefunden . Als solches können wirṫ-Sṭµ¡i³¶ḶŒcÇÐṀ
vier Bytes sparen.ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
GolfScript -
8877 BytesDank cardboard_box habe ich nicht nach mehreren Lösungen gesucht!
Erläuterung
quelle
Batch,
160158 Bytesquelle
3 7
Eingabe27
. Die richtige Lösung ist0 9
.