Dies war eine Interviewfrage, die mit Projekt Euler Problem 14
zu tun hatCollatz-Vermutung sagt, dass, wenn Sie folgendes tun
%Vor%Sie haben am Ende 1.
Zum Beispiel 5 -> 16 -> 8 -> 4 -> 2 -> 1
Unter der Annahme, dass die Vermutung wahr ist, hat jede Zahl eine Kettenlänge: Die Anzahl der Schritte, die erforderlich sind, um zu 1 zu kommen. (Die Kettenlänge von 1 ist 0).
Nun ist das Problem gegeben natürliche Zahlen n, m und eine natürliche Zahl k, geben Sie einen Algorithmus, um alle Zahlen zwischen 1 und n zu finden, so dass die Kettenlänge dieser Zahlen ist & lt; = k. Es gibt auch die Einschränkung, dass die Kette einer dieser Zahlen nur Zahlen zwischen 1 und m enthalten darf (d. H. Sie können nicht über m gehen).
Ein einfacher Weg ist es, es brutal zu erzwingen und das mit Memo zu kombinieren.
Der Interviewer sagte, dass es einen O (S) -Zeitalgorithmus gibt, wobei S die Anzahl der Zahlen ist, die wir ausgeben müssen.
Weiß jemand was es sein könnte?
Ich denke, Sie können das in O (S) lösen, indem Sie den Prozess rückwärts laufen lassen. Wenn Sie wissen, was k ist, können Sie alle Zahlen, die in den meisten k Schritten anhalten, mit der folgenden Logik aufbauen:
Daraus können Sie beginnen, die Zahlen in der Reihenfolge beginnend mit 1 aufzubauen:
%Vor%Wir könnten diesen Algorithmus verwenden, indem wir eine Arbeitswarteschlange verwenden, die Zahlen, die wir besuchen müssen, und die Längen ihrer Ketten speichert. Wir bevölkern die Warteschlange mit dem Paar (1, 0), entziehen dann kontinuierlich ein Element (z, n) aus der Warteschlange und stellen die Warteschlange (2z, n + 1) und (möglicherweise) ((z - 1) / 3, n +) ein 1) in die Warteschlange. Dies geschieht im Wesentlichen in der Collagen-Graphik beginnend mit einer ersten Suche. Wenn wir das erste Element in der Tiefe k finden, stoppen wir die Suche.
Unter der Annahme, dass die Collatz-Vermutung wahr ist, werden wir auf diese Weise niemals Duplikate erhalten. Außerdem haben wir auf diese Weise alle erreichbaren Nummern in den meisten k Schritten gefunden (das können Sie schnell mit einem schnellen induktiven Beweis überprüfen). Und schließlich dauert dies O (S) -Zeit. Beachten Sie, dass die Arbeit, die pro generierter Nummer ausgeführt wird, eine Konstante ist (aus der Warteschlange entfernen und bis zu zwei neue Nummern in die Warteschlange einfügen).
Hoffe, das hilft!