Calcul de grands factoriels en C++

Question

Je comprends que c'est un problème de programmation classique et donc je veux être clair, je ne cherche pas de code comme une solution, mais j'apprécierais une poussée dans la bonne direction. J'apprends le C++ et, dans le cadre du processus d'apprentissage, j'essaie de résoudre certains problèmes de programmation. J'essaye d'écrire un programme qui traite des nombres jusqu'à la factorielle de 1 milliard. Évidemment, cela va être un nombre énorme et beaucoup trop grand pour faire face à des opérations arithmétiques normales. Toute indication quant à la direction que je devrais suivre pour essayer de résoudre ce type de problème serait appréciée.

Je préfère essayer de résoudre cela sans l'aide des bibliothèques supplémentaires si possible

Merci

PS - le problème est ici http://www.codechef.com/problems/FCTRL

---

est ici la méthode que j'utilisé pour résoudre le problème , ceci a été réalisé en lisant les commentaires ci-dessous:

Solution - Le nombre 5 est un facteur premier de tout nombre se terminant par zéro. Par conséquent, en divisant le nombre factoriel par 5, récursivement, et en ajoutant les quotients, vous obtenez le nombre de zéros fin dans le résultat factoriel

E.G. - Nombre de zéros à droite dans 126! = 31

126/5 = 25 reste 1

25/5 = 5 reste 0

5/5 = 1 reste 0

25 + 5 + 1 = 31

Cela fonctionne pour n'importe quelle valeur, continuez à diviser jusqu'à ce que le quotient soit moins que 5

Answer 1

effleurait ces questions, ne sais pas si je vraiment eu c'est juste, mais ici une supposition déductive:

Première question - comment obtenez-vous un zéro la fin du nombre? En multipliant par 10.

Comment multipliez-vous par 10? soit en multipliant par 10 ou par 2 x 5 ...

Donc, pour X! combien de 10s et 2x5s avez-vous ...?

(heureusement 2 & 5 sont des nombres premiers)

modifier: Voici un autre indice - Je ne pense pas que vous devez faire une multiplication. Faites-moi savoir si vous avez besoin d'un autre indice.

Answer 2

Pour commencer, vous devez stocker le nombre dans une sorte de tableau comme un d :: vector (un chiffre pour chaque position dans le tableau) et vous devez trouver un certain algorithme qui va calculer un factoriel (peut-être dans une sorte de classe spécialisée). ;)

Answer 3

Vous avez besoin d'un package "big number" - que ce soit un que vous utilisez ou que vous écrivez vous-même.

Je recommanderais de faire quelques recherches sur "large number algorithms". Vous devez implémenter l'équivalent C++ de Java BigDecimal.

Une autre façon de voir cela est d'utiliser le gamma function. Vous n'avez pas besoin de multiplier toutes ces valeurs pour obtenir la bonne réponse.

Answer 4

Indice: vous n'avez pas besoin de calculer N! afin de trouver le nombre de zéros à la fin de N!

Answer 5

Ceci n'est pas une bonne réponse à votre question car vous l'avez modifié un peu par rapport à ce que j'avais lu à l'origine. Mais je vais laisser ici de toute façon démontrer l'impossibilité d'essayer de faire les calculs par force brute principale.

Un milliard de factoriels va être hors de portée de n'importe quelle bibliothèque de bignum. De tels nombres exigeront plus d'espace pour représenter que presque n'importe qui a dans la RAM. Vous allez devoir commencer à paginer les numéros depuis le stockage pendant que vous travaillez dessus. Il y a des façons de le faire.Le guy who recently calculated π out to 2700 billion places utilisé une telle bibliothèque

Answer 6

Pour résoudre cette question, comme Chris Johnson a dit que vous devez regarder le nombre de 0.

Les facteurs de 10 seront 1,2,5,10 lui-même. Ainsi, vous pouvez passer en revue chacun des numéros de N! et écrivez-les en termes de 2^x * 5^y * 10^z. Jeter les autres facteurs des nombres.

Maintenant, la réponse sera greaterof (x, y) + z. Une chose intéressante que j'apprends de cette question est, il est toujours préférable de stocker factorielle d'un nombre en termes de facteurs premiers pour faciliter les comparaisons. Pour réellement x^y, il existe une méthode simple utilisée dans l'algorithme RSA, qui ne se souvient pas. Je vais essayer de mettre à jour le post si j'en trouve un.

Answer 7

N'utilisez pas la méthode naïve. Si vous devez calculer le factoriel, utilisez un algorithme rapide: http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

Answer 8

Je pense que vous devriez trouver un moyen de résoudre le problème en pseudo-code avant de commencer à penser à C++ ou à tout autre langage d'ailleurs. La nature de la question, comme certains l'ont souligné, est plus un problème d'algorithme qu'un problème C++. Ceux qui suggèrent de chercher une bibliothèque obscure vous pointent dans la direction d'une pente glissante, car apprendre à programmer c'est apprendre à penser, n'est-ce pas? Trouvez un bon texte d'analyse d'algorithme et cela vous servira bien. Dans notre département, nous enseignons à partir du texte CLRS.

Answer 9

Pour calculer grand factoriel, vous pouvez utiliser ce code en 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; 
} 

Comme long double détient de grandes données 1.7E +/- 308, ce code peut vraiment bien !! effectuer