Nehmen wir an, wir betrachten Binärzahlen mit der Länge 2n und n könnten etwa 1000 sein. Wir suchen nach kth number (k ist begrenzt durch 10^9 ) welches folgende Eigenschaften hat:
1's entspricht der Menge von 0's , was wie folgt beschrieben werden kann: #(1) = #(0)
0's wie 1's enthalten. Es könnte einfacher sein, es zu verstehen, nachdem der Satz negiert wurde, nämlich: Es gibt kein Präfix, das mehr 1's als 0's enthalten würde. Und das ist es im Grunde.
Um es klar zu machen, lassen Sie uns ein Beispiel geben:
n=2 , k=2
Wir müssen die Binärzahl der Länge 2n :
Und jetzt müssen wir 2nd number finden, die diese beiden Anforderungen erfüllen. Wir sehen also 0011 ist der erste und 0101 ist der zweite.
Wenn wir k=3 ändern, dann gibt es keine Antwort, da es Zahlen gibt, die die gleiche Anzahl entgegengesetzter Bits haben, aber für 0110 gibt es das Präfix 011 , so dass die Zahl die zweite Bedingung nicht erfüllt und dasselbe wäre alle Zahlen, die 1 als höchstwertiges Bit haben.
Was habe ich bisher gemacht, um einen Algorithmus zu finden?
Nun, meine erste Idee war es, alle möglichen Bits Einstellungen zu generieren, und zu überprüfen, ob es diese beiden Eigenschaften hat, aber alle generieren würde O(2^(2n)) nehmen, was keine Option für n=1000 ist.
Außerdem ist mir klar, dass es nicht nötig ist, alle Zahlen zu überprüfen, die kleiner als 0011 für n=2 , 000111 für n=3 usw. sind. Offen gesagt, die Hälfte der höchstwertigen Bits bleibt übrig "Unberührt", weil diese Nummern keine Möglichkeit haben, #(1) = #(0) condition zu erfüllen. Mit diesem kann ich n um die Hälfte reduzieren, aber es hilft nicht viel. Anstelle von 2 * für immer habe ich für immer Algorithmus ausgeführt. Es ist immer noch O(2^n) Komplexität, die viel zu groß ist.
Irgendeine Idee für Algorithmus?
Fazit
Dieser Text wurde als Ergebnis meiner Gedanken nach dem Lesen von Andy Jones Post erstellt.
Zuerst würde ich Code, den ich verwendet habe, nicht posten, da es im folgenden Dokument Punkt 6 aus Andys Post algorithm binary sequence catalan
Die Zahlen, die Sie beschreiben, entsprechen Dyck-Wörtern . Pt 2 von Kasa 2009 gibt einen einfachen Algorithmus zum Aufzählen in lexikographischer Reihenfolge. Seine Referenzen sollten hilfreich sein, wenn Sie weiterlesen möchten.
Als Nebenbemerkung (und sei gewarnt, dass ich beim Schreiben halb einschlafe, also könnte es falsch sein), bemerkt der Wikipedia-Artikel, dass die Anzahl der Dyck-Wörter der Länge 2n die n katalanische Zahl ist , C(n) . Vielleicht möchten Sie die kleinste n so finden, dass C(n) größer ist als die von Ihnen gewünschte k , und dann die Dyck-Wörter ab X^n Y^n aufzählen.
Tut mir leid, dass ich dieses Problem beim letzten Mal falsch verstanden habe, also bearbeite ich es und jetzt kann ich die Korrektur versprechen und Sie können den Code zuerst testen, die Komplexität ist O(n^2) , die Detailantwort folgt
Zuerst können wir das Problem mit dem nächsten gleichstellen
Wir suchen nach kth largest number (k ist begrenzt durch 10^9 ) welches folgende Eigenschaften hat:
1's entspricht der Menge von 0's , was wie folgt beschrieben werden kann: #(1) = #(0)
1's als 0's ]] enthalten, was bedeutet: Es gibt kein Präfix, das mehr [[ 0's als 1's ]] enthalten würde. Lassen Sie uns ein Beispiel geben, um es zu erklären: Lassen Sie n=3 und k=4 , die Anzahl der erfüllten Zahlen ist 5 , und das Bild unten erklärt, was wir im vorherigen Problem und neuen Problem feststellen sollten:
Also nachdem wir das neue Problem gelöst haben, müssen wir nur noch bitweise nicht.
Jetzt ist das Hauptproblem, wie man das neue Problem löst. Zuerst sei A das Array, also kann A[m]{1<=m<=2n} nur 1 oder 0 sein, lasst DP[v][q] die Anzahl der Zahlen sein, die Bedingung2 und Bedingung # (1) = q in {A[2n-v+1]~A[2n]} erfüllen, also DP[2n][n] ist die Anzahl der erfüllten Zahlen.
A[1] kann nur 1 oder 0 sein, wenn A[1]=1 ist, die Anzahl der Zahlen ist DP[2n-1][n-1] , wenn A[1]=0 , die Anzahl der Zahlen ist DP[2n-1][n] , jetzt wollen wir die kth largest finden Zahl, wenn k<=DP[2n-1][n-1] , kth largest number A[1] 1 sein muss, dann können wir A[2] mit DP[2n-2][n-2] ; Wenn k>DP[2n-1][n-1] , kth largest number A[1] 0 und k=k-DP[2n-1][n-1] sein müssen, können wir A[2] mit DP[2n-2][n-1] beurteilen. Mit der gleichen Theorie können wir A[j] eins nach dem anderen beurteilen, bis es keine zu vergleichende Zahl gibt. Jetzt können wir ein Beispiel geben, um (n=3, k=4)
(Wir verwenden dynamische Programmierung zur Bestimmung der DP-Matrix, die DP-Gleichung lautet DP [v ] [q] = DP [v-1] [q-1] + DP [v-1] [q] )
%Vor%Wenn Sie nicht klar verstanden haben, können Sie den Code verwenden, um
zu verstehen Absicht : DP[2n][n] steigt sehr schnell, so dass der Code nur funktionieren kann, wenn n<=19 , im Problem n<1000 , also können Sie große Zahl verwenden Programmierung, und der Code kann durch Bit-Operation optimiert werden, so ist der Code nur eine Referenz