c++ - usando - Calcule el factorial de un número arbitrariamente grande, mostrando todos los dígitos

programa que muestre el factorial de un numero en c++

Question

Hace poco se me pidió, en una entrevista, que describiera un método para calcular el factorial de cualquier número arbitrariamente grande; un método en el que obtenemos todos los dígitos de la respuesta.

Busqué en varios lugares y pregunté en algunos foros. Pero me gustaría saber si hay alguna forma de lograr esto sin usar bibliotecas como GMP.

Gracias.

Answer 1

¡La biblioteca de Multiprecision de GNU es buena! Pero como dice que no se permite el uso de bibliotecas externas, lo único que creo que es posible es tomar una serie de números enteros y luego multiplicarlos como lo hace con el lápiz sobre papel.

Aquí está el código que escribí hace un tiempo ...

#include<iostream>
#include<cstring>

int max = 5000;

void display(int arr[]){
    int ctr = 0;
    for (int i=0; i<max; i++){
        if (!ctr && arr[i])         ctr = 1;
        if(ctr)
            std::cout<<arr[i];
    }
}


void factorial(int arr[], int n){
    if (!n) return;
    int carry = 0;
    for (int i=max-1; i>=0; --i){
        arr[i] = (arr[i] * n) + carry;
        carry = arr[i]/10;
        arr[i] %= 10;
    }
    factorial(arr,n-1);
}

int main(){
    int *arr = new int[max];
    std::memset(arr,0,max*sizeof(int));
    arr[max-1] = 1;
    int num;
    std::cout<<"Enter the number: ";
    std::cin>>num;
    std::cout<<"factorial of "<<num<<"is :/n";
    factorial(arr,num);
    display(arr);
    delete[] arr;
    return 0;
}

''arr'' es solo una matriz entera, y factorial es una función simple que multiplica el número dado por ''gran número''.

Espero que esto resuelva tu consulta ...

Answer 2

Bueno, tendrías que escribir tus propias rutinas matemáticas usando matrices. Eso es muy fácil de agregar, la multiplicación es un poco más difícil, pero aún es posible.

EDITAR: Quería publicar un ejemplo, pero el ejemplo de Srivatsan Iyer está bien.

Answer 3

Como todos votaron por Srivatsan, solo tengo una duda relacionada con el problema. ¿Necesita almacenar todos los dígitos? Si es así, entonces la solución de Srivatsan está bien. Si no, ¿por qué no solo mostrar los números, a medida que calcula el factorial? No estoy formateando la salida correctamente, pero esto podría servir para el propósito.

int factorial(int num)
{
   if (num <= 0)
      return 1;
   else
   {
      std::cout << num << std::endl;
      return num * factorial(num - 1);
   }
}

ACTUALIZACIÓN Para todos los downvoters, aunque esta publicación de 5 años, y la salida para factorial(3);

3
2
1
6 // this is the result of the factorial and the digits above are the ones all the digits in the calculation.

Pensé que esto es lo que pedí.

Answer 4

Eso es realmente bastante fácil. Aquí hay dos formas. Uno es exacto y el otro es una aproximación. Para cifras exactas, cualquier número superior a 10,000 tardará varios segundos en calcular. Aproximarlo tomará microsegundos, hasta que llegue a millones. Es la aproximación de Stirling si alguien está interesado.

Factorial de 10,000,000 es aproximadamente 1.2024234127436e + 65657059 Esto tomó 5.9 segundos. Encontrar la cantidad exacta tomaría 34 días.

<?php
$test= 3579;

echo ''Factorial of ''.$test.''<br><br>'';

$tm= microtime( true);

echo ''Exact ''.( $f= factorialexact( $test)).'' e+''.(strlen( $f)-1).'' missing decimal place after first digit<br>'';

echo ( microtime( true) - $tm). '' seconds<br><br>'';

$tm= microtime( true);

echo ''Aprox ''.factorialapprox( $test).''<br>'';

echo ( microtime( true) - $tm). '' seconds<br><br>'';


function factorialexact( $n){
    $f= ''1'';
    for ( $i=$n; $i>1; $i--){
        $f= JL_bcmul( $f, (''''.$i));
    }
    return $f;
}

function factorialapprox( $n){
    // Stirling''s factorial approximation
    // aprox factorial n = sqrt( 2 * pi * n) * n^n / e^n
    // store in t the easy part, calc the first term easily
    $t= sqrt( 2 * 3.14159265358979 * $n);
    // things get tough from here because for large n
    // n^n can blow away floating point pachages 
    // declare exponent of the number
    $e= 0;
    // the remaining terms are n^n / e^n
    // both n and e (natural log) are raised to the same power
    // that is n, just negative of each other
    for ( $i=0; $i<$n; $i++){
        // loop to 
        // mulitply by n and divide by e for each iteration
        $t= $t * $n / 2.71828182845904;
        // exponents are going to get away from us 
        // so reduce or increase t
        while ( $t>1000){
            $t= $t/1000;
            $e= $e+3;
        } 
        while ( $t<0.001){
            $t= $t*1000;
            $e= $e-3;
        } 
    }
    // garentee the base number is between 1 and 10
    while ( $t>=10){
        $t= $t/10;
        $e= $e+1;
    } 
    while ( $t<1){
        $t= $t*10;
        $e= $e-1;
    } 
    // return at a floating string.
    // do not use parseFloat() or floatval() 
    // $v= explode( ''e'', $result); $floatvalue= $v[0] * pow( 10, $v[1]);  
    // won''t work either.  $v[1] is way too large
    // the exponent can easily be in the tens of thousands
    $p= ''-'';
    if ( $e>=0){ $p= ''+''; }
    return $t.''e''.$p.$e;
}    

function JL_bcmul( $a, $b){
    if ( function_exists( ''bcmul'')){
        return bcmul( ( ''''.$a), (''''.$b));
    }
    $s= array();
    for ($i=0; $i < count( $a) + count( $b); $i++){ $s[$i]= ''0''; }
    $t= 0;
    for ($i=0; $i < strlen( $b); $i++){ 
        for ($j=0; $j < strlen( $a); $j++){
            $t= $s[$i+$j] + intval( $a[strlen( $a) - $j - 1]) * intval( $b[ strlen( $b) - $i - 1]); 
            $s[$i+$j]= $t % 10;
            $s[$i+$j+1]= $s[$i+$j+1] + floor( $t / 10);
        }
    }
    $s= array_reverse( $s);
    return trim( trim(( implode( '''', $s).''_''), ''0''), ''_'');
}

Answer 5

La respuesta aceptada está bien, pero esto es C ++; podemos hacerlo mejor. Comencemos con nuestra propia clase de Bignum , con una cantidad de dígitos totalmente ilimitada.

Para obtener la mayor eficiencia, trabajaríamos con números binarios puros, empacando cada elemento de la matriz con tantos bits como podamos manejar de manera eficiente. El enfoque más simple es almacenar un solo dígito decimal en cada elemento. Aquí he uint32_t un compromiso, almacenando 9 dígitos decimales en cada elemento uint32_t .

Los datos se almacenan en little-endian, ya que es mucho más fácil extender un vector al final cuando necesitamos elementos de orden superior.

Una vez que tenemos esta clase, la función factorial es la simplicidad misma.

#include <assert.h>
#include <iomanip>
#include <iostream>
#include <stdint.h>
#include <vector>

class Bignum
{
public:
    Bignum(int value)
    {
        assert(value >= 0 && value <= 999999999);
        parts.push_back(value);
    }

    Bignum& operator*=(int rhs)
    {
        assert(rhs >= 0 && rhs <= 999999999);
        uint32_t carry = 0;
        for (size_t i = 0; i < parts.size(); i++)
        {
            uint64_t product = (uint64_t)parts[i] * (uint64_t)rhs + carry;
            parts[i] = (uint32_t)(product % 1000000000LL);
            carry = (uint32_t)(product / 1000000000LL);
        }
        if (carry != 0)
            parts.push_back(carry);
        return *this;
    }

    friend std::ostream & operator<<(std::ostream& stream, const Bignum& num);

private:
    std::vector<uint32_t> parts;
};

inline std::ostream& operator<<(std::ostream& stream, const Bignum& num)
{
    char oldfill = stream.fill(''0'');
    for (std::vector<uint32_t>::const_reverse_iterator it = num.parts.rbegin(); it != num.parts.rend(); it++)
        stream << *it << std::setw(9);
    stream.fill(oldfill);
    stream.width(0);
    return stream;
}

Bignum factorial(int n)
{
    Bignum fac = 1;
    for (int i = 2; i <= n; i++)
        fac *= i;
    return fac;
}

int main(int argc, char* argv[])
{
    for (int n = 0; n <= 52; n++)
        std::cout << factorial(n) << std::endl;
    return 0;
}

Answer 6

Tengo una solución para calcular el factorial, que funciona bien para al menos n <= 15000. Factorial de 10000 se puede calcular en 1 segundo y para calcular el factorial lleva menos de 2 segundos. (Por supuesto, su pregunta no dice nada sobre las limitaciones de tiempo y estos tiempos dependen totalmente de la máquina). De todos modos, el concepto es bastante simple. Yo uso una matriz de caracteres. El primer caracter de la matriz es ''1''. Los LSB se almacenan desde el índice que comienza con 0. Una variable (m según mi programa) realiza un seguimiento de la longitud factorial. El valor final de m es el número de dígitos en el factorial y el elemento (m-1) th de la matriz de caracteres es MSB del factorial. A medida que el ciclo itera, los caracteres se agregan en el lado derecho de la matriz. Una variable ''c'' realiza un seguimiento del acarreo.

Los inconvenientes de usar la matriz se quedan en trozos de bytes no utilizados. Y más allá de cierto punto, no puede reservar espacio para una matriz. Además, las matrices tienden a ser lentas.

Puedes ver mi programa en ideone: http://ideone.com/K410n7

Creo que mi solución aún puede optimizarse. Por favor sugiero cómo.

include<stdio.h> 

char res[200000];

inline int fact(int n)
{

    int i,j;

    register int m,c;

    m=1;

    res[0]=''1'';

    for(i=2;i<=n;i++)
    {

        c=0;

        for(j=0; j< m; j++){

            c =((res[j]-48)*i)+c;

            res[j]=(c%10)+48;

            c=c/10;

        }
        while(c>0){
            res[m]=(c%10)+48;

            c=c/10;

            m++;

        }

    }

    return m;

}

int main() {


    int n,i,d;

    scanf("%d",&n);


    d=fact(n);

    for(i=d-1;i>=0;i--)

        printf("%c",res[i]);


    return 0;
}

Answer 7

Una buena solución de Srivatsan Iyer y mi sugerencia son:

1. Todavía se puede hacer más eficiente con la memoria mediante el uso de matriz de caracteres sin signo en lugar de utilizar la matriz int para almacenar dígitos. Llevará solo el 25% de la memoria necesaria a la de int array.

2. Para la mejor optimización de la memoria, también podemos usar un solo byte para representar 2 dígitos. Dado que solo 4 bits son suficientes para representar cualquier dígito de 0 a 9. Así que podemos empacar dos dígitos en un solo byte usando operaciones bit a bit. Tomará el 12.5% ​​de la memoria necesaria para la de int array.

Answer 8

Una clase BigInteger resolvería su problema, y ​​la implementación de C anterior le da una idea de cómo se implementaría BigInt, excepto que el código está optimizado para la velocidad y está hecho a la medida del factorial solamente.

Answer 9

#include <iostream>
using namespace std;
int main ()
{
    int i,n,p=1;
    cout<<"Enter a number: ";
    cin>>n;
    cout<<endl;

    for (i=1;i<=n; i++)
    {
        cout<<i<<" X "; 
        p=p*i;
    }
    cout<<endl<<endl<<p<<" factorial of "<<n;

    return 0;
}

Answer 10

#include<stdio.h>
#include<string.h>
char f[10000];
char factorial[1010][10000];
void multiply(int k){
    int ci,sum,i;
    int len = strlen(f);
    ci=0;
    i=0;
    while(i<len){
        sum=ci+(f[i] - ''0'') * k;
        f[i] = (sum % 10) + ''0'';
        i++;
        ci = sum/10;
    }
    while(ci>0){
        f[i++] = (ci%10) + ''0'';
        ci/=10;
    }
    f[i]=''/0'';
    for(int j=0;j<i;j++)factorial[k][j]=f[j];
    factorial[k][i]=''/0'';
}
void fac(){
    int k;
    strcpy(f,"1");
    for(k=2;k<=1000;k++)multiply(k);
}
void print(int n){
    int i;
    int len = strlen(factorial[n]);
    printf("%d!/n",n);
    for(i=len-1;i>=0;i--){
        printf("%c",factorial[n][i]);
    }
    printf("/n");
}
int main()
{
    int n;
    factorial[0][0]=''1'';
    factorial[1][0]=''1'';
    fac();
    while(scanf("%d",&n)==1){
        print(n);
    }
    return 0;
}