Sei f (k) = y, wobei k die y-te Zahl in der ansteigenden Folge von nichtnegativen ganzen Zahlen ist die gleiche Anzahl von Einsen in seiner Binärdarstellung wie k, z.B. f (0) = 1, f (1) = 1, f (2) = 2, f (3) = 1, f (4) = 3, f (5) = 2, f (6) = 3 und so weiter. Gegeben sei k & gt; = 0, berechne f (k)
viele von uns haben diese Frage gesehen
1 Lösung für dieses Problem, um Zahlen auf der Grundlage der Anzahl von 1 zu kategorisieren und dann den Rang zu finden. Ich habe einige Muster gefunden, die auf diese Weise gehen, aber es wäre ein langwieriger Prozess. Kann mir jemand eine bessere Lösung vorschlagen?
Dies ist ein Zählproblem. Ich denke, wenn Sie sich diesem Ziel nähern, können Sie viel besser tun, als Werte buchstäblich zu nummerieren und zu überprüfen, wie viele Bits sie haben.
Betrachte die Zahl 17. Die binäre Darstellung ist 10001. Die Anzahl der 1en ist 2. Wir können kleinere Zahlen mit zwei 1en erhalten, indem wir (in diesem Fall) die 1en auf eines der vier niederwertigen Bits umverteilen. 4 wähle 2 ist 6, also sollte 17 die 7. Zahl mit 2 Einsen in der Binärdarstellung sein. Das können wir überprüfen ...
%Vor%Und wir hatten Recht. Verallgemeinere diese Idee und du solltest eine effiziente Funktion erhalten, für die du einfach den Rang von k berechnen kannst.
EDIT: Hinweis zur Verallgemeinerung 17 ist speziell, wenn Sie das höherwertige Bit nicht berücksichtigen, hat die Nummer den Rang 1; Das heißt, f (z) = 1 wobei z alles außer dem höherwertigen Bit ist. Für Zahlen, bei denen dies nicht der Fall ist, wie können Sie die Tatsache berücksichtigen, dass Sie kleinere Zahlen erhalten können, ohne das höherwertige Bit zu verschieben?
f (k) sind ganze Zahlen kleiner oder gleich k, die in ihrer binären Darstellung die gleiche Anzahl von Einsen wie k haben.
Zum Beispiel benötigt k m Bits, das ist k = 2^(m-1) + a , wo a < 2^(m-1) . Die Anzahl der ganzen Zahlen kleiner als 2^(m-1) , die die gleiche Anzahl an Bits wie k haben, ist choose(m-1, bitcount(k)) , da Sie die unter den m-1 am wenigsten signifikanten Bits frei neu verteilen können.
Ganzzahlen, die größer oder gleich 2 ^ (m-1) sind, haben dasselbe höchstwertige Bit wie k (was 1 ist), also gibt es f(k - 2^(m-1)) von ihnen. Dies bedeutet f(k) = choose(m-1, bitcount(k)) + f(k-2^(m-1)) .
Siehe "Auf effiziente Weise die Subsets eines Sets auflisten" . Sehen Sie sich Tabelle 3, die "Bankers-Sequenz", an. Dies ist eine Methode, um genau die Sequenz zu erzeugen, die Sie benötigen (wenn Sie die Bit-Reihenfolge umkehren). Führen Sie K-Iterationen für das Wort mit K-Bits aus. Es gibt Code, um es zu generieren, der in der Zeitung enthalten ist.