Dado un entero 1 ≤ N ≤ 1,000,000 como entrada, ¡emite el último dígito distinto de cero de N! , donde ! es el factorial (el producto de todos los números del 1 al N , inclusive). Esta es la secuencia OEIS A008904 .
Su programa necesita terminar dentro de 10 segundos en una máquina razonable para cualquier entrada válida.
Casos de prueba
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
Este es un código de golf, por lo que gana el código más corto en bytes.
Respuestas:
Ruby - 63 caracteres
Fuente: http://oeis.org/A008904
Maneja hasta mil dígitos por segundo.
Prueba
fuente
Mathematica,
4536 bytesMuy legible para una respuesta ganadora. :) (Por otra parte, todavía no hay presentación de GolfScript & Co.).
Esto maneja la entrada 1,000,000 en aproximadamente 5 segundos en mi máquina.
fuente
Python - 75
fuente
PARI / GP - 27 bytes
Esto cambia la velocidad por el tamaño: el caso de prueba lleva mucho tiempo (~ 6 segundos).
Esta versión es mucho más rápida (~ 15 microsegundos) pero toma 81 bytes:
Puede usar este código (no golfizado) para probar:
fuente
Windows PowerShell, 53
565960637390Notas:
Historia:
$input
a una cadena es suficiente; El repartoint
se aplica implícitamente.fuente
Perl, 53
5861caracteresTodo el espacio en blanco se puede eliminar, pero lo dejé para "legibilidad". Nota: no usar alguna fórmula explícita tonta de Sloane.
Calcula f (10 ^ 6) en 8.7 segundos en mi máquina.
Actualización : OP quería que fuera un programa completo:
Eso lo convierte en 55 caracteres.
fuente
CJam - 28
Puede probarlo en http://cjam.aditsu.net/ para valores de hasta 10000 aproximadamente; para números más grandes debe usar el intérprete de java . 1000000 se ejecuta en aproximadamente 3 segundos en mi computadora portátil.
Explicación:
Desafortunadamente, la solución directa es demasiado lenta, por lo que solo mantengo los últimos 7 dígitos (antes de los ceros finales) después de cada multiplicación.
Nota: este lenguaje es mucho más nuevo que la pregunta.
fuente
Mathematica, 34 bytes
fuente
05AB1E , 4 bytes
Pruébalo en línea!
Explicación
fuente
Jalea , 4 bytes
Pruébalo en línea!
Explicación
Utiliza el hecho de que cuando
Ṛ
(se invierte una lista; no se vectoriza) se aplica a un entero,D
primero toma automáticamente (dígitos).Con entrada 8:
No creo que haya un "primer elemento de verdad" de un byte (que
ȯ/
actúa como), pero si lo hay, se puede acortar a tres bytes en total.fuente
Java (OpenJDK 8) , 62 bytes
Pruébalo en línea!
Similar a @Kevin Cruijssen pero ahorra 5 bytes combinando los bucles.
fuente
||
con|
, y un byte adicional reemplazando==0
con<1
. ¡Disfruta tu estancia!C,
150140135 bytesEsta es la versión para sistemas ASCII; reemplace la cadena
33436
con11214
un sistema EBCDIC, o con\1\1\2\1\4
un programa portátil.Las soluciones C están un poco obstaculizadas por el requisito de proporcionar un programa completo; sin embargo, esto responde la pregunta completamente.
Pruébelo en línea (requiere Javascript):
Explicación
Se basa en el algoritmo descrito en el dígito menos nulo menos significativo de n! , volteamos para que recurramos para encontrar la potencia más alta de cinco, y hagamos el cálculo al salir. Las tablas de constantes eran demasiado grandes, así que las reduje al encontrar una relación entre el residuo anterior
r
, el dígito actuald
y la profundidad de recursiónk
:Para
r>0
, esto se resuelve a veces constantesr
veces2^dk
(mod 5); las constantes estána[]
abajo (en el código de golf). También observamos que(2^4)%5
es 1, por lo que podemos reducir el exponente para evitar desbordar el rango deint
.Pruebas:
El rendimiento también es respetable. Aquí hay una entrada máxima para un sistema con 32 bits
int
:También obtuve los mismos tiempos con un máximo de 64 bits
int
.fuente
2147483647!
tiene más de 19 mil millones de dígitos y(2^63-1)!
más de 170,000,000,000,000,000,000 de dígitos, por lo que esta es una gran victoria sobre el cálculo de los factores.1000000!
como se especifica en la pregunta, es factible calcularlo en el hardware actual; eso es solo 5½ millones de dígitos. :-)PHP - 105
Se ejecuta en menos de 10 segundos con el caso de prueba dado.
fuente
Python3
239 caracteresPuede hacer 10000 en ~ 3.2 segundos (Ideone me corta a los 8 segundos, estoy seguro de que tomará más de 10 segundos :()
Python2.6
299 caracteres (un poco más rápido)fuente
Haskell, 78 personajes
(¡Probablemente deba compilarse para calcular 1,000,000! En 10 segundos).
fuente
foldl1
conproduct
(cf codegolf.stackexchange.com/questions/607/find-the-factorial/… ). Pero, ¿has probado con 1000000? ?J -
4240 caracteresTodo un programa. Guarde este programa en un archivo y ejecútelo
jconsole script.ijs 1234
. Tenga en cuenta que este programa no sale del intérprete después de imprimir un resultado. Escriba^D
oexit]0
para salir del intérprete.Aquí hay una explicación:
x #. y
interpreta el vector enteroy
como unx
número base ; por ejemplo,10 #. 1 2 3 4
rendimientos1234
.u inv
produce el inverso de un verbou
. En particular,x #. inv y
representay
como unx
número base ; por ejemplo,10 #. 1234
rendimientos1 2 3 4
. Observe queinv
se define como^:_1
, es decir,u
aplicado -1 veces.x * y
es el producto dex
yy
, por lo tanto,x 10&#.inv@* y
produce una representación en base 10 del producto dex
yy
.x # y
copia el n -ésimo dey
la frecuencia que el n -ésimo elemento de lax
; cuandox
es un vector de booleanos,x
selecciona qué elementosy
tomar. Por ejemplo,1 0 1 0 # 1 2 3 4
rendimientos1 3
.* y
produce el signum dey
.x u~ y
es el reflejo deu
, es decir, lo mismo quey u x
.y #~ * y
produce un vector de todos los elementos dey
que son positivos. En notación tácita, esto se puede escribir con un gancho como(#~ *)
.{: y
produce el último elemento eny
.([:{:@(#~*)10&#.inv@*)
.u/ y
es la reducción dey
, es decir, el verbo diádicou
insertado entre elementos dey
. Por ejemplo,+/1 2 3 4
es como1 + 2 + 3 + 4
y rinde10
.([:{:@(#~*)10&#.inv@*)/ y
produce el último dígito del producto de los elementos dey
.ARGV
es un vector en caja de los argumentos de la línea de comando.".>{:ARGV
es el último argumento sin caja e interpretado como un número.i. y
calcula números naturales de0
ay - 1
.1+i. y
produce números naturales de1
ay
. También podría haber usado el>:
incremento aquí, pero1+
es más claro al mismo costo de los personajes.1+i.".>{:ARGV
(el vector del1
número en el último argumento de la línea de comando) al verbo([:{:@(#~*)10&#.inv@*)/
e imprime el resultado conecho
.fuente
Pyt , 5 bytes
Explicación:
Pruébalo en línea!
fuente
R ,
63555146 bytesCalcula factorial, extrae el último dígito distinto de cero. Gracias a Giuseppe por proporcionar la estructura básica.
Pruébalo en línea!
Alternativamente, mi vieja respuesta de 51 bytes:
Calcula factorial, convierte a carácter, elimina todos los
0
s, y luego toma el carácter final. Guardado 2 bytes gracias a Giuseppe.Pruébalo en línea!
fuente
gamma(x+1)
es más corto quefactorial(x)
(y=(x<-gamma(scan()+1))%/%10^(0:nchar(x))%%10)[!!y][1]
en 54 bytes.nchar(x)
con1e5
una solución de 46 bytes! Bien hecho.> <> , 25 bytes
Pruébalo en línea!
Maneja 0! correctamente también Valor pasado a través de la
-v
bandera.fuente
1000
no produce ningún resultado en TIO, ¿qué pasa?Perl 6 ,
2635 bytesIntentalo
Como un programa completo:
Intentalo
Expandido:
fuente
C (gcc) , 72 bytes (función)
Pruébalo en línea!
C (gcc) ,
10199 bytes (programa completo)Pruébalo en línea!
Esta pregunta tiene apenas 8 años, por lo que "máquina razonable" no es lo mismo que en aquel entonces, pero obtengo tiempos de ~ .01 segundos en mi computadora cuando hago todos los casos de prueba juntos, así que a menos que las computadoras hayan aumentado su velocidad por un factor de 1000 en esta última década, debería estar bien.
fuente
Añadir ++ , 11 bytes
Pruébalo en línea!
fuente
Adjunto , 26 bytes
Pruébalo en línea!
Explicación
Esta es una composición de 4 funciones:
`!
- esta es una versión funcional del operador factorialDigits
- esto obtiene los dígitos del factorial\&:(All@V)
- Esta es una función de selección. Funciona mediante la unión a la izquierda (&:
) la funciónAll@V
a\
que se seleccione. A su vez,All@V
es una forma corta de probar si un número no es 0. Funciona al enviar su entrada a un vector0 -> [0]
luego preguntar si todos esos miembros son verdaderos (es decir, no 0). Esto da los dígitos del número sin ceros.Last
- esto simplemente obtiene el último miembro de esta matriz.fuente
APL (Dyalog Unicode) ,
1815 bytesPruébalo en línea!
Función de prefijo tácito. Devuelve el dígito correcto para un solo caso de prueba, o una cadena de dígitos para múltiples casos de prueba.
Gracias a @ Adám y @ErikTheOutgolfer por 3 bytes cada uno.
¿Cómo?
fuente
NARS APL, 28 bytes, 14 caracteres
No sé por qué, pero esto pasa la prueba:
fuente
AWK ,
4757 bytesPruébalo en línea!
La solución original no manejó muy bien los valores de entrada "grandes". Podría agregarse
-M
para forzarlo a funcionar, pero eso también requiere mucho más tiempo de procesamiento.fuente
inf
no%
muy bien. :(Japt , 6 bytes
Se me ocurrieron algunos 6 bytes diferentes, pero este me gustó más. Sin embargo, estoy convencido de que debe haber una manera de hacerlo en 5.
Intentalo
Explicación
Ê
calcula el factorial de la entrada, los
convierte en una cadena y vuelve a un número entero después dew
haberlo invertido,ì
convierte el resultado en una matriz de dígitos yv
devuelve el primer elemento.Alternativas
fuente
Perl 5 , 36 + 10 (
-p -Mbigint
) = 46 bytesPruébalo en línea!
fuente
f
(debería ser 4 ) y 100 ⇒7
(debería ser 4 )