Wenn Sie ein wenig Mühe haben, berechnen Sie die Anzahl der nachgestellten Nullen in einer Fakultät einer gegebenen Zahl. Das ist eine der Herausforderungen von Codewars - ich kann meine nicht durchgehen lassen.
%Vor%Ich denke ich bin hier auf dem falschen Weg und es gibt wahrscheinlich einen eleganteren Rubinweg. Das ist, was ich bis jetzt heruntergekommen bin.
%Vor%Dies ist eher eine mathematische Frage. Und du hast Recht, du bist auf einem falschen Weg. (Ich meine, der Weg, auf dem Sie sich befinden, wird zu einer sehr ineffizienten Lösung führen)
Versuchen Sie, das Problem zuerst mathematisch zu reduzieren. (Übrigens, Sie arbeiten für einen Log-N-Order-Algorithmus.)
In meiner Antwort werde ich versuchen, ein paar Schritte zu überspringen, weil es wie eine Hausaufgabenfrage aussieht.
Die Anzahl der nachgestellten Nullen wird gleich der Gesamtleistung von 5s bei der Multiplikation der Reihe sein.
Die Zahlen zwischen 1 und n haben n/5 , n/25 , n/125 Zahlen, die ein Vielfaches von 5s, 25s, 125s usw. sind.
Versuchen Sie, diese Hinweise zu nehmen und einen Algorithmus zu entwickeln, um zu zählen, wie viele Potenzen von 10 in diesen Faktor eingepfercht werden.
Ich habe beschlossen, es im Detail zu erklären. Wenn Sie also versuchen wollen, es selbst zu lösen, hören Sie auf zu lesen, versuchen Sie darüber nachzudenken und kommen Sie dann hierher zurück.
Hier ist eine schrittweise Reduzierung des Problems
Die Anzahl der nachgestellten Nullen in einer Zahl entspricht der Potenz von 10 im Faktor dieser Zahl
z.B.
40 = 4 * 10^1 und es hat 1 abschließende Null 12 = 3 * 4 * 10^0 , also 0 nachgestellte Nullen 1500 = 3 * 5 * 10^2 , so dass es 2 abschließende Nullen Die Anzahl der Potenz von 10 in den Faktoren entspricht der Potenz von 2 und der Potenz von 5 in den Faktoren
z.B.
50 = 2^1 * 5^2 , also ist die minimale Leistung 1 300 = 3^1 * 2^2 * 5^2 , also ist das Minimum 2 (wir sind nur mit dem Minimum der Potenzen von 2 und 5 beschäftigt, also ignoriere Potenzen von 3 und allen anderen Primfaktoren) In jedem Fakultät gibt es viel mehr Potenzen von 2 als die Potenzen von 5
z.B.
5! = 2^3 * 3^1 * 5^1 10! = 2^8 * 3^4 * 5^2 * 7^1 Wie Sie sehen können, wird die Potenz von 2 viel schneller ansteigen, so dass die Potenz von 5 das Minimum der beiden sein wird.
Daher müssen wir nur die Potenz von 5 in der Fakultät zählen.
Lasst uns jetzt in jedem n!
4! ~ 5^0 5! ~ 5^1 (bis zu 9! ) 10! ~ 5^2 (bis zu 14! ) 15! ~ 5^3 (bis '19!) 20! ~ 5^4 (bis zu 24! ) 25! ~ 5^6 (beachten Sie den Sprung von 5^4 nach 5^6 , da die Zahl 25 zwei Potenzen von 5 hinzufügt) Die Art, wie ich die Gesamtkraft von fünf in einer Fakultät zählen möchte, ist ... zählt alle Vielfachen von 5, addiert sie alle eine Potenz von 5. Dann zählen alle Vielfachen von 25, sie addieren alle ein zusätzliche Macht von 5. Beachten Sie, wie 25 zwei Potenzen von 5 hinzugefügt, so kann ich das als eine Macht, weil es ein Vielfaches von 5 und eine zusätzliche Macht, weil es ein Vielfaches von 25 ist. Dann zählen Sie alle das Vielfache von 125 ( 5^3 ) in der Fakultätsmultiplikation addieren sie eine weitere Extrapower von 5 ... und so weiter.
Also, wie hast du das als Algorithmus dargestellt?
lässt sagen, die Zahl ist n . Also ...
pow1 = n/5 (abgerundet auf eine Ganzzahl) pow2 = n/25 pow3 = n/125 und so weiter ...
Jetzt die Gesamtleistung pow = pow1 + pow2 + pow3 ...
Kannst du das jetzt als Schleife ausdrücken?
Nun, da @Spunden die Katze so kunstvoll aus der Tasche gelassen hat, ist hier eine Möglichkeit, sie umzusetzen.
Code
%Vor%Beispiele
%Vor%Erläuterung
Angenommen n = 128 .
Dann stellt jede Zahl zwischen eins und 128 (inklusive), die durch 5^1=>5 teilbar ist, mindestens einen Faktor zur Verfügung, und es gibt 128/5 => 25 solcher Zahlen. Von diesen sind die einzigen, die mehr als einen Faktor bereitstellen, diejenigen, die durch 5^2=>25 teilbar sind, von denen es 128/25 => 5 ( 25, 50, 75, 100, 125 ) gibt. Von diesen gibt es aber 128/125 => 1 , die mehr als zwei Faktoren liefert, und da 125/(5^4) => 0 keine Zahlen mehr als drei Teiler beitragen. Daher ist die Gesamtzahl von fünf Teilern:
(Beachten Sie, dass für 125 , das drei Teiler von 5 hat, eins in jedem dieser drei Begriffe gezählt wird; für 25 , 50 usw., die jeweils zwei Faktoren von% haben co_de%, eins wird in jedem der ersten Terme gezählt.)
Für beliebig 5 berechnen wir zuerst die höchste Potenz n , für die gilt:
was ist:
%Vor%Der größte Wert ist also:
%Vor% Wie @spundun angemerkt hat, könnten Sie k auch einfach durch Iteration berechnen, z. B.
Die Gesamtzahl der Faktoren von fünf ist daher
%Vor%Definieren:
%Vor%Diese Summe wird gesehen:
%Vor%wo
%Vor% Der Wert von k ist die Summe der Terme einer geometrischen Reihe. Ich vergesse die Formel dafür, aber erinnere mich, wie sie abgeleitet ist:
Ich habe dann eine Umordnung vorgenommen, so dass nur die Ganzzahlarithmetik zur Berechnung des Ergebnisses verwendet wurde.
Hier ist eine Lösung, die einfacher zu lesen ist:
%Vor%Lassen Sie mich wissen, was Sie denken und gerne bearbeiten können, wenn Sie eine Verbesserung sehen!
Der Artikel Eine Anmerkung zu Factorial und seinen nachfolgenden Nullen in GanitCharcha ist aufschlussreich und hat die Mathematik hinter diesem Brunnen erklärt. Schau es dir an.
Laut der Erklärung von @spundan und abgesehen von @ cary's Code können Sie die Anzahl der nachgestellten Nullstellen auf sehr einfache und effiziente Weise finden .. siehe unter Code ..
%Vor% Zum Beispiel Nullen (100000000) Dies gibt Ihnen die Ausgabe - & gt; 24999999
Mit der Zeit Zeit abgelaufen - & gt; 5.0453d-05 (Siehe 5.0453d-05 )
Dies ist der Teil von sogar Millisekunden.
Wenn N eine Zahl ist, dann ist die Anzahl der abschließenden Nullen in N! ist
N/5 + N/5^2 + N/5^3 ..... N/5^(m-1) WHERE (N/5^m)<1
Sie können hier erfahren, wie diese Formel zustande kommt.