Ich implementiere ein Programm, das eine Gleichung berechnet: F (n) = F (n-1) + 'a' + func1 (func2 (F (n-1))).
func1 nimmt jedes "a" und macht es "c" und jedes "c" wird "a".
func2 kehrt die Zeichenfolge um (e.x. "xyz" wird zu "zyx").
Ich möchte den K-Charakter von F berechnen (10 ** 2017). Die Grundregeln sind F (0)="" (leere Zeichenkette), und Beispiele sind F (1)="a", F (2)="aac", und so weiter.
Wie mache ich das effizient?
Der grundlegende Teil meines Codes ist dies:
%Vor% Beginnen wir damit, Ihren ursprünglichen Code zu korrigieren und eine Funktion zu definieren, um F(n) für kleine n zu berechnen. Wir werden auch die ersten Werte von F ausdrucken. Der folgende Code ist für Python 3; Wenn Sie Python 2 verwenden, müssen Sie einige kleinere Änderungen vornehmen, zum Beispiel str.maketrans durch string.maketrans und range durch xrange ersetzen.
Dies ergibt die folgende Ausgabe:
%Vor%Ein paar Beobachtungen an dieser Stelle:
F(n) ist eine Zeichenfolge der Länge 2**n-1 . Das bedeutet, dass F(n) schnell wächst. Die Berechnung von F(50) würde bereits einige ernsthafte Hardware erfordern: Selbst wenn wir ein Zeichen pro Bit speichern würden, würden wir über 100 Terabyte benötigen, um die vollständige Zeichenfolge zu speichern. F(200) hat mehr Zeichen als geschätzte Atome im Sonnensystem. Daher ist die Idee von computing F(10**2017) direkt lächerlich: Wir brauchen einen anderen Ansatz.
Nach dem Aufbau ist jedes F(n) ein Präfix von F(n+1) . Also, was wir wirklich haben, ist eine gut definierte unendliche Zeichenkette, wobei jedes F(n) uns nur die ersten 2**n-1 Zeichen dieser unendlichen Zeichenkette gibt und wir versuchen, seine k zu berechnen. th Charakter. Und aus irgendeinem praktischen Grund könnte F(10**2017) genauso gut sein wie diese unendliche Zeichenkette: wenn wir beispielsweise unsere Berechnung durchführen, müssen wir das nicht überprüfen k < 2**(10**2017)-1 , da a k Diese Überschreitung kann in diesem Universum nicht einmal in normaler binärer Notation dargestellt werden.
Glücklicherweise ist die Struktur der Zeichenkette einfach genug, um das k th-Zeichen direkt zu berechnen. Der Hauptschlüssel kommt, wenn wir die Charaktere auf geraden und ungeraden Positionen betrachten:
Die Zeichen an even Positionen wechseln einfach zwischen a und c (und es ist einfach zu beweisen, dass dies wahr ist, basierend auf der Konstruktion). Wenn also k gerade ist, können wir einfach schauen, ob k/2 ungerade oder gerade ist, um zu bestimmen, ob wir eine a oder eine c bekommen.
Was ist mit den ungeraden Positionen? Gut F(6)[1::2] sollte etwas vertraut aussehen: es ist nur F(5) :
Wiederum ist es einfach zu beweisen (z. B. durch Induktion), dass dies nicht einfach ein Zufall ist und dass F(n+1)[1::2] == F(n) für alle nichtnegativen n .
Wir haben jetzt eine effektive Möglichkeit, das k th Zeichen in unserer unendlichen Zeichenkette zu berechnen: Wenn k gerade ist, betrachten wir nur die Parität von k/2 . Wenn k ungerade ist, wissen wir, dass das Zeichen an der Position k gleich dem an der Position (k-1)/2 ist. Also hier ist eine erste Lösung zur Berechnung dieses Charakters:
Und eine Überprüfung, dass dies das Richtige tut:
%Vor% Aber wir können es besser machen. Wir starren effektiv auf die binäre Darstellung von k , entfernen alle nachlaufenden '1' s und die nächste '0' und schauen uns dann einfach das nächste Bit an, um festzustellen, ob wir 'a' oder% co_de haben %. Das Identifizieren der abschließenden 1s kann durch Bit-Operation-Tricks erfolgen. Dies gibt uns die folgende halbverschleierte schleifenfreie Lösung, die ich Ihnen zum Entspannen überlassen möchte:
Lassen Sie uns noch einmal überprüfen:
%Vor%Schlussbemerkung: Dies ist eine sehr bekannte und gut untersuchte Sequenz: Sie wird als Drachenkurvenfolge oder als reguläres Papier bezeichnet Faltungssequenz und ist Sequenz A014577 in der Online-Enzyklopädie von Integer-Sequenzen. Einige Google-Suchanfragen bieten Ihnen wahrscheinlich viele weitere Möglichkeiten zur Berechnung ihrer Elemente. Siehe auch diese Codegolf-Frage .
Tags und Links python