Die niedrigsten Anfangszahlen in einer Fibonacci-ähnlichen Folge

22

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
Stewie Griffin
quelle
Wenn a>=0und a<bgibt es jemals mehrere Lösungen?
Jonathan Allan
Ich kann nicht garantieren, dass es mehrere Lösungen gibt oder nicht. Beides 1,4und 2,3würde geben 5, 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.
Stewie Griffin
2
total inspiriert von codegolf.stackexchange.com/q/147200/67961
J42161217
3
Die entsprechende OEIS-Sequenz für den niedrigstmöglichen Mittelwert, A249783 , weist eine wild aussehende Grafik auf .
Peter Kagey
1
@ ØrjanJohansen Ich habe meiner Antwort einen Beweis hinzugefügt, dass es keine doppelten Lösungen gibt (da meine Antwort davon abhängt).
cardboard_box

Antworten:

8

Schale , 19 18 16 14 13 15 Bytes

Danke Zgarb für das Speichern von 1 Byte.

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

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 der mapad2die Funktion auf alle benachbarten Paare in einer Liste angewendet wird. (Obwohl, wenn man Husk kennt, im Kontext dieses Programms etwas anderes bedeuten könnte)

            Θḣ⁰    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
quelle
Ich bin sicher, ich habe es versucht ...
H.PWiz
8

JavaScript (Node.js) , 92 90 89 91 83 82 Byte

-3 Bytes -1 Bytes dank ThePirateBay

-8 -9 Bytes dank Neil.

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]

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

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 >= 5gibt eine Lösung, a,bdie erfüllt a+b < n:

wenn gerade nist,FIB(0,n/2,3) = n

wenn nungerade ist,FIB(1,(n-1)/2,3) = n

Beweis

Fälle, in denen umfassend n < 5geprüft werden kann.

Angenommen , wir haben zwei minimale Lösungen für n >= 5, a0,b0und a1,b1mit a0 + b0 = a1 + b1und a0 != a1.

Dann gibt es k0,k1so etwas FIB(a0,b0,k0) = FIB(a1,b1,k1) = n.

  • Fall 1: k0 = k1

    WLOG annehmen b0 < b1(und daher a0 > a1)

    Sei DIFF(k)der Unterschied zwischen den Fibonnaci-ähnlichen Sequenzen beginnend mit a1,b1und a0,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) = 0ist , wenn k = 2, so dass die einzige Wahl für k0 = k1ist 2.

    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 ist k >= 0, ist es auch nicht abnehmend.

    Das gibt uns a2 >= b1 > a0und b2 >= 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 DIFF2 positive Ausdrücke und daher sind alle nachfolgenden Ausdrücke positiv.

    Wenn also die einzige Zeit , möglich ist es , das DIFF(k) = 0ist k = 1, so dass die einzige Wahl für k0ist 1.

    FIB(a0,b0,1) = n

    b0 = n

    Dies widerspricht Lemma 2.

Pappschachtel
quelle
1
77 Bytes
Neil
@Neil Das minimiert banstatt zu minimieren a+b, und somit gibt deine Lösung f(27) = [3,7]doch die optimale Lösung f(27)=[0,9]. Nachdem wir die Änderungen rückgängig gemacht haben, sind wir auf 83 Bytes gesunken.
cardboard_box
1
Ich denke, Sie können ein anderes Byte speichern, indem Sie b-~aanstelle von verwenden a+b+1.
Neil
1
Es gibt einen kleinen Fehler in der zweiten Fall: a2 >= a1 + b1nicht , wenn korrigieren wird k1-k0=1. Stattdessen können Sie a2 >= b1 > a0und verwenden b2 >= a1+b1 = a0+b0, und dann folgt der Rest.
Ørjan Johansen
8

Haskell , 76 72 74 Bytes

BEARBEITEN:

  • -4 Bytes: @ H.PWiz empfohlene Verwendung /anstelle von div, obwohl dies die Verwendung eines Typs mit gebrochenen Zahlen erfordert.
  • +2 Bytes: Ein Fehler mit EnumBereichen durch Hinzufügen wurde behoben -1.

fNimmt einen Wert von Doubleoder RationalTyp und gibt ein Tupel desselben zurück. Doublesollte für alle Werte ausreichen, die nicht groß genug sind, um Rundungsfehler zu verursachen, während sie Rationaltheoretisch unbegrenzt sind.

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

Probieren Sie es online!(mit H.PWiz's Header Anpassungen an Input / Output Rationals im Integer Format)

Wie es funktioniert

  • ?ist ein lokal verschachtelter Operator im Bereich von f. a?bDurchläuft rekursiv die Fibonacci-ähnliche Sequenz, beginnend mit a,bbis b>=n, und kehrt zurückTrue iff" wenn sie ngenau trifft .
  • Im Listenverständnis:
    • sDurchläuft alle Zahlen von 1oben nach unten und repräsentiert die Summe von aundb .
    • adurchläuft die Zahlen von 0bis s/2-1. (Obs ungerade ist, wird das Bereichsende aufgerundet.)
    • a?(s-a)testet, ob die Sequenz mit a,s-aTreffern beginnt n. 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.
Ørjan Johansen
quelle
8

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

2 Bytes gespart dank @ Adám

Dank @ngn werden 12 Bytes gespeichert

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

Probieren Sie es online!

Verwendet ⎕IO←0 .

Wie? Das war echt verrückt geworden.

k←⎕ - Eingang zuordnen zu k

⍳2⍴1+k←⎕- Kartesisches Produkt der Reihe 0bisk mit sich

|-\¨ - subtrahiere jedes rechte Paarelement von dem linken und erhalte absolute Werte

a←,⍉ - transponieren, abflachen und zuweisen a

o←a/⍨</¨a - Behalten Sie nur Paare bei, bei denen das linke Element kleiner als das rechte ist, und weisen Sie es zu o

oenthält nun eine Liste aller Paare mit a < b, geordnet nach ihrem arithematischen Mittelwert

+\∘⌽⍣{k≤⊃⍺}¨o- oWenden Sie für jedes Paar in Fibonacci an (vertauschen Sie das Paar und Cumsum), bis eine khöhere Laufzeit erreicht ist

k∊¨- Entscheide dann, ob kes sich um den letzten Begriff handelt (dh, er ist in der Sequenz enthalten)

o/⍨- und bewahren Sie Paare dort auf, owo die vorherige Überprüfung zutrifft

- das erste Ergebnis zurückgeben.

Uriel
quelle
5

Python 2 , 127 109 107 Bytes

-2 Bytes dank ovs (ändern andauf *)

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

Probieren Sie es online!

Irgendwelche Bonuspunkte für n,a,s-a?

Erläuterung:

  • Die erste Zeile deklariert ein rekursives Lambda, gdas überprüft, ob es a, bals Fibonacci-Sequenz expandiert wird x. Es überprüft auch, dass a <= beines der Kriterien der Frage. (Dies würde Fälle ermöglichen, in denen a == baber in einem solchen Fall 0, abereits entdeckt und zurückgegeben worden wäre).
    • Die verkettete Ungleichung a<=b<xführt zwei nützliche Aufgaben gleichzeitig aus: Verifizieren a <= bund das b < x.
    • Wenn b < xergibt True, 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 ...
    • Wenn b < xRenditen False, dann haben wir den Punkt erreicht, an dem wir prüfen müssen, ob b==x. In diesem TrueFall wird dies zurückgegeben , was bedeutet, dass das ursprüngliche Paar a, bschließlich erreicht wird x. Andernfalls ist b > xdas Paar ungültig.
  • Die zweite Zeile deklariert ein weiteres rekursives Lambda, fdas die Lösung für einen bestimmten Wert findet n. Es versucht rekursiv neue Anfangspaare a, b, bis sich g(n, a, b)ergibt True. Diese Lösung wird dann zurückgegeben.
    • Die Funktion zählt rekursiv die anfänglichen Fibonacci-Paare unter Verwendung von zwei Variablen s(anfänglich 1) und a(anfänglich 0). Bei jeder Iteration awird inkrementiert und a, s-aals erstes Paar verwendet. Wenn jedoch atriffts wird es jedoch auf 0 zurückgesetzt und sinkrementiert. Dies bedeutet, dass die Paare nach folgendem Muster hochgezählt werden:
      s = 1 (0, 1) (1, 0)
      s = 2 (0, 2) (1, 1) (2, 0)
      s = 3 (0, 3) (1, 2), (2, 1), (3, 0)
      
      Offensichtlich enthält dies einige ungültige Paare, diese werden jedoch sofort gelöscht, wenn sie an übergeben werden g(siehe ersten Aufzählungspunkt).
    • Wenn Werte aund sso gefunden werden, g(n, a, s-a) == Truewird 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.
FlipTack
quelle
3

R , 183 Bytes 160 Bytes

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

Probieren Sie es online!

Danke an Giuseppe für das Golfen mit 23 Bytes

Code Erklärung

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.
Kennzeichen
quelle
1
160 Bytes - im Allgemeinen sollten Sie Bytes speichern, wo immer Sie können. Daher ist das Speichern von 4 Bytes durch Entfernen von netten Namen nicht nur akzeptabel oder empfohlen, sondern in gewissem Sinne auch für Code-Golf erforderlich . Trotzdem, nette Antwort, +1.
Giuseppe
1

Mathematica, 117 Bytes

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


Probieren Sie es online!

J42161217
quelle
1

Jelly , 19 Bytes

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

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 .

Erik der Outgolfer
quelle
... ein führendes Inkrement sollte die Beobachtung von @ StewieGriffin auflösen.
Jonathan Allan
Ich habe das Gefühl, Sie können die
Jonathan Allan
1
Wir müssen nur den Startwert finden, der die Eingabe bewirkt, xund der als letztes angezeigt wird. Wenn x es beim dritten Index für multiple gefunden würde, dann funktioniert es für 0,xund würde daher auch entweder 1,(x-1)/2( xungerade) oder 2,x/2-1( xgerade) funktionieren, woraufhin xspä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 daher xbei einem späteren Index gefunden . Als solches können wir ṫ-Sṭµ¡i³¶ḶŒcÇÐṀvier Bytes sparen.
Jonathan Allan
... Hoppla, zuzüglich der Erhöhung:ṫ-Sṭµ¡i³¶‘ḶŒcÇÐṀ
Jonathan Allan
@StewieGriffin Dieser Testfall existierte nicht, als ich antwortete: p
Erik the Outgolfer
1

GolfScript - 88 77 Bytes

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

Dank cardboard_box habe ich nicht nach mehreren Lösungen gesucht!

Erläuterung

~: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
quelle
Probieren Sie es online!
Ørjan Johansen
0

Batch, 160 158 Bytes

@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
quelle
Dies gibt (auch) eine 3 7Eingabe 27. Die richtige Lösung ist 0 9.
cardboard_box
@ Cardboard_box Immer noch nicht zu sehen, wo die Frage das erfordert ...
Neil
Im ersten Satz: "mit dem niedrigstmöglichen Mittelwert".
cardboard_box
@cardboard_box Ah, sorry, das war zu leicht zu übersehen.
Neil
1
@ cardboard_box OK sollte jetzt behoben sein.
Neil