Schreiben Sie ein Programm oder eine Funktion, die die Anzahl der Nullen am Ende von n!
Basis 10 ermittelt, wobei n
es sich um eine eingegebene Zahl handelt (in einem beliebigen Format).
Es kann davon ausgegangen werden, dass n
es sich um eine positive ganze Zahl handelt, was bedeutet, dass n!
es sich auch um eine ganze Zahl handelt. Nach dem Komma stehen in keine Nullen n!
. Es kann auch davon ausgegangen werden, dass Ihre Programmiersprache den Wert von n
und verarbeiten kann n!
.
Testfälle
1
==> 0
5
==> 1
100
==> 24
666
==> 165
2016
==> 502
1234567891011121314151617181920
==> 308641972752780328537904295461
Das ist Code Golf. Es gelten Standardregeln. Der kürzeste Code in Bytes gewinnt.
Einreichungen
Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:
# Language Name, N bytes
Wo N
ist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:
# Ruby, <s>104</s> <s>101</s> 96 bytes
Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:
# Perl, 43 + 2 (-p flag) = 45 bytes
Sie können den Namen der Sprache auch als Link festlegen, der dann im Leaderboard-Snippet angezeigt wird:
# [><>](http://esolangs.org/wiki/Fish), 121 bytes
Bestenliste
Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren.
/* Configuration */
var QUESTION_ID = 79762; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 43444; // This should be the user ID of the challenge author.
/* App */
var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;
function answersUrl(index) {
return "https://api.stackexchange.com/2.2/questions/" + QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}
function commentUrl(index, answers) {
return "https://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}
function getAnswers() {
jQuery.ajax({
url: answersUrl(answer_page++),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
answers.push.apply(answers, data.items);
answers_hash = [];
answer_ids = [];
data.items.forEach(function(a) {
a.comments = [];
var id = +a.share_link.match(/\d+/);
answer_ids.push(id);
answers_hash[id] = a;
});
if (!data.has_more) more_answers = false;
comment_page = 1;
getComments();
}
});
}
function getComments() {
jQuery.ajax({
url: commentUrl(comment_page++, answer_ids),
method: "get",
dataType: "jsonp",
crossDomain: true,
success: function (data) {
data.items.forEach(function(c) {
if (c.owner.user_id === OVERRIDE_USER)
answers_hash[c.post_id].comments.push(c);
});
if (data.has_more) getComments();
else if (more_answers) getAnswers();
else process();
}
});
}
getAnswers();
var SCORE_REG = /<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;
var OVERRIDE_REG = /^Override\s*header:\s*/i;
function getAuthorName(a) {
return a.owner.display_name;
}
function process() {
var valid = [];
answers.forEach(function(a) {
var body = a.body;
a.comments.forEach(function(c) {
if(OVERRIDE_REG.test(c.body))
body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
});
var match = body.match(SCORE_REG);
if (match)
valid.push({
user: getAuthorName(a),
size: +match[2],
language: match[1],
link: a.share_link,
});
});
valid.sort(function (a, b) {
var aB = a.size,
bB = b.size;
return aB - bB
});
var languages = {};
var place = 1;
var lastSize = null;
var lastPlace = 1;
valid.forEach(function (a) {
if (a.size != lastSize)
lastPlace = place;
lastSize = a.size;
++place;
var answer = jQuery("#answer-template").html();
answer = answer.replace("{{PLACE}}", lastPlace + ".")
.replace("{{NAME}}", a.user)
.replace("{{LANGUAGE}}", a.language)
.replace("{{SIZE}}", a.size)
.replace("{{LINK}}", a.link);
answer = jQuery(answer);
jQuery("#answers").append(answer);
var lang = a.language;
if (/<a/.test(lang)) lang = jQuery(lang).text();
languages[lang] = languages[lang] || {lang: a.language, user: a.user, size: a.size, link: a.link};
});
var langs = [];
for (var lang in languages)
if (languages.hasOwnProperty(lang))
langs.push(languages[lang]);
langs.sort(function (a, b) {
if (a.lang > b.lang) return 1;
if (a.lang < b.lang) return -1;
return 0;
});
for (var i = 0; i < langs.length; ++i)
{
var language = jQuery("#language-template").html();
var lang = langs[i];
language = language.replace("{{LANGUAGE}}", lang.lang)
.replace("{{NAME}}", lang.user)
.replace("{{SIZE}}", lang.size)
.replace("{{LINK}}", lang.link);
language = jQuery(language);
jQuery("#languages").append(language);
}
}
body { text-align: left !important}
#answer-list {
padding: 10px;
width: 290px;
float: left;
}
#language-list {
padding: 10px;
width: 290px;
float: left;
}
table thead {
font-weight: bold;
}
table td {
padding: 5px;
}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="answer-list">
<h2>Leaderboard</h2>
<table class="answer-list">
<thead>
<tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
</thead>
<tbody id="answers">
</tbody>
</table>
</div>
<div id="language-list">
<h2>Winners by Language</h2>
<table class="language-list">
<thead>
<tr><td>Language</td><td>User</td><td>Score</td></tr>
</thead>
<tbody id="languages">
</tbody>
</table>
</div>
<table style="display: none">
<tbody id="answer-template">
<tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
<table style="display: none">
<tbody id="language-template">
<tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
</tbody>
</table>
n
eine Eingabezeichenfolge sein?n!
dürften, dass sie in Ihren Integer-Typ passt! Na ja, vielleicht ein anderes Mal.Antworten:
Python 2, 27 Bytes
Die Endung Nullen sind begrenzt durch Faktoren von 5. Die Anzahl der Vielfachen ,
5
dass es höchstensn
istn/5
(mit Boden Division), aber dies die wiederholten Faktoren in Vielfachen von nicht zählen25, 125, ...
. Um diese zu erhalten, dividieren Sien
durch 5 und wiederholen Sie den Vorgang.quelle
Gelee , 5 Bytes
Verwendet den kontraproduktiven Ansatz, die Fakultät zu finden und sie dann erneut zu faktorisieren und in der Primfaktorisierung nach dem Exponenten von 5 zu suchen.
Probieren Sie es online!
quelle
Mornington Crescent,
19491909 Bytes-40 Bytes dank NieDzejkob
quelle
Mornington Crescent
wäre cool. :)Pyth, 6 Bytes
Probieren Sie es hier aus.
Alternative 7-Byte :
Das kumulative Reduzieren
.u/N5
teilt sich5
so oft, bis es eine Wiederholung erhält, was in diesem Fall geschieht, nachdem es 0 erreicht hat.Das erste Element wird dann entfernt (
t
) und der Rest summiert (s
).quelle
Eigentlich 10 Bytes
Probieren Sie es online!
Beachten Sie, dass der letzte Testfall fehlschlägt, wenn Seriously auf CPython ausgeführt wird, weil
math.factorial
eine C-Erweiterung verwendet wird (die auf 64-Bit-Ganzzahlen beschränkt ist). Seriously auf PyPy auszuführen, funktioniert jedoch einwandfrei.Erläuterung:
quelle
Haskell, 26 Bytes
Floor dividiert die Eingabe durch
5
und fügt das Ergebnis der aufgerufenen Funktion hinzu. Der Ausdruck(+)=<<f
nimmt eine Eingabex
und Ausgabenx+(f x)
.Gekürzt ab:
Ein nicht rekursiver Ausdruck ergab 28 Bytes:
quelle
i
ein Zähler von1..n
?log_5(n)
der Rest gibt 0.MATL , 9 Bytes
Probieren Sie es online!
Dies funktioniert bei sehr großen Zahlen, da die Fakultät nicht berechnet wird.
Wie bei anderen Antworten wird auch hier die Tatsache ausgenutzt, dass die Häufigkeit des
2
Auftretens als Teiler der Fakultät größer oder gleich der Häufigkeit des Auftretens ist5
.quelle
05AB1E, 5 Bytes
Wäre 4 Bytes, wenn wir garantieren könnten, dass n> 4 ist
Code:
Erläuterung:
Alternative, viel schnellere 6-Byte-Lösung: Inspiriert von Luis Mendos MATL-Antwort
Erläuterung:
Bearbeiten: Entfernte Lösungen mit ¢ (count), da alle Primzahlen mit 5 als 5 gezählt würden, z. B. 53.
Edit 2: Es wurde eine effizientere Lösung für höhere Eingaben als Vergleich hinzugefügt.
quelle
5¢
,5Q
sollte funktionieren. Gute Antwort! :)Ó
ist langsamÎ!Ó2é
. Der Fehler wurde gestern behoben .Î!Ó7è
es 8 Byte, und die "6 Byte" -Lösung ist 10 ByteMatlab
(59) (54)(39)Hey dawg !!!! Wir haben gehört, dass du Mathe magst ...
Dies basiert auf meiner Antwort in der Codeüberprüfung .
weiter als in meiner Antwort in der Codeüberprüfung erwähnt, lautet die Formel für die Anzahl der Nullen in der Fakultät (n) Summe (n / (5 ^ k)), wobei k zwischen 1 und log_5 (n) variiert.
Der einzige triviale Grund, warum es nicht Golfspieler werden kann, ist, dass
log5
es in Matlab nicht als eingebautes Programm verfügbar ist. Daher habe ich log (5) durch 1.6 ersetzt. Das spielt keine Rolle, da es sowieso mit Fußboden ausgelegt sein wird.Versuche es
quelle
Mathematica, 20 Bytes
IntegerExponent
zählt die Nullen. Zum Spaß ist hier eine Version, die die Fakultät nicht berechnet:quelle
Array
spart ein Byte bei der zweiten Lösung.C 28 Bytes
Erläuterung
Die Anzahl der nachgestellten Nullen entspricht der Anzahl der Fünfer, aus denen sich die Fakultät zusammensetzt. Von all dem
1..n
trägt ein Fünftel eine Fünf bei, also fangen wir ann/5
. Von diesenn/5
ist ein Fünftel ein Vielfaches von 25, tragen also weitere fünf bei und so weiter. Wir landen mitf(n) = n/5 + n/25 + n/125 + ...
, was istf(n) = n/5 + f(n/5)
. Wir müssen die Rekursion beenden, wennn
Null erreicht wird. Wir nutzen auch den Sequenzpunkt?:
, umn
vor der Addition zu teilen .Als Bonus ist dieser Code viel schneller als derjenige, der jeden besucht
1..n
(und viel schneller als die Berechnung der Fakultät).Testprogramm
Ausgang testen
quelle
JavaScript ES6, 20 Byte
Gleiche Taktik wie bei xnors Antwort, aber kürzer.
quelle
Julia,
343130 BytesDies ist eine anonyme Funktion, die jeden vorzeichenbehafteten Ganzzahltyp akzeptiert und eine Ganzzahl zurückgibt. Um es aufzurufen, weisen Sie es einer Variablen zu. Die größeren Testfälle erfordern das Bestehen
n
als größerer Typ, wie zBigInt
.Wir berechnen die Fakultät von
n
(die manuelle Verwendungprod
ist kürzer als die eingebautefactorial
), erhalten ein Arraydigits
in umgekehrter Reihenfolge,find
die Indizes der Nicht-Null-Elemente, erhalten den ersten solchen Index und subtrahieren 1.Probieren Sie es online! (Beinhaltet alle bis auf den letzten Testfall, da der letzte zu lange dauert)
Dank Dennis ein Byte gespart!
quelle
C, 36
Die gleiche Methode wie bei @ xnor, bei der 5s gezählt werden, jedoch nur eine einfache for-Schleife anstelle einer Rekursion verwendet wird.
Ideone .
quelle
Retina , 33 Bytes
Nimmt unäre Eingaben auf.
Gibt die Ausgabe in Unary zurück.
(Beachten Sie den nachfolgenden Zeilenumbruch.)
Probieren Sie es online!
Wie es funktioniert:
Die erste Stufe:
Leicht ungolfed:
Was es macht:
11111
, die abgeglichen werden kann.5
.(?=1)
versichert, dass die Zahl positiv ist.+`
Mittel wiederholen sich bis zum Idempotenten.Wenn die Eingabe 100 ist (in Unary), lautet der Text jetzt:
Zweite Etage:
Entfernt einfach alle Semikolons.
quelle
Ruby, 22 Bytes
Eines der wenigen Male, in denen die
0
Wahrheit des Rubins ein Problem für die Byteanzahl ist.quelle
0
wahr?nil
undfalse
sind Falsche, und sonst ist nichts. Es gibt viele Fälle, in denen beim Golfen0
geholfen wird , da Wahrhaftigkeit bedeutet, dass die Index- und Regex-Indexfunktionen in Ruby zurückgegeben werden,nil
wenn es keine Übereinstimmung gibt-1
, und einige Fälle, in denen dies ein Problem darstellt, z. B. wenn leere Zeichenfolgen immer noch wahr sind.Perl 6 , 23 Bytes
Ich könnte es kürzer machen, wenn
^...
es zu Perl 6 hinzugefügt würde{sum $_,*div 5^...0}
.Bei größeren Zahlen sollte es speichereffizienter sein, wenn Sie
lazy
zwischensum
und dem Sequenzgenerator einen Modifikator einfügen.Erläuterung:
Prüfung:
(Diese letzte Zeile ist leicht irreführend, da MoarVM starten, den Perl 6-Compiler und die Laufzeit laden, den Code kompilieren und ausführen muss. Es dauert also insgesamt ungefähr anderthalb Sekunden.
Das ist immer noch erheblich schneller als es ist war das Ergebnis des letzten Tests mit WolframAlpha.com zu überprüfen)
quelle
Mathcad, [tbd] Bytes
Mathcad ist eine Art mathematisches "Whiteboard", das die 2D-Eingabe von Ausdrücken, Text und Zeichnungen ermöglicht. Es werden mathematische Symbole für viele Operationen wie Summation, Differenzierung und Integration verwendet. Programmieroperatoren sind spezielle Symbole, die normalerweise als einzelne Tastenkombinationen von Steuerung und / oder Umschalttaste auf einer Standardtaste eingegeben werden.
Was Sie oben sehen, ist genau, wie das Mathcad-Arbeitsblatt so aussieht, wie es eingegeben und wie es von Mathcad ausgewertet wird. Wenn Sie beispielsweise n von 2016 auf einen anderen Wert ändern, aktualisiert Mathcad das Ergebnis von 502 auf den neuen Wert.
http://www.ptc.com/engineering-math-software/mathcad/free-download
Die Methode zur Bewertung der Byte-Äquivalenz von Mathcad muss noch ermittelt werden. Bei einer Symboläquivalenz benötigt die Lösung etwa 24 "Bytes" (der while-Operator kann nur über die Tastenkombination "ctl-]" (oder über eine Symbolleiste) eingegeben werden. Die Matlab-Methode von Agawa001 benötigt bei der Übersetzung in Mathcad ca. 37 Byte (der Summationsoperator wird mit ctl-shft- $ eingegeben).
quelle
Gleichstrom, 12 Bytes
Dies definiert eine Funktion,
f
die ihre Eingabe vom oberen Ende des Stapels verbraucht und ihre Ausgabe am oberen Ende des Stapels belässt. Siehe meine C-Antwort für die mathematische Basis. Wir teilen wiederholt durch 5, akkumulieren die Werte auf dem Stapel und addieren dann alle Ergebnisse:Testprogramm
Ausgang testen
quelle
Jolf, 13 Bytes
Definiert eine rekursive Funktion, die am Eingang aufgerufen wird. Probieren Sie es hier aus!
quelle
J,
281716 BytesZiemlich dasselbe wie die nicht-rekursive Technik aus der Antwort von xnor.
Hier ist eine ältere Version, die ich hier behalten habe, weil es mir persönlich besser gefällt und ich mit 28 Bytes anfange:
Obwohl nicht benötigt, habe ich
x:
in die Testfälle für erweiterte Präzision aufgenommen.Die letzte Nummer funktioniert mit dieser Funktion nicht.
Erläuterung
Dies funktioniert, indem berechnet
n!
, in eine Zeichenfolge konvertiert und jedes Element auf Gleichheit mit überprüft wird'0'
. Dennn = 15
dieser Prozess wäre:Nun
;._1
teilen wir die Liste auf das erste Element (Null) auf , wobei wir jedes Teilungsergebnis boxen und eine Box mit Assen (a:
) oder Läufen von1
s erhalten, wie folgt:Wir erhalten einfach das letzte Mitglied (
{:
), entpacken es (>
) und addieren es+/
, wobei wir die Anzahl der Nullen erhalten.Hier ist die besser lesbare Version:
quelle
>:@i.
kann geschrieben werden1+i.
, um ein Byte zu speichern.[:#.~'0'=":@!
durch Ändern der Methode zum Zählen der nachgestellten Einsen in 13 Bytes umgewandelt werden.Python 3, 52 Bytes
quelle
Pyke, 5 Bytes
Probieren Sie es hier aus!
quelle
RETURN , 17 Bytes
Try it here.
Rekursiver Operator Lambda. Verwendung:
Erläuterung
quelle
Perl,
2422 + 1 (-p
Flag) = 23 BytesVerwenden von:
Volles Programm:
quelle
Java, 38 Bytes
Volles Programm mit ungolfed Methode:
quelle
J, 7 Bytes
Monadische Funktion, rechts argumentierend.
Wenn
x
positiv, werdenx q: y
die Exponenten in einer Primfaktorisierung vony
nur für die erstenx
Primzahlen zurückgegeben. Die3
-rd-Primzahl ist 5 und steht{:
am Ende einer Liste.Beachten Sie, dass Sie ganze Zahlen mit einem
x
am Ende eingeben müssen, andernfalls werden sie von J als Gleitkommazahlen behandelt.Probieren Sie es selbst bei tryj.tk jedoch, dass sich dieser Online-Dolmetscher beschwert, wenn Sie etwas versuchen, das größer als 1343 ist.
Wenn Sie etwas wollen, das n nicht berechnet ! und daher muss es nicht in eine ganze Zahl passen, verwenden Sie die rekursive Lösung
<.@%&5(+$:@)^:*
. (tryj.tk meckert immer noch bei großen Eingaben.)quelle
Ruby,
70615149 BytesVersion 3 mit Dank an Kenny Lau und daniero
Bearbeiten: Es hat sich herausgestellt, dass Sie durch Zuordnen
to_i
vor Ihnen zwei Bytes sparen könnenreduce
. Seltsam: PDiese Funktion subtrahiert die Summe der
n
fünf Stellen der Basis vonn
und dividiert das Ergebnis durch 4. Dies bezieht sich auf die Summe der geometrischen Reihen1+5+25+..+5**n = (5**n+1)/4
.Betrachten Sie als Beispiel (erneut dank Kenny Lau)
358
(2413
in Basis 5) minus der 5-stelligen Basis.Teilen Sie
348
durch4
und Sie bekommenf(358) = 87
.Version 2 mit Dank an Kenny Lau
Diese Funktion berechnet
n!
und subtrahiert dann dassize
vonn!
vomsize
von(n!).reverse.to_i.to_s
, wodurch alle Nullen entfernt werden und somit dassize
von den Nullen selbst zurückgegeben wird.Version 1
Dies ist eine Variation der "Wie viele
5
s gibt es in der Primfaktorisierung vonn!
?" Trick, der Rubys einfache integrierte Basisumwandlung verwendet.Der Golf ist ein bisschen wie ein Schmerz aber, mit der Umwandlung von
Integer
bisString
zuArray
, einen Teil des für die HeimelfArray
und Umwandeln dassString
zuInteger
wieder für diereduce
. Anregungen zum Golfen sind willkommen.quelle
to_i
bevor es reduziert wird:->n{(n-n.to_s(5).chars.map(&:to_i).reduce(:+))/4}
(spart zwei Bytes)Julia,
2119 BytesVerwendet die rekursive Formel aus der Antwort von xnor .
Probieren Sie es online!
quelle
Dyalog APL , 9 Bytes
⎕
Aufforderung zur Eingabe der Nummer!
faktorisieren⍕
stringifizieren'0'=
Überprüfen Sie die Gleichheit mit dem Zeichen Null⊥⍨
zähle nachfolgende Wahrheiten ** Es handelt sich buchstäblich um eine gemischte Basis-Basis-10-Konvertierung, wobei die Boolesche Liste sowohl als Zahl als auch als Basis verwendet wird:
⊥⍨0 1 0 1 1
ist das Gleiche wie0 1 0 1 1⊥⍨0 1 0 1 1
das,0×(0×1×0×1×1) 1×(1×0×1×1) 0×(0×1×1) 1×(1×1) + 1×(1)
was wiederum zwei ist (die Anzahl der nachgestellten Einsen).quelle