Die Einführung eines schnellen Power -Modulalgorithmus wird durch die Grenzen eines naiven Algorithmus vorgeschlagen, der den Modul aus den Dezimalstellen großer Zahlen enthält. Bei der naiven Methode berechnen wir eine Zahl wie 5^1003%31, die unsere Rechenressourcen sehr verbraucht. Das Problem im gesamten Berechnungsprozess ist unser 5^1003 -Prozess.
Nachteil 1: Bei der Berechnung des Index später sind die berechneten Zahlen nicht alle erhöht, was viele unserer Rechenressourcen (hauptsächlich Zeit und Raum) einnimmt
Nachteil 2: Die Zahlen unserer Berechnung sind so groß, dass unsere vorhandenen Computer so lange Daten nicht aufzeichnen können. Daher müssen wir uns eine effizientere Möglichkeit vorstellen, dieses Problem zu lösen.
Wenn wir AB%C berechnen, ist es am bequemsten, die POW -Methode in der Mathematikfunktion aufzurufen. Manchmal ist die Anzahl A bis die Kraft von B jedoch zu groß, und sogar das Doppelprezisionsdoppel überläuft. Um das Ergebnis von AB%C zu erhalten, werden wir den Fast Power Modulus -Algorithmus verwenden, um das gewünschte Ergebnis einfach und schnell zu erhalten.
Um zu verhindern, dass Zahlen überfließen und die Komplexität verringern, müssen wir die folgende Formel verwenden:
ABMOD C = (A MOD C) BMOD C
Die Bedeutung dieser Formel lautet: Das Produkt übernimmt den Rest gleich dem Produkt. Es ist leicht zu erkennen, dass diese Formel transitiv ist, damit wir einen immer kleineren machen können, indem wir ständig den Rest nehmen, um Überlauf zu verhindern.
Theoretisch können wir mit dieser Formel Code schreiben. Durch ständiges Moduloieren von A stellen wir sicher, dass das Ergebnis nicht überflutet. Dies kann in der Tat den Modul einer Leistung zu einer größeren Leistung berechnen, aber die Komplexität dieser Methode ist immer noch o (n) und nicht schnell.
Um den Modul einer Leistung schneller zu berechnen, müssen wir uns auch auf die folgende Formel verlassen:
AB Mod C = (A2) B/2 Mod C, B ist eine gleichmäßige Zahl
AB mod c = ((a2) b/2 ・ a) mod c, b ist eine ungerade Zahl
Diese Formel ist sehr einfach. Das Prinzip besteht darin, B ständig durch das Quadrat von A zu ersetzen und B durch die ursprüngliche Hälfte zu ersetzen. Weil wir durch die erste Formel wissen, dass das Modul einer Zahl die gleiche Leistung hat (dieser Satz ist etwas verwirrend, was die Formel 1 bedeutet). Dann ist der Effekt der Verwendung des Ergebniss von a*a%c anstelle von a gleich.
Nach der obigen Formel erhalten wir also eine Methode zur Berechnung der schnellen Leistung mit Komplexität O (logn):
import Java.util.scanner; public class main {public static void main (String [] args) {scanner in = neuer Scanner (System.in); int a = in.nextint (), b = in.nextint (), c = in.nextint (); int res = 1; a %= c; für (; b! = 0; b /= 2) {if (b % 2 == 1) res = (res * a) % c; a = (a * a) % c; } System.out.println (res); }}Dieser Algorithmus ist ungefähr so. Der erste Schritt besteht darin, einen%= C zu reduzieren, um zu verhindern, dass die Anzahl überflutet wird, wenn ein*A erstmals durchgeführt wird. Wenn B in der for -Schleife eine ungerade Zahl ist, sei res = res*a und dann zuerst in das Ergebnis multiplizieren und dann verarbeiten. Um zu verhindern, dass die Anzahl überflutet ist, wird das Ergebnismod C von Res*direkt betrieben. In diesem Fall wird B für die Schleife früher oder später 1 gleich 1 eingeben, den IF -Zweig eingeben und schließlich den Wert von res und mod C berechnen, und dann verlässt C die für die Loop und dann das Endergebnis.
Zusammenfassen
Das obige ist die detaillierte Erklärung dieses Artikels zur Implementierung des Fast Power Modulus -Algorithmus der Java -Sprache. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf andere verwandte Themen auf dieser Website verweisen. Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!