Bei einer Ganzzahl von 1 ≤ N ≤ 1.000.000 als Eingabe wird die letzte Ziffer von N ungleich Null ausgegeben ! wo ! ist die Fakultät (das Produkt aller Zahlen von 1 bis einschließlich N ). Dies ist die OEIS-Sequenz A008904 .
Ihr Programm muss innerhalb von 10 Sekunden auf einem vernünftigen Computer für eine gültige Eingabe beendet sein.
Testfälle
1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4
Dies ist ein Code-Golf, also gewinnt der kürzeste Code in Bytes!
Antworten:
Ruby - 63 Zeichen
Quelle - http://oeis.org/A008904
Verarbeitet bis zu tausend Stellen in weniger als einer Sekunde.
Prüfung
quelle
Mathematica,
4536 BytesSehr gut lesbar für eine gewinnende Antwort. :) (Es gibt aber noch keinen Beitrag von GolfScript & Co.)
Dies erledigt die Eingabe von 1.000.000 in ca. 5 Sekunden auf meinem Computer.
quelle
Python - 75
quelle
PARI / GP - 27 Bytes
Dies tauscht Geschwindigkeit gegen Größe - der Testfall dauert lange (~ 6 Sekunden).
Diese Version ist viel schneller (~ 15 Mikrosekunden), benötigt aber 81 Bytes:
Mit diesem Code (ohne Golf) können Sie Folgendes testen:
quelle
Windows PowerShell, 53
565960637390Anmerkungen:
Geschichte:
$input
auf eine Zeichenfolge zu werfen . Die Umwandlung inint
wird implizit angewendet.quelle
Perl, 53
5861ZeichenAlle Leerzeichen können entfernt werden, aber ich habe es für "Lesbarkeit" belassen. Hinweis: Verwenden Sie keine alberne explizite Formel von Sloane.
Berechnet f (10 ^ 6) in 8,7 Sekunden auf meinem Computer.
Update : OP wollte, dass es ein ganzes Programm ist:
Das sind 55 Zeichen.
quelle
CJam - 28
Sie können es unter http://cjam.aditsu.net/ für Werte bis zu 10000 oder so versuchen . Für größere Zahlen sollten Sie den Java-Interpreter verwenden . 1000000 läuft in ca. 3 Sekunden auf meinem Laptop.
Erläuterung:
Leider ist die einfache Lösung zu langsam, so dass ich nach jeder Multiplikation nur die letzten 7 Ziffern (vor den nachgestellten Nullen) behalte.
Hinweis: Diese Sprache ist viel neuer als die Frage.
quelle
Mathematica, 34 Bytes
quelle
05AB1E , 4 Bytes
Probieren Sie es online!
Erläuterung
quelle
Gelee , 4 Bytes
Probieren Sie es online!
Erläuterung
Verwendet die Tatsache, dass, wenn
Ṛ
(eine Liste umkehren; nicht vektorisieren) auf eine Ganzzahl angewendet wird, diese automatisch verwendet wirdD
(Ziffern) verwendet wird.Mit Eingang 8:
Ich glaube nicht, dass es ein Ein-Byte-Element "first truthy element" gibt (das
ȯ/
als solches fungiert), aber wenn es ein solches Element gibt, kann es auf insgesamt drei Byte verkürzt werden.quelle
Java (OpenJDK 8) , 62 Byte
Probieren Sie es online!
Ähnlich wie @Kevin Cruijssen, spart jedoch 5 Bytes durch Kombinieren der Schleifen.
quelle
||
mit|
und ein zusätzliches Byte durch den Ersatz==0
mit<1
. Genieße deinen Aufenthalt!C
150140135 BytesDies ist die Version für ASCII-Systeme. Ersetzen Sie die Zeichenfolge
33436
durch11214
für ein EBCDIC-System oder durch\1\1\2\1\4
für ein tragbares Programm.C-Lösungen werden durch die Anforderung, ein vollständiges Programm bereitzustellen, etwas behindert. Dies beantwortet jedoch die Frage vollständig.
Probieren Sie es online aus (erfordert Javascript):
Erläuterung
Es basiert auf dem Algorithmus, der in der am wenigsten signifikanten Nicht-Null-Ziffer von n angegeben ist! , drehte sich um, damit wir die höchste Potenz von fünf finden und die Berechnung auf dem Weg nach draußen durchführen. Die Konstantentabellen waren zu groß, deshalb habe ich sie reduziert, indem ich eine Beziehung zwischen dem vorherigen Rest
r
, der aktuellen Zifferd
und der Rekursionstiefe gefunden habek
:Denn
r>0
dies löst sich zu konstanten Zeitenr
auf2^dk
(mod 5); Die Konstanten sinda[]
unten angegeben (im Golf Code angegeben). Wir beobachten auch, dass dies(2^4)%5
1 ist, so dass wir den Exponenten reduzieren können, um ein Überlaufen des Bereichs von zu vermeidenint
.Tests:
Auch die Leistung ist respektabel. Hier ist eine maximale Eingabe für ein System mit 32-Bit
int
:Ich habe die gleichen Timings auch mit maximal 64-Bit
int
.quelle
2147483647!
es über 19 Milliarden Stellen und(2^63-1)!
über 170.000.000.000.000.000.000 Stellen hat, also ist dies ein großer Gewinn bei der Berechnung der Fakultäten.1000000!
wie in der Frage angegeben ist es möglich, auf der aktuellen Hardware zu berechnen; das sind nur 5½ Millionen Stellen. :-)PHP - 105
Läuft mit dem angegebenen Testfall unter 10 Sekunden.
quelle
Python3
239 ZeichenKann 10000 in ~ 3,2 Sekunden erledigen (Ideone schneidet mich nach 8 Sekunden ab, ich bin mir aber sicher, dass es länger als 10 Sekunden dauern wird :()
Python2.6
299 Zeichen (etwas schneller)quelle
Haskell, 78 Zeichen
(Müsste wahrscheinlich kompiliert werden, um 1.000.000 zu berechnen! In 10 Sekunden).
quelle
foldl1
durchproduct
(siehe codegolf.stackexchange.com/questions/607/find-the-factorial/… ). Aber hast du es tatsächlich mit 1000000 versucht! ?J -
4240 ZeichenEin ganzes Programm. Speichern Sie dieses Programm in einer Datei und führen Sie es mit aus
jconsole script.ijs 1234
. Beachten Sie, dass dieses Programm den Interpreter nach dem Drucken eines Ergebnisses nicht beendet. Geben Sie^D
oder einexit]0
, um den Interpreter zu beenden.Hier ist eine Erklärung:
x #. y
interpretiert den ganzzahligen Vektory
als Basiszahlx
; zum Beispiel10 #. 1 2 3 4
Ausbeuten1234
.u inv
ergibt die Umkehrung eines Verbsu
. Insbesonderex #. inv y
stellty
alsx
Basiszahl; zum Beispiel10 #. 1234
Ausbeuten1 2 3 4
. Beachten Sie, dass diesinv
als -1-mal angewendet definiert^:_1
istu
.x * y
ist das Produkt vonx
undy
, sox 10&#.inv@* y
ergibt sich eine Base-10-Darstellung des Produktes vonx
undy
.x # y
kopiert das n- te Element vony
so oft wie das n- te Element vonx
; Wannx
ist ein Vektor von Booleschen Werten, derx
auswählt, welche Elemente genommen werden solleny
. Zum Beispiel1 0 1 0 # 1 2 3 4
Erträge1 3
.* y
ergibt das Zeichen vony
.x u~ y
ist das Reflexiv vonu
, das heißt das gleiche wiey u x
.y #~ * y
ergibt sich ein Vektor aller Elementey
, die positiv sind. In stillschweigender Schreibweise kann dies mit einem Haken als geschrieben werden(#~ *)
.{: y
ergibt den letzten Eintrag iny
.([:{:@(#~*)10&#.inv@*)
.u/ y
ist die Reduktion desy
dyadischen Verbsu
zwischen Elementen vony
. Zum Beispiel+/1 2 3 4
ist wie1 + 2 + 3 + 4
und ergibt10
.([:{:@(#~*)10&#.inv@*)/ y
ergibt die Phrase die letzte Ziffer des Produkts der Artikel vony
.ARGV
ist ein umrahmter Vektor der Befehlszeilenargumente.".>{:ARGV
ist das letzte Argument, das als Zahl interpretiert wird.i. y
berechnet natürliche Zahlen von0
bisy - 1
.1+i. y
ergeben sich natürliche Zahlen von1
bisy
. Ich hätte hier auch>:
Inkrement verwenden können , ist aber1+
bei gleichen Zeichenkosten klarer.1+i.".>{:ARGV
(der Vektor1
der Zahl im letzten Befehlszeilenargument) auf das Verb an([:{:@(#~*)10&#.inv@*)/
und gibt das Ergebnis mit ausecho
.quelle
Pyt , 5 Bytes
Erläuterung:
Probieren Sie es online!
quelle
R ,
63555146 ByteBerechnet Fakultät, extrahiert die letzte Ziffer ungleich Null. Vielen Dank an Giuseppe für die Bereitstellung der Grundstruktur.
Probieren Sie es online!
Alternativ meine alte 51-Byte-Antwort:
Berechnet Fakultät, konvertiert in Zeichen, entfernt alle
0
s und nimmt dann das letzte Zeichen. 2 Bytes dank Giuseppe gespeichert.Probieren Sie es online!
quelle
gamma(x+1)
ist kürzer alsfactorial(x)
(y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]
bei 54 Bytes.nchar(x)
mit1e5
einer 46-Byte - Lösung! Es läuft gut.> <> 25 Bytes
Probieren Sie es online!
Griffe 0! auch richtig. Wert, der über das
-v
Flag übergeben wurde.quelle
1000
erzeugt keine Ausgabe auf TIO - was ist los?Perl 6 ,
2635 BytesVersuch es
Als volles Programm:
Versuch es
Erweitert:
quelle
C (gcc) , 72 Bytes (Funktion)
Probieren Sie es online!
C (gcc) ,
10199 Bytes (gesamtes Programm)Probieren Sie es online!
Diese Frage ist gerade mal 8 Jahre alt, also ist "vernünftige Maschine" nicht die gleiche wie damals, aber ich bekomme Zeiten von ~ 0,01 Sekunden auf meinem Computer, wenn ich alle Testfälle zusammen mache, es sei denn, die Geschwindigkeit der Computer hat zugenommen um den Faktor 1000 in diesem letzten Jahrzehnt sollte es in Ordnung sein.
quelle
Add ++ , 11 Bytes
Probieren Sie es online!
quelle
Attache , 26 Bytes
Probieren Sie es online!
Erläuterung
Dies ist eine Komposition aus 4 Funktionen:
`!
- Dies ist eine funktionale Version des FakultätsoperatorsDigits
- Dies erhält die Ziffern der Fakultät\&:(All@V)
- Dies ist eine Auswahlfunktion. Es funktioniert durch linkes Bonden (&:
) der FunktionAll@V
nach\
, die ausgewählt ist. DiesAll@V
ist eine kurze Möglichkeit, um zu testen, ob eine Zahl ungleich 0 ist. Die Eingabe wird in einen Vektor umgewandelt0 -> [0]
wandelt um und fragt dann ab, ob alle diese Mitglieder wahr sind (dh nicht 0). Dies ergibt die Ziffern der Zahl ohne 0s.Last
- Dies erhält einfach das letzte Mitglied dieses Arrays.quelle
APL (Dyalog Unicode) ,
1815 BytesProbieren Sie es online!
Tacit-Präfix-Funktion. Gibt die richtige Ziffer für einen einzelnen Testfall oder eine Ziffernfolge für mehrere Testfälle zurück.
Vielen Dank an @ Adám und @ErikTheOutgolfer für jeweils 3 Bytes.
Wie?
quelle
APL NARS, 28 Byte, 14 Zeichen
Ich weiß nicht warum, aber dies besteht den Test:
quelle
AWK ,
4757 BytesProbieren Sie es online!
Die ursprüngliche Lösung handhabte "große" Eingabewerte nicht sehr gut. Könnte hinzufügen
-M
, um es zum Arbeiten zu zwingen, aber das erfordert auch viel mehr Verarbeitungszeit.quelle
inf
nicht%
sehr gut. :(Japt , 6 Bytes
Kam mit ein paar verschiedenen 6-Byte, aber ich mochte dieses am besten. Ich bin davon überzeugt, dass es einen Weg geben muss, dies in 5 zu tun.
Versuch es
Erläuterung
Ê
berechnet die Fakultät der Eingabe,s
konvertiert sie in einen String und zurück in eine Ganzzahl, nachdemw
sie umgekehrt wurde,ì
konvertiert das Ergebnis in ein Array von Ziffern undv
gibt das erste Element zurück.Alternativen
quelle
Perl 5 , 36 + 10 (
-p -Mbigint
) = 46 BytesProbieren Sie es online!
quelle
f
(sollte 4 sein ) und 100 ⇒7
(sollte 4 sein )