Sie erhalten eine Ganzzahl n, und Sie müssen den Index ihres ersten Auftretens in Sterns Diatomic Sequence finden.
Die Reihenfolge ist wie folgt definiert:
%Vor%Siehe MathWorld .
Da n bis zu 400000 sein kann, ist es keine gute Idee, es zu bruten, zumal das Zeitlimit 4000 ms beträgt.
Die Reihenfolge ist ziemlich seltsam: Das erste Vorkommen von 8 ist 21, aber das erste Vorkommen von 6 ist 33.
Irgendwelche Ideen, wie man das löst?
Vielleicht könnte das helfen: OEIS
Wir können leicht das erste Auftreten einer Zahl im Bereich von 400000 in weniger als vier Sekunden lösen:
%Vor%Der Schlüssel dazu ist der Calkin-Wilf-Baum.
Ausgehend von der Fraktion 1/1 wird nach der Regel aufgebaut, dass für einen Knoten mit dem Bruch a/b das linke Kind den Bruch a/(a+b) und das rechte Kind den Bruch (a+b)/b trägt.
usw. Die zweiatomige Sequenz (beginnend mit Index 1) ist die Folge von Zählern der Brüche im Calkin-Wilf-Baum, wenn diese Ebene für Ebene durchlaufen wird, jede Ebene von links nach rechts.
Wenn wir uns den Indexbaum ansehen
%Vor% können wir leicht überprüfen, dass der Knoten am Index k im Calkin-Wilf-Baum den Anteil a[k]/a[k+1] durch Induktion trägt.
Das gilt natürlich für k = 1 ( a[1] = a[2] = 1 ) und von da an
für k = 2*j haben wir das linke Kind des Knotens mit dem Index j , also ist der Bruch a[j]/(a[j]+a[j+1]) und a[k] = a[j] und a[k+1] = a[j] + a[j+1] sind die definierenden Gleichungen der Sequenz.
für k = 2*j+1 haben wir das rechte Kind des Knotens mit dem Index j , also ist der Bruch (a[j]+a[j+1])/a[j+1] und das ist a[k]/a[k+1] wieder durch die definierenden Gleichungen.
Alle positiv reduzierten Fraktionen treten genau einmal im Calkin-Wilf-Baum auf (links als Übung für den Leser), daher treten alle positiven ganzen Zahlen in der zweiatomigen Sequenz auf.
Wir können den Knoten im Calkin-Wilf-Baum vom Index aus finden, indem wir der binären Darstellung des Index folgen, vom höchstwertigen bis zum kleinsten, für ein 1-Bit gehen wir zum rechten Kind und für eine 0 -Bit nach links. (Daher ist es schön, den Calkin-Wilf-Baum mit einem Knoten 0/1 zu erweitern, dessen rechtes Kind der Knoten 1/1 ist, so dass wir einen Schritt für das höchstwertige gesetzte Bit des Index benötigen.)
Das hilft jetzt noch nicht sehr, das Problem zu lösen.
Aber lasst uns zuerst ein verwandtes Problem lösen: Für einen reduzierten Bruch p/q , bestimme seinen Index.
Angenommen, p > q . Dann wissen wir, dass p/q ein rechtes Kind ist und dessen Eltern (p-q)/q ist. Wenn auch p-q > q , haben wir wieder ein rechtes Kind, dessen Eltern (p - 2*q)/q ist. Fortfahren, wenn
Dann erreichen wir den Knoten p/q vom Knoten b/q , indem wir zum rechten Kind a mal gehen.
Jetzt müssen wir einen Knoten finden, dessen Zähler kleiner als sein Nenner ist. Das ist natürlich das linke Kind seines Elternteils. Der Elternteil von b/q ist dann b/(q-b) . Wenn
Wir müssen zum linken Kind c mal vom Knoten b/d gehen, um b/q zu erreichen.
Und so weiter.
Wir können den Weg von der Wurzel ( 1/1 ) zum Knoten p/q finden, indem wir die Fortsetzung von p/q verwenden (ich denke hier nur an einfache fortlaufende Brüche). Lassen Sie p > q und
die fortlaufende Fraktionserweiterung von p/q endet in 1 .
r gerade ist, dann gehe zum rechten Kind a_r mal, dann nach links a_(r-1) mal, dann zum rechten Kind ... dann a_1 mal zum linken Kind und schließlich a_0 mal nach rechts. r ungerade ist, dann gehe zuerst zum linken Kind a_r mal, dann a_(r-1) mal nach rechts ... dann a_1 mal zum linken Kind und schließlich a_0 mal zu das Recht. Für p < q müssen wir aufhören, nach links zu gehen, also gehen wir nach links für gerade r und beginnen, nach rechts für ungerade r zu gehen.
Wir haben also eine enge Verbindung zwischen der binären Repräsentation des Index und der fortgesetzten Fraktionsexpansion des vom Knoten getragenen Bruchteils über den Pfad vom Wurzelknoten zum Knoten gefunden.
Lassen Sie die Lauflängencodierung des Index k
d. Die binäre Darstellung von k beginnt mit c_1 eins, gefolgt von c_2 Nullen, dann c_3 Einsen usw., und endet mit c_j
k ungerade ist - daher ist j auch ungerade; k gerade ist - daher ist j auch gerade. Dann ist [c_j, c_(j-1), ..., c_2, c_1] die fortlaufende Fraktionserweiterung von a[k]/a[k+1] , deren Länge die gleiche Parität wie k hat (jedes rationale hat genau zwei kontinuierliche Bruchdehnungen, eins mit ungerader Länge, das andere mit gerader Länge).
Die RLE gibt den Pfad vom Knoten 0/1 über 1/1 bis a[k]/a[k+1] an. Die Länge des Pfades ist
k und Um nun den Index des ersten Auftretens von n > 0 in der zweiatomigen Sequenz zu finden, müssen wir zuerst feststellen, dass der kleinste Index notwendigerweise ungerade sein muss, da a[k] = a[k/2] für gerade k . Sei der kleinste Index k = 2*j+1 . Dann
k ist ungerade, k ist a[2*j+1]/a[2*j+2] = (a[j] + a[j+1])/a[j+1] , daher handelt es sich um ein rechtes Kind. Der kleinste Index k mit a[k] = n entspricht also der äußersten linken aller kürzesten Pfade zu einem Knoten mit dem Zähler n .
Die kürzesten Pfade entsprechen den fortgesetzten Fraktionserweiterungen von n/m , wobei 0 < m <= n ist coprime to n [der Bruch muss reduziert werden] mit der kleinsten Summe der Teilquotienten.
Welche Länge müssen wir erwarten? Bei einem fortgesetzten Bruch p/q = [a_0, a_1, ..., a_r] mit a_0 > 0 und sum
Der Zähler p wird durch F(s+1) und den Nenner q by F(s) begrenzt, wobei F(j) die j -te Fibonacci-Zahl ist. Die Grenzen sind scharf, für a_0 = a_1 = ... = a_r = 1 ist der Bruch F(s+1)/F(s) .
Wenn also F(t) < n <= F(t+1) ist, ist die Summe der Teilquotienten der Fortsetzungsfraktions-Erweiterung (eine der beiden) >= t . Oft gibt es ein m , so dass die Summe der Teilquotienten der fortgesetzten Fraktionserweiterung von n/m genau t ist, aber nicht immer:
und die kontinuierlichen Fraktionserweiterungen der beiden reduzierten Fraktionen 6/m mit 0 < m <= 6 sind
mit Summe der Teilquotienten 6. Die kleinste mögliche Summe der Teilquotienten ist jedoch nie viel größer (die größte, die mir bekannt ist, ist t+2 ).
Die kontinuierlichen Fraktionserweiterungen von n/m und n/(n-m) sind eng miteinander verwandt. Nehmen wir an, dass m < n/2 , und lassen Sie
Dann a_0 >= 2 ,
und seit
%Vor% Die fortgesetzte Fraktionserweiterung von n/(n-m) ist
Insbesondere ist die Summe der Teilquotienten für beide gleich.
Leider ist mir keine Möglichkeit bekannt, m mit der kleinsten Summe von Teilquotienten ohne Brute-Force zu finden, also ist der Algorithmus (ich nehme n > 2
für 0 < m < n/2 coprime bis n , finde die kontinuierliche Bruchdehnung von n/m und sammle die mit der kleinsten Summe der Teilquotienten (der übliche Algorithmus erzeugt Erweiterungen, deren letzter Teilquotient% co_de ist %, nehmen wir das an.)
Passen Sie die gefundenen fortgesetzten Fraktionserweiterungen [diese sind nicht zahlreich an] auf folgende Weise an:
> 1 gerade Länge hat, wandle sie in [a_0, a_1, ..., a_r] um
[a_0, a_1, ..., a_(r-1), a_r - 1, 1]
(wählt den zwischen [1, a_0 - 1, a_1, ..., a_(r-1), a_r - 1, 1] und n/m , der zum kleineren Index führt)
kehrt die fortlaufenden Brüche um, um die Lauflängenkodierungen der entsprechenden Indizes zu erhalten
wähle die kleinsten unter ihnen aus.
In Schritt 1 ist es nützlich, die kleinste Summe zu verwenden, die bisher zum Abkürzen gefunden wurde.
Code (Haskell, da ist das am einfachsten):
%Vor%Ich würde Ihnen empfehlen, diesen Brief von Dijkstra zu lesen, der einen alternativen Weg erklärt um diese Funktion zu berechnen über:
%Vor%Dies beginnt mit a, b = 1,0 und verwendet effektiv aufeinanderfolgende Bits von N (vom kleinsten zum höchstwertigen), um a und b zu erhöhen, wobei das Endergebnis der Wert von b ist.
Der Index des ersten Auftretens eines bestimmten Wertes für b kann daher berechnet werden, indem das kleinste n gefunden wird, für das diese Iteration zu dem Wert von b führt.
Eine Methode, um dieses kleinste n zu finden, ist A * search , wobei die Kosten der Wert von n sind . Die Effizienz des Algorithmus wird durch die Wahl der Heuristik bestimmt.
Für die Heuristik würde ich Folgendes empfehlen:
BEARBEITEN
Hier ist ein Beispiel für Python-Code, um den A * -Ansatz zu veranschaulichen.
%Vor%