2 réponses
Le grand pb avec le calcul de la factorielle est lorsque n est très grand. tu peux utiliser listes chaînées pour stocker chacun des chiffres de chaque nombres allant de n à 1.
@julien2011
Lorsque l'on calcule n! la limite sur la taille de n pour obtenir un résultat correct dépend du type de retour de la fonction factorielle.
Mais pour les grandes valeurs de n il n'est pas nécessaire de passer par des listes chaînées car Java implémente déjà des calculs de grands nombres (BigInteger, et BigDecimal)
Le plus gros problème est d'adapter l'algorithme à ces grandes valeurs...
Prenons l'algorithme "naïf" qui calcule n! en faisant n*(n-1)!
Si on utilise l'implémentation récursive on va obtenir des StackOverflowError
Donc on utilisera plutôt l'algorithme itératif mais le temps va être très long...
Exemple d'exécutions avec des BigInteger :
StackOverflowError en récursif pour n>25 000
Temps d'exécution de 15 minutes en itératif pour n=500 000
Lorsque l'on calcule n! la limite sur la taille de n pour obtenir un résultat correct dépend du type de retour de la fonction factorielle.
int => n<12 long => n<22 float => n<34 double => n<170
Mais pour les grandes valeurs de n il n'est pas nécessaire de passer par des listes chaînées car Java implémente déjà des calculs de grands nombres (BigInteger, et BigDecimal)
Le plus gros problème est d'adapter l'algorithme à ces grandes valeurs...
Prenons l'algorithme "naïf" qui calcule n! en faisant n*(n-1)!
Si on utilise l'implémentation récursive on va obtenir des StackOverflowError
Donc on utilisera plutôt l'algorithme itératif mais le temps va être très long...
Exemple d'exécutions avec des BigInteger :
StackOverflowError en récursif pour n>25 000
Temps d'exécution de 15 minutes en itératif pour n=500 000