Ich versuche, nachgestellte Nullen von Zahlen zu zählen, die aus faktoriellen Zahlen resultieren (was bedeutet, dass die Zahlen ziemlich groß werden). Der folgende Code nimmt eine Zahl an, berechnet die Fakultät der Zahl und zählt die abschließenden Nullen. Wenn die Zahl jedoch ungefähr so groß wie 25 ist, funktionieren NumZeros nicht.
%Vor%Ich mache mir keine Gedanken um die Effizienz dieses Codes, und ich weiß, dass es mehrere Möglichkeiten gibt, die Effizienz dieses Codes BESSERER zu machen. Was ich herausfinden will, ist der Grund, warum die nachgestellten Nullen von Zahlen, die größer als 25 sind, gezählt werden! funktioniert nicht.
Irgendwelche Ideen?
Ihre Aufgabe besteht nicht darin, die Fakultät zu berechnen, sondern die Anzahl der Nullen. Eine gute Lösung verwendet die Formel aus Ссылка (die Sie beweisen können)
%Vor%Ich hoffe, Sie können dies in Java übersetzen. Dies berechnet einfach [n / 5] + [n / 25] + [n / 125] + [n / 625] + ... und stoppt, wenn der Teiler größer als n wird.
Verwenden Sie KEINE BigIntegers. Dies ist ein Bozosort. Solche Lösungen benötigen Sekunden für große Zahlen.
Sie müssen nur wirklich wissen, wie viele 2er und 5er es im Produkt gibt. Wenn Sie nachgestellte Nullen zählen, dann zählen Sie tatsächlich "Wie oft teilen zehn diese Zahl?". wenn du n repräsentierst! als q * (2 ^ a) * (5 ^ b), wobei q nicht durch 2 oder 5 teilbar ist. Wenn Sie dann nur das Minimum von a und b im zweiten Ausdruck nehmen, erhalten Sie die Anzahl der 10 Teile. Tatsächlich ist die Multiplikation Overkill.
Bearbeiten: Das Zählen von Zweien ist auch Overkill, also brauchst du nur die Fünf.
Und bei einigen Pythons sollte das funktionieren:
%Vor%Meine 2 Cent: Vermeiden Sie, mit Double zu arbeiten, da sie fehleranfällig sind. Ein besserer Datentyp ist in diesem Fall BigInteger , und hier gibt es eine kleine Methode, die Ihnen helfen wird:
%Vor%Sie können ein DezimalFormat verwenden, um große Zahlen zu formatieren. Wenn Sie Ihre Nummer auf diese Weise formatieren, erhalten Sie die Nummer in wissenschaftlicher Notation , dann wird jede Zahl wie 1.4567E7 sein Machen Sie Ihre Arbeit viel einfacher. Weil die Zahl nach dem E - die Anzahl der Zeichen hinter dem. sind die Anzahl der abschließenden Nullen, denke ich.
Ich weiß nicht, ob das genau das richtige Muster ist. Sie können sehen, wie Sie die Muster hier
erstellen > %Vor%So habe ich es gemacht, aber mit größerem & gt; 25 Fakultät die lange Kapazität ist nicht genug und sollte die Klasse Biginteger verwendet werden, mit der ich noch nicht vertraut bin:)
%Vor%Ich hatte das gleiche Problem in Javascript zu lösen, und ich löste es wie folgt:
%Vor%Diese Lösung gibt Ihnen die Anzahl der abschließenden Nullen.
Java verdoppelt sich bei ein bisschen mehr als 9 * 10 ^ 18 wo als 25! ist 1,5 * 10 ^ 25. Wenn Sie in der Lage sein möchten, factorials so hoch zu haben, können Sie BigInteger verwenden (ähnlich BigDecimal, aber keine Dezimalstellen).
Am besten mit der Komplexität der logarithmischen Zeit ist Folgendes:
%Vor%schamlos kopiert von Ссылка
Ich habe das sehr schnell geschrieben, ich denke, es löst genau dein Problem. Ich habe die BigInteger-Klasse verwendet, um zu vermeiden, dass die Umwandlung von double in integer, die könnte Ihnen Probleme verursacht. Ich habe es an mehreren großen Zahlen über 25 getestet, z. B. 101, die genau 24 Nullen zurückgeben.
Die Idee hinter der Methode ist, dass wenn Sie 25 nehmen! dann ist die erste Berechnung 25 * 24 = 600, also kannst du sofort zwei Nullen abklopfen und dann 6 * 23 = 138 machen. Also berechnet es das faktorielle Entfernen von Nullen, wie es geht.
%Vor%Da du gesagt hast, dass dir die Laufzeit überhaupt egal ist (nicht dass meine erste besonders effizient war, nur ein bisschen mehr), tut sie nur die Fakultät und zählt dann die Nullen, also ist es einfacher:
> %Vor%Der doppelte Typ hat eine begrenzte Genauigkeit. Wenn also die Zahlen, mit denen Sie arbeiten, zu groß werden, ist das Doppelte nur eine Annäherung. Um dies zu umgehen, können Sie etwas wie BigInteger verwenden, um es für beliebig große Ganzzahlen zu verwenden.