¿Cómo encuentro el factorial de un número positivo?

18

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 . No tome en serio la pregunta y / o las respuestas. Más información aquí . Cada pregunta de es también una pregunta de , por lo que gana la respuesta más votada.

alephalpha
fuente
66
Ver también el programador La evolución de Haskell .
Petr Pudlák
44
-1, lo siento, porque estamos recibiendo una gran inundación de estas preguntas Código de arrastre y esto no añade nada nuevo para ellos
Pomo
El trolling de códigos está en proceso de eliminación, según la postura oficial. Esta pregunta tiene una buena cantidad de votos con muchas respuestas, muchas de las cuales son extremadamente altamente votadas. Recibió un poco más del 50% de votos de "eliminación" en la encuesta , pero es único en el sentido de que recibió tantas respuestas y votos, así que lo estoy bloqueando por su importancia histórica.
Pomo de la puerta

Respuestas:

46

Este es un problema informático numérico muy simple que podemos resolver con la aproximación de Stirling :

Fórmula de 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:

Babylonian method

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:

def sqrt(x, n): # not the same n as below
    return .5 * (sqrt(x, n - 1) + x / sqrt(x, n - 1)) if n > 0 else x

n = float(raw_input())
print (n / 2.718) ** n * sqrt(2 * 3.141 * n, 10)

Con una simple modificación, el programa anterior puede generar una tabla ordenada de factoriales:

1! =    0.92215
2! =    1.91922
3! =    5.83747
4! =   23.51371
5! =  118.06923
6! =  710.45304
7! = 4983.54173
8! = 39931.74015
9! = 359838.58817

Este método debe ser lo suficientemente preciso para la mayoría de las aplicaciones.

nwk
fuente
16
+1 La simplicidad y precisión de este método lo convierte en un claro ganador
Joe the Person el
44

C#

Lo siento, pero odio la función recursiva.

public string Factorial(uint n) {
    return n + "!";
}
tia
fuente
1
Técnicamente, ¡has satisfecho el resumen! ;) +1 por abuso breve
WallyWest
36

Java

public int factorial ( int n ) {
switch(n){
case 0: return 1;
case 1: return 1;
case 2: return 2;
case 3: return 6;
case 4: return 24;
case 5: return 120;
case 6: return 720;
case 7: return 5040;
case 8: return 40320;
case 9: return 362880;
case 10: return 3628800;
case 11: return 39916800;
case 12: return 479001600;
default : throw new IllegalArgumentException();
}
}
emory
fuente
16
Lo probé, muy eficiente. Se enviará con el próximo lanzamiento. :)
Johannes
Además del "síndrom de números mágicos", esta podría ser una buena implementación siempre que n <13, mucho menos pilas. Escríbelo "caso 4: devuelve 4 * 3 * 2;" y tendrías una clase decente, mucho más rápida que la anterior recursiva.
Fabinout
66
@Fabinout, la implementación es correcta incluso para n> = 13. 13!> Integer.MAX_VALUE.
emory
21

Pitón

Por supuesto, la mejor manera de resolver cualquier problema es usar expresiones regulares:

import re

# adapted from http://stackoverflow.com/q/15175142/1333025
def multiple_replace(dict, text):
  # Create a regular expression  from the dictionary keys
  regex = re.compile("(%s)" % "|".join(map(re.escape, dict.keys())))
  # Repeat while any replacements are made.
  count = -1
  while count != 0:
    # For each match, look-up corresponding value in dictionary.
    (text, count) = regex.subn(lambda mo: dict[mo.string[mo.start():mo.end()]], text)
  return text

fdict = {
    'A': '@',
    'B': 'AA',
    'C': 'BBB',
    'D': 'CCCC',
    'E': 'DDDDD',
    'F': 'EEEEEE',
    'G': 'FFFFFFF',
    'H': 'GGGGGGGG',
    'I': 'HHHHHHHHH',
    'J': 'IIIIIIIIII',
    'K': 'JJJJJJJJJJJ',
    'L': 'KKKKKKKKKKKK',
    'M': 'LLLLLLLLLLLLL',
    'N': 'MMMMMMMMMMMMMM',
    'O': 'NNNNNNNNNNNNNNN',
    'P': 'OOOOOOOOOOOOOOOO',
    'Q': 'PPPPPPPPPPPPPPPPP',
    'R': 'QQQQQQQQQQQQQQQQQQ',
    'S': 'RRRRRRRRRRRRRRRRRRR',
    'T': 'SSSSSSSSSSSSSSSSSSSS',
    'U': 'TTTTTTTTTTTTTTTTTTTTT',
    'V': 'UUUUUUUUUUUUUUUUUUUUUU',
    'W': 'VVVVVVVVVVVVVVVVVVVVVVV',
    'X': 'WWWWWWWWWWWWWWWWWWWWWWWW',
    'Y': 'XXXXXXXXXXXXXXXXXXXXXXXXX',
    'Z': 'YYYYYYYYYYYYYYYYYYYYYYYYYY'}

def fact(n):
    return len(multiple_replace(fdict, chr(64 + n)))

if __name__ == "__main__":
    print fact(7)
Petr Pudlák
fuente
1
Por supuesto que sí :)
Pierre Arlaud
15

Haskell

El código corto es un código eficiente, así que intente esto.

fac = length . permutations . flip take [1..]

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.

jgon
fuente
Horrible y sin embargo tan elegante, todo al mismo tiempo.
PLL
1
¿Estás seguro sobre el problema de memoria? En cualquier punto, debe mantener en la memoria: - la lista [1..n]. - Una permutación particular de [1..n], consed a un thunk para el resto de las permutaciones (polinomio n). - Un acumulador para la lengthfunción.
John Dvorak
Punto justo, probablemente no en realidad. Realmente no lo pensé demasiado. Agregaré un comentario en la parte inferior.
jgon
10

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:

public string Factorial(uint n) {
    MLApp.MLApp matlab = new MLApp.MLApp();
    return matlab.Execute(String.Format("factorial({0})", n);
}
Moshe Katz
fuente
Matlab para estudiantes comienza en $ 100. Las versiones profesionales o las licencias de sitio pueden llegar a miles.
Moshe Katz
44
Moshe Katz: justificado porque los factoriales.
Mike H.
9

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:

long Factorial(int n)
{
    if(n==0)
    {
        return 1;
    }

    Stack<long> s = new Stack<long>();
    for(var i=1;i<=n;i++)
    {
        s.Push(i);
    }
    var items = new List<long>();
    var n2 = s.Pop();
    while(s.Count >0)
    {
        var n3 = s.Pop();
        items.AddRange(FactorialPart(n2,n3));
        n2 = items.Sum();
    }
    return items.Sum()/(n-1);
}

IEnumerable<long> FactorialPart(long n1, long n2)
{
    for(var i=0;i<n2;i++){
        yield return n1;
    }
}
Matt Sieker
fuente
Tiene un cuello de botella que envía todo esto a través de una CPU o núcleo, lo que creo que podría haber resuelto en mi respuesta :-)
Paul
9
#include <math.h>

int factorial(int n)
{
    const double g = 7;
    static const double p[] = { 0.99999999999980993, 676.5203681218851,
                                -1259.1392167224028, 771.32342877765313,
                                -176.61502916214059, 12.507343278686905,
                                -0.13857109526572012, 9.9843695780195716e-6,
                                1.5056327351493116e-7 };
    double z = n - 1 + 1;
    double x = p[0];
    int i;
    for ( i = 1; i < sizeof(p)/sizeof(p[0]); ++i )
        x += p[i] / (z + i);
    return sqrt(2 * M_PI) * pow(z + g + 0.5, z + 0.5)  * exp(-z -g -0.5) * x + 0.5;
}

Trolls:

  • Una manera 100% correcta de calcular factorial que pierde completamente el punto de hacerlo de forma iterativa o recursiva.
  • No tienes idea de por qué funciona y no puedes generalizarlo para hacer otra cosa.
  • Más costoso que simplemente calcularlo con matemáticas enteras.
  • El código "subóptimo" más obvio ( z = n - 1 + 1) es en realidad autodocumentado si sabe lo que está sucediendo.
  • ¡Para un curricán adicional, debo calcular p[]usando un cálculo recursivo de los coeficientes de la serie!

(Es la aproximación de Lanczos de la función gamma )

Ben Jackson
fuente
¿Hay algún punto - 1 + 1aquí? 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.
Konrad Borowski
44
@xfix: double z = n - 1es parte de la aproximación de la función gamma. El + 1es de la relación que gamma(n + 1) = n!para el entero n.
Ben Jackson
9

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:

from math import log,exp

def fac_you(x):
    return round(exp(sum(map(log,range(1,x+1)))))

for i in range(1,99):
    print i,":",fac_you(i)

Crea una lista de números de 1a x, ( +1es 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.

nitro2k01
fuente
Ojalá pudiera dar algunos votos adicionales para la descripción, pero Python apesta
Mark K Cowan
1
Me reí de "fac you"
Número9
8

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:

window.factorial = function($nb_number) {
  $nb_trials = 1
  for($i = 0; $i < $nb_number; $i++) $nb_trials *= $nb_number
  $nb_successes = 0
  __trying__:
  for($nb_trial = 0; $nb_trial < $nb_trials; $nb_trial++){
    $a_trial_split = new Array
    $nb_tmp = $nb_trial
    for ($nb_digit = 0; $nb_digit < $nb_number; $nb_digit++){
      $a_trial_split[$nb_digit] = $nb_tmp - $nb_number * Math.floor($nb_tmp / $nb_number)
      $nb_tmp = Math.floor($nb_tmp / $nb_number)
    }
    for($i = 0; $i < $nb_number; $i++)
      for($j = 0; $j < $nb_number; $j++)
        if($i != $j)
          if($a_trial_split[$i] == $a_trial_split[$j])
            continue __trying__
    $nb_successes += 1
  }
  return $nb_successes
}

alert("input a number")
document.open()
document.write("<input type = text onblur = alert(factorial(parseInt(this.value))))>")
document.close()


Trolls:

  • Tipos de notación húngara, snake_case y sigilos . ¿Qué tan malvado es eso?
  • Inventé mi propia convención para las etiquetas de salto, incompatible con el uso actual de esta convención.
  • Cada variable posible es accidentalmente global.
  • La solución no es O(n), no O(n!), peroO(n^n) . Esto solo habría bastado para calificar aquí.
  • Incrementar un número y luego convertirlo como base-n es una mala manera de generar una lista de secuencias. Incluso si quisiéramos duplicados. Romper misteriosamente para n> 13 no es la única razón.
  • Por supuesto que podríamos haber usado number.toString(base), pero eso no funciona para bases superiores a 36. Sí, ¡sé 36! es mucho , pero aun así ...
  • ¿Mencioné que Javascript tenía el operador de módulo? OMath.pow ? ¿No? Oh bien.
  • Negarse a usar ++fuera de for-loops lo hace aún más misterioso. También,== es malo.
  • Construcciones de bucle sin tirantes profundamente anidadas. Además, condicionales anidados en lugar de AND. Además, la condición externa podría haberse evitado terminando el ciclo interno en$i .
  • Las funciones 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?
  • Controladores de eventos en línea. Ah, y las tuberías profundas son un infierno para depurar.
  • Los atributos sin comillas son divertidos, y los espacios alrededor = hacen aún más difíciles de leer.
  • ¿Ya mencioné que odio los punto y coma?
John Dvorak
fuente
8

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.

require 'rest-client'
require 'nokogiri'

n = gets.chomp.to_i
response = Nokogiri::XML(RestClient.get("http://api.wolframalpha.com/v2/query?input=#{n}!&format=moutput&appid=YOUR_APP_KEY"))
puts response.xpath("//*/moutput/text()").text
migimunz
fuente
7

Javascript

Javascript es un lenguaje de programación funcional, esto significa que tienes que usar funciones para todo porque es más rápido.

function fac(n){
    var r = 1,
        a = Array.apply(null, Array(n)).map(Number.call, Number).map(function(n){r = r * (n + 1);});
    return r;
}
Luka
fuente
1
¿Puedes explicar?
Mhmd
77
1 no es una función. Su código es así lento.
Pierre Arlaud
44
@ArlaudPierre r = -~(function(){})seguramente resolverá eso.
nitro2k01
44
Estoy en una máquina de trabajo, así que realmente no quiero instalar este idioma. ¿Dónde puedo encontrar una versión que se ejecutará en mi navegador?
joeytwiddle
3
Tengo un poco de miedo de usar Google porque mi jefe tiene una cuenta con ellos y no quiero que sepa que estoy jugando al golf en el trabajo. Estaba buscando una extensión para Firefox que pudiera ejecutar Javascript, pero parece que no puedo encontrar una. Algunos de mis amigos ejecutan Javascript en jsfiddle.net, pero eso está usando la electricidad de otra persona, que es un poco como robar. Mi madre dijo que no debería andar con gente así, pero ellos son mis amigos, ¿qué puedo hacer? De todos modos, a veces toma más crema de la que necesita. Gracias por los consejos, uso Ctrl-Shift-J o K en Firefox. Descargo de responsabilidad: # comentario-trolling
joeytwiddle
5

Usando Bogo-Sort en Java

public class Factorial {
    public static void main(String[] args) {
        //take the factorial of the integers from 0 to 7:
        for(int i = 0; i < 8; i++) {
            System.out.println(i + ": " + accurate_factorial(i));
        }
    }

    //takes the average over many tries
    public static long accurate_factorial(int n) {
        double sum = 0;
        for(int i = 0; i < 10000; i++) {
            sum += factorial(n);
        }
        return Math.round(sum / 10000);
    }

    public static long factorial(int n) {
        //n! = number of ways to sort n
        //bogo-sort has O(n!) time, a good approximation for n!
        //for best results, average over several passes

        //create the list {1, 2, ..., n}
        int[] list = new int[n];
        for(int i = 0; i < n; i++)
            list[i] = i;

        //mess up list once before we begin
        randomize(list);

        long guesses = 1;

        while(!isSorted(list)) {
            randomize(list);
            guesses++;
        }

        return guesses;
    }

    public static void randomize(int[] list) {
        for(int i = 0; i < list.length; i++) {
            int j = (int) (Math.random() * list.length);

            //super-efficient way of swapping 2 elements without temp variables
            if(i != j) {
                list[i] ^= list[j];
                list[j] ^= list[i];
                list[i] ^= list[j];
            }
        }
    }

    public static boolean isSorted(int[] list) {
        for(int i = 1; i < list.length; i++) {
            if(list[i - 1] > list[i])
                return false;
        }
        return true;
    }
}

Esto realmente funciona, muy lentamente, y no es preciso para números más altos.

James Hagborg
fuente
4

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?

#!/usr/bin/perl -w                                                              
use strict;
use bigint;
die "usage: f.perl N (outputs N!)" unless ($ARGV[0] > 1);
print STDOUT &main::rangeProduct(1,$ARGV[0])."\n";
sub main::rangeProduct {
    my($l, $h) = @_;
    return $l    if ($l==$h);
    return $l*$h if ($l==($h-1));
    # arghhh - multiplying more than 2 numbers at a time is too much work       
    # find the midpoint and split the work up :-)                               
    my $m = int(($h+$l)/2);
    my $pid = open(my $KID, "-|");
      if ($pid){ # parent                                                       
        my $X = &main::rangeProduct($l,$m);
        my $Y = <$KID>;
        chomp($Y);
        close($KID);
        die "kid failed" unless defined $Y;
        return $X*$Y;
      } else {
        # kid                                                                   
        print STDOUT &main::rangeProduct($m+1,$h)."\n";
        exit(0);
    }
}

Trolls:

  • bifurca los procesos O (log2 (N))
  • no comprueba cuántas CPU o núcleos tienes
  • Oculta muchas conversiones bigint / text que ocurren en cada proceso
  • Un bucle for suele ser más rápido que este código
Pablo
fuente
¡TIL que en perl ARGV[0]es en realidad el primer argumento y no el guión!
ThinkChaos
@plg Creo que $ 0 podría contener el nombre del archivo de script, pero eso no es lo mismo que $ ARGV [0]
Paul
Sí, eso es lo que leí. Me pareció sorprendente que en Perl no sea $ARGV[0]porque la mayoría de los idiomas que conozco un poco lo tienen allí
ThinkChaos
4

Pitón

Solo un algoritmo O (n! * N ^ 2) para encontrar el factorial. Caso base manejado. Sin desbordamientos.

def divide(n,i):
    res=0
    while n>=i:
         res+=1
         n=n-i
    return res

def isdivisible(n,numbers):
    for i in numbers:
         if n%i!=0:
             return 0
         n=divide(n,i)
    return 1

def factorial(n):
    res = 1
    if n==0: return 1 #Handling the base case
    while not isdivisible(res,range(1,n+1)):
         res+=1
    return res
Sudharsan Mohan
fuente
3

Bueno, hay una solución fácil en Golfscript. Puede usar un intérprete Golfscript y ejecutar este código:

.!+,1\{)}%{*}/

Fácil eh :) ¡Buena suerte!

Martijn Courteaux
fuente
2
No conozco GolfScript, pero este me decepciona ... Según los otros ejemplos de GolfScript en este sitio, habría esperado que la respuesta fuera!
Sr. Lister el
1
Ese es el operador de negación. 0 se convierte en 1 y todo lo demás se convierte en 0.
Martijn Courteaux
3

Mathematica

factorial[n_] := Length[Permutations[Table[k, {k, 1, n}]]]

No parece funcionar para números mayores que 11, y factorial [11] congeló mi computadora.

Stephen Montgomery-Smith
fuente
3

Rubí

f=->(n) { return 1 if n.zero?; t=0; t+=1 until t/n == f[n-1]; t }

La frase más lenta que puedo imaginar. Calcula 2 minutos en un procesador i7 6!.

reescrito
fuente
2

El enfoque correcto para estos problemas matemáticos difíciles es un DSL. Así que modelaré esto en términos de un lenguaje simple

data DSL b a = Var x (b -> a)
             | Mult DSL DSL (b -> a)
             | Plus DSL DSL (b -> a)
             | Const Integer (b -> a) 

Para escribir bien nuestro DSL, es útil verlo como una mónada gratuita generada por el functor algebraico

F X = X + F (DSL b (F X)) -- Informally define + to be the disjoint sum of two sets

Podríamos escribir esto en Haskell como

Free b a = Pure a
         | Free (DSL b (Free b a))

Dejaré al lector derivar la implementación trivial de

join   :: Free b (Free b a) -> Free b a
return :: a -> Free b a
liftF  :: DSL b a -> Free b a

Ahora podemos describir una operación para modelar un factorial en este DSL

factorial :: Integer -> Free Integer Integer
factorial 0 = liftF $ Const 1 id
factorial n = do
  fact' <- factorial (n - 1)
  liftF $ Mult fact' n id

Ahora que hemos modelado esto, solo necesitamos proporcionar una función de interpretación real para nuestra mónada libre.

denote :: Free Integer Integer -> Integer
denote (Pure a) = a
denote (Free (Const 0 rest)) = denote $ rest 0
...

Y dejaré el resto de la denotación al lector.

Para mejorar la legibilidad, a veces es útil presentar un AST concreto del formulario

data AST = ConstE Integer
         | PlusE AST AST
         | MultE AST AST

y luego a la derecha una reflexión trivial

reify :: Free b Integer -> AST

y luego es sencillo evaluar recursivamente el AST.

Daniel Gratzer
fuente
2

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 la factorialrutina y dividiremos internamente la cadena en sus dígitos para poder realizar la multiplicación.

Así que aquí está el código: la getDigitsfunció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 funciones increasey sean multiplymás simples). La increasefunción toma dicha lista y la aumenta en uno. Como su nombre lo indica, la multiplyfunció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 factorialfunción usa estas funciones auxiliares para calcular el factorial real, por ejemplo, factorial("9")da "362880"como salida.

import copy

def getDigits(n):
    digits = []
    for c in n:
        digits.append(ord(c) - ord('0'))

    digits.reverse()
    return digits

def increase(d):
    d[0] += 1
    i = 0
    while d[i] >= 10:
        if i == len(d)-1:
            d.append(0)

        d[i] -= 10
        d[i+1] += 1
        i += 1

def multiply(a, b):
    subs = [ ]
    s0 = [ ]
    for bi in b:

        s = copy.copy(s0)
        carry = 0
        for ai in a:
            m = ai * bi + carry
            s.append(m%10)
            carry = m//10

        if carry != 0:
            s.append(carry)

        subs.append(s)
        s0.append(0)

    done = False
    res = [ ]
    termsum = 0
    pos = 0
    while not done:
        found = False
        for s in subs:
            if pos < len(s):
                found = True
                termsum += s[pos]

        if not found:
            if termsum != 0:
                res.append(termsum%10)
                termsum = termsum//10
            done = True
        else:
            res.append(termsum%10)
            termsum = termsum//10
            pos += 1

    while termsum != 0:
        res.append(termsum%10)
        termsum = termsum//10

    return res

def factorial(x):
    if x.strip() == "0" or x.strip() == "1":
        return "1"

    factorial = [ 1 ]
    done = False
    number = [ 1 ]
    stopNumber = getDigits(x)
    while not done:
        if number == stopNumber:
            done = True

        factorial = multiply(factorial, number)
        increase(number)

    factorial.reverse()

    result = ""
    for c in factorial:
        result += chr(c + ord('0'))

    return result

print factorial("9")

Notas

En python, un número entero no tiene límite, por lo que si desea hacer esto manualmente, puede hacerlo

fac = 1
for i in range(2,n+1): 
    fac *= i

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.

brm
fuente
No hay límite en los números enteros en Python ... ¿verdad? Es posible que deba explicar esto mejor.
Riking
@Riking Sí, en Python no hay límite para los enteros. He agregado algunas notas para que quede más claro.
brm
2

Pitón

La solución más razonable es claramente verificar todos los números hasta encontrar el factorial del número dado.

print('Enter the number')
n=int(input())
x=1
while True:
    x+=1
    tempx=int(str(x))
    d=True
    for i in range(1, n+1):
        if tempx/i!=round(tempx/i):
            d=False
        else:
            tempx/=i
    if d:
        print(x)
        break
PygameNerd
fuente
2

La solución recursiva más elegante en C

Todos saben que las soluciones más elegantes para los factoriales son recursivas.

Factorial:

0! = 1
1! = 1
n! = n * (n - 1)!

Pero la multiplicación también puede definirse recursivamente como adiciones sucesivas.

Multiplicación:

n * 0 = 0
n * 1 = n
n * m = n + n * (m - 1)

Y también puede sumarse como incrementos sucesivos.

Adición:

n + 0 = n
n + 1 = (n + 1)
n + m = (n + 1) + (m - 1)

En C, podemos usar ++xy --xmanejar las primitivas (x + 1)y (x - 1)respectivamente, por lo que tenemos todo definido.

#include <stdlib.h>
#include <stdio.h>

// For more elegance, use T for the type
typedef unsigned long T;

// For even more elegance, functions are small enough to fit on one line

// Addition
T A(T n, T m) { return (m > 0)? A(++n, --m) : n; }

// Multiplication
T M(T n, T m) { return (m > 1)? A(n, M(n, --m)): (m? n: 0); }

// Factorial
T F(T n) { T m = n; return (m > 1)? M(n, F(--m)): 1; }

int main(int argc, char **argv)
{
    if (argc != 2)
        return 1;

    printf("%lu\n", F(atol(argv[1])));

    return 0;
}

Probémoslo:

$ ./factorial 0
1
$ ./factorial 1
1
$ ./factorial 2
2
$ ./factorial 3
6
$ ./factorial 4
24
$ ./factorial 5
120
$ ./factorial 6
720
$ ./factorial 7
5040
$ ./factorial 8
40320

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:

$ ./factorial 9

Hmm, te avisaré cuando vuelva ...


fuente
2

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!

def complicatedfactorial(n):
    def addby1(num):
        return num + 1
    def addnumbers(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addby1(cp2)
            b -= 1
    def multiply(a,b):
        copy = b
        cp2 = a
        while b != 0:
            cp2 = addnumbers(cp2,cp2)
    if n == 0:
        return 1
    else:
        return multiply(complicatedfactorial(n-1),n)

Creo que este código garantiza un error SO, porque

  1. La recursión lo calienta

  2. Cada capa genera llamadas para multiplicar

  3. que genera llamadas a addnumbers

  4. que genera llamadas a addby1!

Demasiadas funciones, ¿verdad?

Dan el hombre
fuente
1

TI-Basic 84

:yumtcInputdrtb@gmail And:cReturnbunchojunk@Yahoo A!op:sEnd:theemailaddressIS Crazy ANSWER LOL

Realmente funciona :)

Timtech
fuente
1

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:

$.alert=function(message){
    alert(message);
}$.factorial=function(number){
    alert(math.eval(number+"!"));
    return math.eval(number+"!");
}
$.factorial(10);
scrblnrd3
fuente
1

Pitón

Con solo una ligera modificación de la implementación factorial recursiva estándar, se vuelve intolerablemente lenta para n> 10.

def factorial(n):
    if n in (0, 1):
        return 1
    else:
        result = 0
        for i in range(n):
            result += factorial(n - 1)
        return result
dan04
fuente
1

Golpetazo

#! /bin/bash

function fact {
    if [[ ${1} -le 1 ]]; then
        return 1
    fi;

    fact $((${1} - 1))
    START=$(date +%s)
    for i in $(seq 1 $?); do sleep ${1}; done
    END=$(date +%s)
    RESULT=$(($END - $START))
    return $RESULT
}

fact ${1}
echo $?
alaroldai
fuente
1

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

def RandomPermutation(n) :           
    t = range(0,n)                   
    for i in xrange(n-1,0,-1):       
        x = t[i]                     
        r = randint(0,i)             
        t[i] = t[r]                  
        t[r] = x                     
    return t                         

def MonteCarloFactorial(n,c) :   
    a = 0                            
    b = 0                            
    t = RandomPermutation(n)         
    while a < c :                
        t2 = list(t)                 
        t = RandomPermutation(n)     
        if t == t2 :                 
            a += 1                   
        b += 1                       
    return round(b/c)            

MonteCarloFactorial(5,1000)
# returns an estimate of 5!
yo'
fuente
1

golpetazo

Los factoriales se determinan fácilmente con las conocidas herramientas de línea de comandos de bash.

read -p "Enter number: " $n
seq 1 $n | xargs echo | tr ' ' '*' | bc

Como @Aaron Davies mencionó en los comentarios, esto parece mucho más ordenado y todos queremos un programa agradable y ordenado, ¿no?

read -p "Enter number: " $n
seq 1 $n | paste -sd\* | bc
jippie
fuente
1
Recomiendo el pastecomando altamente subestimado :seq 1 $n | paste -sd\* | bc
Aaron Davies
2
@AaronDavies se pasteparece a una palabra inglesa normal y es fácil de recordar. ¿En verdad queremos eso? ; o)
jippie