usando - programa para calcular el factorial en c++
Cálculo factorial de grandes números en C (15)
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);
}
¿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
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 factorial es enorme, para ser precisos es 93326215443944152681699238856666700490715968264381621468592963895217 5999932299156089414639761500000000000000000000000000002020
Tal vez deberías usar una biblioteca bignum como GMP . Tiene documentos agradables, una interfaz bastante consistente, velocidad y si estás en Linux tu distro probablemente tiene un paquete (creo que el mío lo instala por defecto)
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.
Esto es sin duda debido al desbordamiento. Necesita una forma de representar números grandes ( unsigned long long ni siquiera cubrirá hasta 25).
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.
Para calcular aproximadamente factoriales de grandes números, puede ir de esta manera:
n! = n * (n-1)! so log(n!) = log(n) + log(n-1!)
Ahora puede usar la programación dinámica para calcular el registro (n!) Y calcular
¡norte! como (base) ^ (valor logarítmico)
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).
Si no desea utilizar una biblioteca bigint, lo mejor que puede hacer con stdlib es usar long double y tgammal() de math.h :
long double fact(unsigned n)
{
return tgammal(n + 1);
}
¡Esto te dará 100! con una precisión de 18 decimales en x86 (es decir, long double bit de 80 bit).
Una implementación exacta tampoco es tan complicada:
#include <math.h>
#include <stdio.h>
#include <string.h>
void multd(char * s, size_t len, unsigned n)
{
unsigned values[len];
memset(values, 0, sizeof(unsigned) * len);
for(size_t i = len; i--; )
{
unsigned x = values[i] + (s[i] - ''0'') * n;
s[i] = ''0'' + x % 10;
if(i) values[i - 1] += x / 10;
}
}
void factd(char * s, size_t len, unsigned n)
{
memset(s, ''0'', len - 1);
s[len - 1] = ''1'';
for(; n > 1; --n) multd(s, len, n);
}
int main(void)
{
unsigned n = 100;
size_t len = ceill(log10l(tgammal(n + 1)));
char dstr[len + 1];
dstr[len] = 0;
factd(dstr, len, n);
puts(dstr);
}
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.
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.
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);
esto es lo que hice para resolver un acertijo de Google hace algunos años, usa la biblioteca GMP GMP :
#include <stdio.h>
#include "gmp.h"
void fact(mpz_t r,int n){
unsigned int i;
mpz_t temp;
mpz_init(temp);
mpz_set_ui(r,1);
for(i=1;i<=n;i++){
mpz_set_ui(temp,i);
mpz_mul(r,r,temp);
}
mpz_clear(temp);
}
int main(void) {
mpz_t r;
mpz_init(r);
fact(r,188315);
/* fact(r,100); */
gmp_printf("%Zd/n",r);
mpz_clear(r);
return(0);
}
gcc -lgmp -o hecho fact.c
./hecho