while - programa que calcule el factorial de un numero en java




Cálculo factorial de grandes números en C (10)

¿Alguna forma de manejar factorial de grandes números en C?

Como los factoriales pueden exceder rápidamente el rango de enteros estándar de ancho fijo e incluso tipos de punto flotante como el double , el Código debe considerar un tipo de usuario que permita una precisión de enteros ilimitada para una respuesta exacta .

Existen varias bibliotecas de precisión de enteros anchos, pero si el código necesita una solución simple, considere usar una cadena .

Lo siguiente no es rápido, ni tiene en cuenta los límites de las matrices, pero es ilustrativo de la idea. La conversión de '0'-'9' a / de 0-9 es un desperdicio, sin embargo, esto permite una fácil depuración paso a paso.

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

static char *strfact_mult(char *s, unsigned x) {
  unsigned sum = 0;
  size_t len = strlen(s);
  size_t i = len;
  while (i > 0) {
    sum += (s[--i] - '0') * x;
    s[i] = sum % 10 + '0';
    sum /= 10;
  }
  while (sum) {
    len++;
    memmove(&s[1], s, len);
    s[i] = sum % 10 + '0';
    sum /= 10;
  }
  return s;
}

char *str_fact(char *dest, unsigned n) {
  strcpy(dest, "1");
  while (n > 1) {
    strfact_mult(dest, n--);
  }
  return dest;
}

void test_fact(unsigned n) { 
  char s[1000];
  printf("%3u %s\n", n, str_fact(s, n));
}

int main(void) {
  test_fact(0);
  test_fact(4);
  test_fact(54);
  test_fact(100);
}

Salida

  0 1
  4 24
 54 230843697339241380472092742683027581083278564571807941132288000000000000
100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

En mi código C, quiero calcular el factorial para números en el rango de 1 a 100. Para números pequeños, la función funciona, pero para números más grandes, por ejemplo, 100! devuelve resultado incorrecto. ¿Alguna forma de manejar factorial de grandes números en C?. El compilador que estoy usando es gcc v4.3.3. Mi código es el siguiente:

#include <stdio.h>
#include <math.h>

double print_solution(int);

int main(void)
{
        int no_of_inputs,n ;

        int ctr = 1;

        scanf("%d",&no_of_inputs); //Read no of inputs

        do
        {
                scanf("%d",&n); //Read the input

                printf("%.0f\n",print_solution(n));

                ctr++;  

        }while(ctr <= no_of_inputs);


        return 0;       
}

double print_solution(int n)
{
        if(n == 0 || n == 1)
                return 1;
        else
                return n*print_solution(n-1);


}

Calcular grandes factoriales sin ninguna biblioteca externa

Es realmente un viejo problema. Veo la mayoría de las respuestas que sugieren una biblioteca externa o un resultado aproximado , que muestra una limitación de memoria. Pero, piense un poco diferente: ¡no siempre tiene que usar integer o double o unsigned long long en la programación para hacer matemáticas!

Utilicé int[] para calcular Big Factorials . Este pequeño código de Java puede (teóricamente) averiguar factorial de cualquier número :

public class BigFactorial {
    public static int[] calculateFactorial(int inputNumber) {
        int[] factorial = initializeFactorial(inputNumber);

        for(int i=inputNumber-1, j, k; i>0; i--){
            for(j=factorial.length-1, k=0; factorial[j] >= 0; j--){
                k += i*factorial[j];
                factorial[j] = k%10;
                k /= 10;
            }

            factorial[j] = k%10;
            k /= 10;
            factorial[j-1] = k;

            for(j=0; factorial[j]<1; j++){
                factorial[j] = -1;
            }
        }

        return factorial;
    }

    private static int[] initializeFactorial(int inputNumber){

        int digits = (int) Math.ceil(inputNumber*Math.log10(inputNumber/2))+2;
        int[] factorial = new int[digits+1];

        for(int i=0; i<factorial.length; i++){
            factorial[i] = -1;
        }

        for(int j=factorial.length-1, i=inputNumber; i>0; j--){
            factorial[j] = i%10;
            i /= 10;
        }

        return factorial;
    }

    public static void showOutput(int[] factorial){
        int i=0;
        while(factorial[i]<1){
            i++;
        }

        for(; i<factorial.length; i++){
            System.out.print(factorial[i]);
        }
    }

    ///test
    public static void main(String[] args) {
        int inputNumber = 5000;
        showOutput(calculateFactorial(inputNumber));
    }
}

100! = 933262154439441526816992388562667004907159682643816214685929 638952175999932299156089414639715651828625369792080022

No puedes representar un número tan grande con un int o un largo.


Además de los consejos de otros, sugiero que se familiaricen con los límites de almacenamiento de los tipos básicos (int, long, long long, ...) para cualquier computadora / plataforma que esté usando. ("En caso de duda, imprima más!")

Un póster anterior se refería a un límite de precisión de 80 bits, pero eso es particular a una CPU x86.

Otra persona citó ISO C90 varias veces, aunque C99 es el último estándar; incluso si muchos compiladores no han implementado completamente C99, es probable que encuentren que es muy probable que al menos tengan soporte por mucho tiempo, lo que debería corresponder a una precisión de> = 64 bits.


Ningún tipo de datos C estándar manejará con precisión números tan grandes como 100 !. Su única opción es usar aritmética de enteros de precisión arbitraria , ya sea a través de una biblioteca o por usted mismo.

Si esto es solo un proyecto de hobby, sugeriría intentarlo usted mismo. Es una especie de ejercicio divertido. Si esto está relacionado con el trabajo, use una biblioteca preexistente.

El tipo de datos C más grande que normalmente obtendrá es un entero de 64 bits. 100! es del orden de 10 157 , que toma la mayor parte de 500 bits para almacenar con precisión como un entero.


No use el algoritmo recursivo, creo que es super lento, incluso si se almacena en caché será lento. Esto es solo algo que deberías considerar.

La razón de esto es que cuando llama al hecho (100), en realidad no lo ejecuta 100 veces, en realidad ejecuta esa función 5050 veces. Lo que es malo, si se almacena en caché entonces podría ser 100 veces, sin embargo, aún es más lento ejecutar una llamada a la función con sentencias if luego ejecutar un bucle.

double print_solution(int n)
{
    double rval = 1;
    unsigned int i;

    for( i = 1; i <= n; i++ ) {
        rval *= i;
    }

    return rval;

}

Si usa aritmética de precisión arbitraria, podría hacerlo muy alto; sin embargo, necesita usar una biblioteca para hacerlo, o podría crear su propia biblioteca, pero eso llevaría mucho tiempo.


Puedes intentar usar el tipo "sin signo largo y largo", pero eso es lo máximo que puedes obtener con los tipos incorporados. Yo sugeriría (como cletus ya ha mencionado) ir con una implementación conocida de grandes números, o escribir uno mismo. "Es un buen ejercicio" x 2.


Si desea utilizar solo los tipos de datos estándar y no necesita la respuesta exacta, ¡calcule el logaritmo de n! en lugar de n! sí mismo. El logaritmo de n! cabe fácilmente en un double (a menos que n es enorme).


Supongo que eso se debe a que está desbordando el rango int, que es de hasta aprox. 2 billones. Puede obtener hasta 4 mil millones si usa int sin firmar, pero más allá de eso, tiene que usar la biblioteca bigint .


Todos te están diciendo la respuesta correcta, sin embargo, un par de puntos más.

  1. Su idea inicial de usar un doble para obtener un rango más amplio no funciona porque un doble no puede almacenar estos datos con precisión. Puede hacer los cálculos pero con mucho redondeo. Por eso existen las bibliotecas bigint.

  2. Sé que este es probablemente un ejemplo de un tutorial o sitio de ejemplos, pero hacer una recursión ilimitada lo morderá en algún momento. Usted tiene una solución recursiva para lo que es esencialmente un proceso iterativo. Comprenderá por qué este sitio se denomina como es cuando intenta ejecutar su programa con valores más grandes (Intente 10000).

Un enfoque iterativo simple es el siguiente

  int answer, idx;

  for (answer = 1, idx = 1; idx <= no_of_inputs; idx++ ) {
    answer = answer * idx;
  }
  printf("Factorial of %3d =  %d\n", no_of_inputs, answer);






algorithm