Calcola il fattoriale di un numero arbitrariamente grande, mostrando tutte le cifre

Question

Mi è stato chiesto di recente, in un'intervista, di descrivere un metodo per calcolare il fattoriale di un qualsiasi numero arbitrariamente grande; un metodo in cui otteniamo tutte le cifre della risposta.

Ho cercato in vari posti e chiesto in alcuni forum. Ma mi piacerebbe sapere se c'è un modo per farlo senza usare librerie come GMP.

Grazie.

Answer 1

La libreria GNU Multiprecision è una buona soluzione! Ma dal momento che dici che l'uso di librerie esterne non è permesso, solo il modo in cui credo sia possibile, prendendo una serie di int e moltiplicando i numeri come fai con la penna su carta!

Ecco il codice che ho scritto qualche tempo fa ..

#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' è solo un array di interi, e fattoriale è una semplice funzione che moltiplica il numero dato al 'gran numero'.

Spero che questo risolve la query ..

classe

Answer 2

Bene, dovresti scrivere le tue routine matematiche utilizzando gli array. Questo è molto facile per l'aggiunta, la moltiplicazione è un po 'più difficile, ma ancora possibile.

EDIT: Volevo pubblicare un esempio, ma l'esempio di Srivatsan Iyer va bene.

Answer 3

Un BigInteger avrebbe risolto il problema, e l'implementazione C sopra vi dà un'idea di come un BigInt sarebbe stata attuata, se non che il codice è ottimizzato per la velocità e su misura per calcolare solo il fattoriale.

Answer 4

bella soluzione per Srivatsan Iyer e il mio suggerimento è:

1. Si può ancora essere reso più efficiente della memoria utilizzando unsigned array di caratteri piuttosto che utilizzare int array per le cifre dei negozi. Ci vorrà solo il 25% della memoria necessaria per l'array int.

2. Per ottimizzare la memoria, possiamo anche utilizzare un singolo byte per rappresentare 2 cifre. Poiché solo 4 bit sono sufficienti per rappresentare qualsiasi cifra da 0 a 9. Quindi possiamo impacchettare due cifre in un singolo byte utilizzando operazioni bit a bit. Ci vorrà il 12,5% della memoria necessaria a quella dell'array int.

Answer 5

Dal momento che tutti hanno votato per Srivatsan, ho solo un dubbio relativo al problema. Hai bisogno di memorizzare tutte le cifre? Se sì, allora la soluzione di Srivatsan va bene. In caso contrario, perché non visualizzare solo i numeri, come si calcola il fattoriale? Non sto formattando correttamente l'output, ma questo potrebbe servire allo scopo.

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

UPDATE Per tutte le downvoters, anche se questo 5 anni dopo, e l'uscita per 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. 

ho pensato che questo è quello che ha chiesto.

Answer 6

La risposta accettata va bene, ma questo è C++; possiamo fare di meglio Iniziamo con la nostra classe Bignum, con un numero di cifre totalmente illimitato.

Per la massima efficienza, lavoreremmo con numeri binari puri, impacchettando ogni elemento dell'array con tutti i bit che possiamo gestire in modo efficiente. L'approccio più semplice consiste nel memorizzare una singola cifra decimale in ciascun elemento. Qui sono andato per un compromesso, memorizzando 9 cifre decimali in ogni elemento uint32_t.

I dati vengono memorizzati little-endian, poiché è molto più semplice estendere uno vector alla fine quando sono necessari elementi di ordine superiore.

Una volta che abbiamo questa classe, la funzione fattoriale è la semplicità stessa.

#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 7

In realtà è piuttosto semplice. Qui ci sono due modi. Uno è esatto e uno è un'approssimazione. Per cifre esatte, qualsiasi numero superiore a 10.000 impiegherà più secondi per il calcolo. Approssimativamente ci vorranno microsecondi, fino a quando non entrerai in milioni. È l'approssimazione di Stirling se qualcuno è interessato.

Fattoriale di 10.000.000 è aprox 1.2024234127436e + 65657059 Ciò ha richiesto 5,9 secondi Trovare l'importo esatto richiederebbe 34 giorni.

<?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 8

ho una soluzione per il calcolo del fattoriale, che funziona bene per almeno n < = 15000. Il fattore di 10000 può essere calcolato in 1 secondo e quello per il calcolo del fattoriale richiede meno di 2 secondi. (Naturalmente la tua domanda non dice nulla sui limiti di tempo e questi tempi sono totalmente dipendenti dalla macchina). Ad ogni modo, il concetto è abbastanza semplice. Io uso un array di caratteri. Il primo carattere dell'array è '1'. Gli LSB vengono memorizzati dall'indice a partire da 0. Una variabile (m secondo il mio programma) tiene traccia della lunghezza fattoriale. Il valore finale di m è il numero di cifre nel fattoriale e l'elemento (m-1) th dell'array char è MSB del fattoriale. Mentre il ciclo itera, i caratteri vengono aggiunti nella parte destra dell'array. Una variabile "c" tiene traccia del carry.

Gli svantaggi dell'utilizzo dell'array sono costituiti da blocchi di byte inutilizzati. E oltre un certo punto, non è possibile riservare spazio per un array. Inoltre, gli array tendono a rallentare.

È possibile controllare il mio programma su Ideone: http://ideone.com/K410n7

credo che la mia soluzione può ancora essere ottimizzato. Si prega di suggerire come.

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 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; 
}