Ich bereite mich auf meine Interviews vor und bin auf diese Frage gestoßen:
Schreiben Sie ein Programm, um zu überprüfen, ob eine Zahl n die Form x ^ y hat. Es ist bekannt, dass n, x und y ganze Zahlen sind und dass x und y größer als 2 sind.
Ich dachte daran, Logs und andere Sachen zu nehmen, konnte aber nicht herausfinden, wie man überprüft, ob die Nummer von der Form ist. Könnte jemand von Ihnen bitte helfen? :)
"Das Log und Zeug nehmen" ist der richtige Weg. Beachten Sie, dass N & gt; 1 ist niemals a ^ b für die ganze Zahl a und b & gt; log_2 (N). Sie können floor (N ^ (1 / b)) ^ b = N für jede ganze Zahl b zwischen 2 und log_2 (N) überprüfen. Sie müssen über log (N) viele Exponentiationen machen, von denen jede eine Zahl höchstens der Größe von N erzeugt.
Das ist viel schneller als die Lösung von @ dasblinkenlight, die Sie zuerst N einstufen müssen. (Kein Polynomialzeitalgorithmus --- dh Polynom in der Anzahl von Bits in N, ist für die Ganzzahlfaktorisierung bekannt. Jedoch kann die Ganzzahl-Potenzierung mit einem kleinen Exponenten in Polynomialzeit ausgeführt werden.)
Eine Möglichkeit, dies zu lösen, wäre es, n zu faktorisieren, die einzelnen Faktoren zu zählen und den größten gemeinsamen Nenner der Zählungen zu finden. Wenn GCD 1 ist, lautet die Antwort "Nein". Ansonsten lautet die Antwort "Ja".
Hier sind einige Beispiele:
Es gibt viele gute Antworten, aber ich sehe, dass noch Modulo-Arithmetik fehlt.
Abhängig von der Größe der zu überprüfenden Zahlen kann es sinnvoll sein, sie nach ihren letzten Bits zu klassifizieren. Wir können leicht eine Tabelle mit möglichen Kandidaten erstellen.
Um zu zeigen, wie es funktioniert, lassen Sie uns eine solche Tabelle für 4 letzte Bits erstellen. In diesem Fall müssen wir 16 Fälle berücksichtigen:
%Vor%Der Tisch ist besser umgekehrt; welche Basen x sind für eine gegebene Zahl möglich n = x ^ y .
%Vor%Wenn man also nur die vier letzten Bits über ein Viertel der Zahlen betrachtet, kann man sie sofort wegwerfen.
Wenn wir die Zahl 13726423 nehmen, ist der Rest von 16 7, und wenn es von der Form ist, an der wir interessiert sind, muss es (16 n +7) ^ y sein .
Bei den meisten Zahlen ist die Anzahl der zu probierenden Teiler ziemlich begrenzt. In der Praxis könnte die Tabelle viel größer sein, z. B. 16 Bits.
Eine einfache Optimierung mit Binärzahlen besteht darin, die nachfolgenden Nullen zu entfernen. Dies macht es unnötig, sich um gerade Zahlen zu kümmern, und y muss ein Faktor für die Anzahl der entfernten Nullen sein.
Wenn wir immer noch zu viel Arbeit haben, können wir eine andere Modulo-Tabelle erstellen. Das andere könnte z.B. modulo 15. Die äquivalente Tabelle sieht so aus:
%Vor%Da unsere Nummer aus dem vorherigen Beispiel (13726423) 13 modulo 15 ist, dann x = (15 m +7) oder (15 m +13). Da es keine gemeinsamen Faktoren in 15 und 16 gibt, sind die gültigen Zahlen 240 p + 7 und 240 p + 103. Durch zwei ganzzahlige Divisionen und zwei Tabellen-Lookups haben wir es geschafft um die möglichen Werte von x auf 1/120 von Zahlen zu begrenzen.
Wenn die Tabellen größer sind, ist die Anzahl der möglichen x s leicht auf eine sehr niedrige Anzahl zu begrenzen. Bei Tabellen mit 65536 und 65535 Elementen ist der Zyklus z. B. 4294901760, sodass für jede Zahl unter etwa 1,6 x 10 ^ 19 die beiden Tabellen eine kurze eindeutige Liste möglicher Werte von x enthalten.
Wenn Sie n faktorisieren können, dann ist es einfach, eine Antwort zu finden, indem Sie die Multiplizitäten der Faktoren untersuchen. Aber die übliche Verwendung zum Bestimmen, ob eine Zahl eine perfekte Leistung ist, ist ein vorläufiger Test für einige Factoring-Algorithmen, in welchem Fall es nicht realistisch ist, die Faktoren von n zu finden.
Der Trick, um zu bestimmen, ob eine Zahl eine perfekte Potenz ist, besteht darin zu wissen, dass, wenn die Zahl eine perfekte Potenz ist, der Exponent e kleiner sein muss als log2 n , denn wenn e größer ist als 2 e ist größer als n . Außerdem ist es nur notwendig, prime e s zu testen, denn wenn eine Zahl eine perfekte Potenz für einen zusammengesetzten Exponenten ist, ist sie auch eine perfekte Potenz für die Primfaktoren der zusammengesetzten Komponente; zum Beispiel ist 2 15 = 32768 = 32 3 = 8 5 eine perfekte Kubikwurzel und auch eine perfekte fünfte Wurzel. Hier ist Pseudocode für eine Funktion, die b zurückgibt, wenn es einen Exponenten e gibt, so dass b e = n oder 0 falls nicht; Die Funktion root(e,n) gibt die e -te Wurzel von n zurück:
Ich diskutiere diese Funktion im Blog .
Wenn die Faktorisierung zu schwierig ist, können Sie alternativ Ihre Mathebibliothek ausnutzen und viele Werte von x oder y ausprobieren, bis Sie eine finden, die funktioniert.
Der Versuch nach y wird weniger Arbeit sein, wenn Sie eine Operation "y-te Wurzel von n" haben (sie könnte sich unter dem Namen "x zur Potenz von 1 / y" maskieren). Probieren Sie einfach alle ganzzahligen Werte von y größer als 2 aus, bis Sie entweder eine ganzzahlige Antwort erhalten oder das Ergebnis unter 2 fällt. Wenn n eine standardmäßige 32-Bit-Ganzzahl ist, dauert es nicht mehr als 32 Versuche ( und, allgemeiner, wenn n eine m-Bit-Ganzzahl ist, dann wird es nicht mehr als m Versuche dauern.)
Wenn Sie nicht die "y-te Wurzel von n" haben, können Sie alle x mit der Operation "log base x of n" versuchen, bis Sie eine ganzzahlige Antwort erhalten oder das Ergebnis unter 2 fällt mehr Arbeit, da Sie alle Werte bis zur Quadratwurzel von x überprüfen müssen. Ich denke, dass es möglich sein sollte, dies irgendwie zu optimieren und bei möglichen ganzzahligen Ergebnissen "nach Hause" zu gehen.
Der Exponent y ist leicht begrenzt 2 ≤ y ≤ log_2 (n). Testen Sie jedes y in diesem Bereich. Wenn es existiert, ist x der ganzzahlige yth Stamm von n.
Der Punkt ist, während x y bestimmt und umgekehrt, der Suchraum für y ist viel kleiner, also sollten Sie y statt x suchen (was so groß wie sqrt (n) sein könnte).