El reto:
Escriba un programa o una función que ingrese un número positivo y devuelva su factorial .
Nota: Esta es una pregunta de arrastre de código . No tome en serio la pregunta y / o las respuestas. Más información aquí . Cada pregunta de código trolling es también una pregunta de concurso de popularidad , por lo que gana la respuesta más votada.
popularity-contest
code-trolling
alephalpha
fuente
fuente
Respuestas:
Este es un problema informático numérico muy simple que podemos resolver con la aproximación de Stirling :
Como puede ver, esa fórmula presenta una raíz cuadrada, que también necesitaremos una forma de aproximar. Elegiremos el llamado "método babilónico" para eso porque podría decirse que es el más simple:
Tenga en cuenta que calcular la raíz cuadrada de esta manera es un buen ejemplo de recursividad.
Poner todo junto en un programa Python nos da la siguiente solución a su problema:
Con una simple modificación, el programa anterior puede generar una tabla ordenada de factoriales:
Este método debe ser lo suficientemente preciso para la mayoría de las aplicaciones.
fuente
C#
Lo siento, pero odio la función recursiva.
fuente
Java
fuente
Pitón
Por supuesto, la mejor manera de resolver cualquier problema es usar expresiones regulares:
fuente
Haskell
El código corto es un código eficiente, así que intente esto.
Por qué es curricán:
Me reiría de cualquier programador que escribiera esto ... La ineficiencia es hermosa. También es probablemente incomprensible para cualquier programador de Haskell que realmente no pueda escribir una función factorial.
Editar: publiqué esto hace un tiempo, pero pensé en aclarar para las personas futuras y las personas que no pueden leer Haskell.
El código aquí toma la lista de los números 1 a n, crea la lista de todas las permutaciones de esa lista y devuelve la longitud de esa lista. En mi máquina, ¡tardo unos 20 minutos en 13! ¡Y luego debería tomar cuatro horas para 14! y luego dos días y medio por 15 !. Excepto que en algún momento allí te quedas sin memoria.
Edición 2: En realidad, probablemente no se quedará sin memoria debido a que este es Haskell (vea el comentario a continuación). Es posible que pueda forzarlo a evaluar la lista y mantenerla en la memoria de alguna manera, pero no sé lo suficiente sobre cómo optimizar (y no optimizar) a Haskell para saber exactamente cómo hacerlo.
fuente
[1..n]
. - Una permutación particular de[1..n]
, consed a un thunk para el resto de las permutaciones (polinomion
). - Un acumulador para lalength
función.C#
Dado que este es un problema matemático, tiene sentido usar una aplicación específicamente diseñada para resolver problemas matemáticos para hacer este cálculo ...
Paso 1:
Instalar MATLAB. Creo que una prueba funcionará, pero este problema súper complicado probablemente sea lo suficientemente importante como para merecer comprar la versión completa de la aplicación.
Paso 2:
Incluya el componente MATLAB COM en su aplicación.
Paso 3:
fuente
C#
Los factoriales son una operación matemática de nivel superior que puede ser difícil de digerir todo de una vez. La mejor solución en problemas de programación como este es dividir una tarea grande en tareas más pequeñas.
Ahora n! se define como 1 * 2 * ... * n, entonces, en esencia, la multiplicación repetida, y la multiplicación no es más que la suma repetida. Entonces, con eso en mente, lo siguiente resuelve este problema:
fuente
Trolls:
z = n - 1 + 1
) es en realidad autodocumentado si sabe lo que está sucediendo.p[]
usando un cálculo recursivo de los coeficientes de la serie!(Es la aproximación de Lanczos de la función gamma )
fuente
- 1 + 1
aquí? Mi compilador lo optimiza (no es un número de coma flotante donde optimizar un código como este podría ser peligroso), por lo que parece innecesario.double z = n - 1
es parte de la aproximación de la función gamma. El+ 1
es de la relación quegamma(n + 1) = n!
para el entero n.Todos sabemos desde la universidad que la forma más eficiente de calcular una multiplicación es mediante el uso de logaritmos. Después de todo, ¿por qué otra razón la gente usaría tablas de logaritmos durante cientos de años?
Entonces, a partir de la identidad
a*b=e^(log(a)+log(b))
, formamos el siguiente código de Python:Crea una lista de números de
1
ax
, (+1
es necesario porque Python apesta) calcula el logaritmo de cada uno, suma los números, eleva la e al poder de la suma y finalmente redondea el valor al entero más cercano (porque Python apesta) . Python tiene una función incorporada para calcular factoriales, pero solo funciona para enteros, por lo que no puede producir números grandes (porque Python es una mierda). Es por eso que se necesita la función anterior.Por cierto, un consejo general para los estudiantes es que si algo no funciona como se esperaba, probablemente sea porque el idioma apesta.
fuente
Desafortunadamente, Javascript carece de una forma integrada de calcular el factorial. Pero, sin embargo, puede usar su significado en combinatoria para determinar el valor:
El factorial de un número n es el número de permutaciones de una lista de ese tamaño.
Por lo tanto, podemos generar cada lista de números de n dígitos, verificar si es una permutación y, de ser así, incrementar un contador:
Trolls:
O(n)
, noO(n!)
, peroO(n^n)
. Esto solo habría bastado para calificar aquí.number.toString(base)
, pero eso no funciona para bases superiores a 36. Sí, ¡sé 36! es mucho , pero aun así ...Math.pow
? ¿No? Oh bien.++
fuera de for-loops lo hace aún más misterioso. También,==
es malo.$i
.new Array
,document.write
(con amigos) yalert
(en lugar de un aviso o una etiqueta de entrada) forman una trifecta completa de pecados de elección de funciones. ¿Por qué la entrada se agrega dinámicamente después de todo?=
hacen aún más difíciles de leer.fuente
Ruby y WolframAlpha
Esta solución utiliza la API REST WolframAlpha para calcular el factorial, con RestClient para obtener la solución y Nokogiri para analizarla. No reinventa ninguna rueda y utiliza tecnologías bien probadas y populares para obtener el resultado de la manera más moderna posible.
fuente
Javascript
Javascript es un lenguaje de programación funcional, esto significa que tienes que usar funciones para todo porque es más rápido.
fuente
r = -~(function(){})
seguramente resolverá eso.Usando Bogo-Sort en Java
Esto realmente funciona, muy lentamente, y no es preciso para números más altos.
fuente
PERL
Factorial puede ser un problema difícil. Una técnica de mapa / reducción similar, al igual que Google usa, puede dividir las matemáticas al bifurcar varios procesos y recopilar los resultados. Esto hará un buen uso de todos esos núcleos o cpus en su sistema en una fría noche de invierno.
Guarde como f.perl y chmod 755 para asegurarse de que pueda ejecutarlo. Usted tiene instalado el Lister de basura patológicamente ecléctico, ¿no?
Trolls:
fuente
ARGV[0]
es en realidad el primer argumento y no el guión!$ARGV[0]
porque la mayoría de los idiomas que conozco un poco lo tienen allíPitón
Solo un algoritmo O (n! * N ^ 2) para encontrar el factorial. Caso base manejado. Sin desbordamientos.
fuente
Bueno, hay una solución fácil en Golfscript. Puede usar un intérprete Golfscript y ejecutar este código:
Fácil eh :) ¡Buena suerte!
fuente
!
Mathematica
No parece funcionar para números mayores que 11, y factorial [11] congeló mi computadora.
fuente
Rubí
La frase más lenta que puedo imaginar. Calcula 2 minutos en un procesador i7
6!
.fuente
El enfoque correcto para estos problemas matemáticos difíciles es un DSL. Así que modelaré esto en términos de un lenguaje simple
Para escribir bien nuestro DSL, es útil verlo como una mónada gratuita generada por el functor algebraico
Podríamos escribir esto en Haskell como
Dejaré al lector derivar la implementación trivial de
Ahora podemos describir una operación para modelar un factorial en este DSL
Ahora que hemos modelado esto, solo necesitamos proporcionar una función de interpretación real para nuestra mónada libre.
Y dejaré el resto de la denotación al lector.
Para mejorar la legibilidad, a veces es útil presentar un AST concreto del formulario
y luego a la derecha una reflexión trivial
y luego es sencillo evaluar recursivamente el AST.
fuente
Pitón
A continuación se muestra una versión de Python de la solución, que no se limita al límite de 32 bits (o 64 bits en un sistema muy reciente) para números enteros en Python. Para evitar esta limitación, usaremos una cadena como entrada y salida para lafactorial
rutina y dividiremos internamente la cadena en sus dígitos para poder realizar la multiplicación.Así que aquí está el código: la
getDigits
función divide una cadena que representa un número en sus dígitos, por lo que "1234" se convierte[ 4, 3, 2, 1 ]
(el orden inverso simplemente hace que las funcionesincrease
y seanmultiply
más simples). Laincrease
función toma dicha lista y la aumenta en uno. Como su nombre lo indica, lamultiply
función se multiplica, por ejemplo,multiply([2, 1], [3])
devuelve[ 6, 3 ]
porque 12 por 3 es 36. Esto funciona de la misma manera que multiplicaría algo con lápiz y papel.Finalmente, la
factorial
función usa estas funciones auxiliares para calcular el factorial real, por ejemplo,factorial("9")
da"362880"
como salida.Notas
En python, un número entero no tiene límite, por lo que si desea hacer esto manualmente, puede hacerlo
También existe la
math.factorial(n)
función muy conveniente .Obviamente, esta solución es mucho más compleja de lo que debe ser, pero funciona y, de hecho, ilustra cómo puede calcular el factorial en caso de que esté limitado por 32 o 64 bits. Entonces, aunque nadie creerá que esta es la solución que se le ocurrió para este simple problema (al menos en Python), en realidad puede aprender algo.
fuente
Pitón
La solución más razonable es claramente verificar todos los números hasta encontrar el factorial del número dado.
fuente
La solución recursiva más elegante en C
Todos saben que las soluciones más elegantes para los factoriales son recursivas.
Factorial:
Pero la multiplicación también puede definirse recursivamente como adiciones sucesivas.
Multiplicación:
Y también puede sumarse como incrementos sucesivos.
Adición:
En
C
, podemos usar++x
y--x
manejar las primitivas(x + 1)
y(x - 1)
respectivamente, por lo que tenemos todo definido.Probémoslo:
Perfecto, aunque 8! tomó mucho tiempo por alguna razón. Bueno, las soluciones más elegantes no siempre son las más rápidas. Continuemos:
Hmm, te avisaré cuando vuelva ...
fuente
Pitón
Como indicó la respuesta de @ Matt_Sieker, los factoriales se pueden dividir en una suma: por qué, dividir las tareas es la esencia de la programación. ¡Pero podemos dividir eso en 1!
Creo que este código garantiza un error SO, porque
La recursión lo calienta
Cada capa genera llamadas para multiplicar
que genera llamadas a addnumbers
que genera llamadas a addby1!
Demasiadas funciones, ¿verdad?
fuente
Simplemente vaya a Google y escriba su factorial:
http://lmgtfy.com/?q=5!
fuente
TI-Basic 84
Realmente funciona :)
fuente
Javascript
Obviamente, el trabajo de un programador es hacer el menor trabajo posible y utilizar tantas bibliotecas como sea posible. Por lo tanto, queremos importar jQuery y math.js . Ahora, la tarea es simple como esta:
fuente
Pitón
Con solo una ligera modificación de la implementación factorial recursiva estándar, se vuelve intolerablemente lenta para n> 10.
fuente
Golpetazo
fuente
Tratemos de hacerlo por el Método Monte Carlo . ¡Todos sabemos que la probabilidad de que dos n- permutaciones al azar sean iguales es exactamente 1 / n! . Por lo tanto, solo podemos verificar cuántas pruebas se necesitan (llamemos a este número b ) hasta obtener c hits. Entonces, n! ~ b / c .
Sage, también debería funcionar en Python
fuente
golpetazo
Los factoriales se determinan fácilmente con las conocidas herramientas de línea de comandos de bash.
Como @Aaron Davies mencionó en los comentarios, esto parece mucho más ordenado y todos queremos un programa agradable y ordenado, ¿no?
fuente
paste
comando altamente subestimado :seq 1 $n | paste -sd\* | bc
paste
parece a una palabra inglesa normal y es fácil de recordar. ¿En verdad queremos eso? ; o)