Das Problem besteht darin, die Anzahl der wiederholbaren Binärzeichenfolgen der Länge n zu finden. Eine Binärzeichenfolge ist wiederholbar, wenn sie von einer Unterzeichenfolge der Binärzeichenfolge abgerufen werden kann, die sich selbst wiederholt, um die ursprüngliche Binärzeichenfolge zu bilden.
%Vor%Die Lösung, an die ich gedacht habe, besteht darin, alle möglichen binären Strings der Länge n zu erzeugen und zu überprüfen, ob es sich um einen wiederholbaren KMP-Algorithmus handelt oder nicht. Aber diese Lösung ist selbst für kleine n wie n nicht machbar >
Der zweite Ansatz, den ich dachte, ist
Beispiel für n = 6 haben wir Teiler 1,2,3
für die Länge 1 haben wir 2 Sub-Strings "1" und "0", die sich wiederholen 6 mal so "111111" und "000000" sind wiederholbare Strings
für die Länge 2 haben wir 4 Sub-Strings "00" "01" "10" "11" also "000000" "010101" "101010" und "111111" sind wiederholbare Zeichenfolgen
Ähnlich haben wir für Länge 3 8 Strings, die wiederholbar sind.
Im obigen Beispiel wurde die Zeichenfolge "111111" und "000000" dreimal für jeden Divisor gezählt. Also bin ich offensichtlich überzählig. Ich muss die Duplikate abziehen, aber ich kann mir sowieso nicht vorstellen, die Duplikate zu subtrahieren meine tatsächliche Zählung Wie kann ich das tun?
Gehe ich in die richtige Richtung oder brauche ich einen anderen Ansatz?
Wenn Sie das zweite Schema verwenden, entfernen Sie die Unterzeichenfolgen, die aus wiederholbaren Binärdateien bestehen. Zum Beispiel werden 00 und 11 aus der Wiederholung von 0 bzw. 1 gebildet. Also für die Länge von 2 nur die "01" und "10" für die Länge 3 nur "001", "010", "011", "100", "101", "110" ... allgemein, für ungerade Länge von n entferne 0 und (2 ^ n) -1, für gerade Länge von n, entferne 0, (2 ^ (n / 2) +1), (2 ^ (n / 2) +1) 2, ...., (2 ^ n) -1 und wenn n durch 3 teilbar ist, (1 + 2 ^ (n / 2) + 2 ^ (n-2)), (1 + 2 ^ (n / 2) + 2 ^ (n-2)) 2, ... Weiter für alle Teiler.
Eine Idee ist, dass, wenn wir nur die Möglichkeiten zählen, die Teiler-Strings aus nicht wiederholten Teilstrings zu machen, die Zählungen aus den Divisoren des Divisors die Wege erklären, die Teiler aus wiederholten Teilstrings zu machen.
%Vor% ... bedeutet die Summe von nur den Arten, wie Teiler von n nicht aus wiederholten Teilstrings gemacht werden können.
Tags und Links algorithm string combinatorics counting