Calcolo di fattoriali grandi in C++

Question

Capisco che questo è un classico problema di programmazione e quindi voglio essere chiaro che non cerco codice come soluzione, ma apprezzerei una spinta nella giusta direzione. Sto imparando C++ e come parte del processo di apprendimento sto tentando alcuni problemi di programmazione. Sto tentando di scrivere un programma che si occupa di numeri fino a fattoriale di 1 miliardo. Ovviamente questi saranno numeri enormi e troppo grandi per poter gestire le normali operazioni aritmetiche. Qualsiasi indicazione su quale direzione dovrei andare nel cercare di risolvere questo tipo di problema sarebbe apprezzata.

Preferisco cercare di risolvere questo senza l'utilizzo di librerie aggiuntive, se possibile,

Grazie

PS - il problema è qui http://www.codechef.com/problems/FCTRL

---

Ecco il metodo che ho usato per risolvere il problema , questo è stato ottenuto leggendo i commenti seguenti:

Soluzione - Il numero 5 è un fattore primo di qualsiasi numero che termina in zero. Pertanto, dividendo il numero fattoriale per 5, in modo ricorsivo, e sommando i quozienti, si ottiene il numero di zeri finali nel risultato fattoriale

E.G. - Numero di zeri finali in 126! = 31

126/5 = 25 restante 1

25/5 = 5 restante 0

5/5 = 1 resto 0

25 + 5 + 1 = 31

Funziona per qualsiasi valore, continua a dividere fino a quando il quoziente è inferiore a rispetto a 5

Answer 1

scremato questa domanda, non so se ho davvero capito bene, ma qui è una supposizione deduttiva:

Prima domanda - come si ottiene uno zero su la fine del numero? Moltiplicando per 10.

Come si moltiplica per 10? moltiplicando per 10 o per 2 x 5 ...

Quindi, per X! quanti 10 e 2x5 hai ...?

(per fortuna 2 & 5 sono numeri primi)

Edit: Ecco un altro suggerimento - non penso che devi fare qualsiasi moltiplicazione. Fammi sapere se hai bisogno di un altro suggerimento.

Answer 2

Per iniziare, è necessario memorizzare il numero in una sorta di matrice come una d :: vector (una cifra per ogni posizione nell'array) e devi trovare un determinato algoritmo che calcoli un fattoriale (magari in una sorta di classe specializzata). ;)

Answer 3

È necessario un pacchetto "big number" - uno che si utilizza o uno che si scrive.

Suggerirei di fare qualche ricerca su "large number algorithms". Dovrai implementare l'equivalente C++ di Java BigDecimal.

Un altro modo di vederlo è utilizzare lo gamma function. Non è necessario moltiplicare tutti questi valori per ottenere la risposta giusta.

Answer 4

Suggerimento: potrebbe non essere necessario calcolare N! per trovare il numero di zeri alla fine di N!

Answer 5

Questa non è una buona risposta alla tua domanda poiché l'hai modificata un po 'da quello che ho letto in origine. Ma lo lascerò comunque qui per dimostrare l'impraticabilità di cercare effettivamente di fare i calcoli con la forza bruta principale.

Un miliardo di fattoriali sarà fuori dalla portata di qualsiasi libreria bignum. Tali numeri richiederanno più spazio per rappresentare di quanto quasi nessuno abbia nella RAM. Dovrai iniziare a cercare i numeri dalla memoria mentre lavori su di loro. Ci sono modi per farlo.Il guy who recently calculated π out to 2700 billion places usato una tale libreria

Answer 6

Per risolvere questa domanda, come Chris Johnson ha detto che devi guardare il numero di 0.

I fattori di 10 saranno 1,2,5,10. Quindi, puoi esaminare ciascuno dei numeri di N! e scriverli in termini di 2^x * 5^y * 10^z. Scarta altri fattori dei numeri.

Ora la risposta sarà maggiore di (x, y) + z.

Una cosa interessante che apprendo da questa domanda è che è sempre meglio memorizzare un numero in termini di fattori primi per facili confronti.

In realtà x^y, esiste un metodo semplice utilizzato nell'algoritmo RSA, che non si ricorda. Cercherò di aggiornare il post se trovo uno.

Answer 7

Non utilizzare il metodo naive. Se è necessario calcolare il fattoriale, utilizzare un algoritmo veloce: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Answer 8

Penso che dovresti trovare un modo per risolvere il problema in pseudo codice prima di iniziare a pensare a C++ oa qualsiasi altro linguaggio. La natura della domanda, come alcuni hanno sottolineato, è più un problema di algoritmo che un problema di C++. Coloro che suggeriscono di cercare qualche biblioteca oscura ti stanno indirizzando verso un pendio scivoloso, perché imparare a programmare è imparare a pensare, giusto? Trova un buon testo di analisi algoritmica e ti sarà utile. Nel nostro dipartimento insegniamo dal testo CLRS.

Answer 9

Per calcolare grande fattoriale, è possibile utilizzare questo codice in C++:

#include<iostream> 
using namespace std; 

long double factorial(int n); 

int main() 
{ 
    int n; 

    cout << "Enter a positive integer: "; 
    cin >> n; 

    cout << "Factorial of " << n << " = " << factorial(n); 

    return 0; 
} 

long double factorial(int n) 
{ 
    if(n > 1) 
     return n * factorial(n - 1); 
    else 
     return 1; 
} 

Come il lungo doppio detiene dati di grandi dimensioni 1.7E +/- 308, questo codice può davvero funzionare bene !!