Factorielle
Fermé
haye.sidi
Messages postés
1
Date d'inscription
jeudi 24 février 2011
Statut
Membre
Dernière intervention
24 février 2011
-
Modifié par haye.sidi le 24/02/2011 à 01:04
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 25 févr. 2011 à 14:05
KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 - 25 févr. 2011 à 14:05
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.
KX
Messages postés
16753
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
25 novembre 2024
3 020
25 févr. 2011 à 14:05
25 févr. 2011 à 14:05
@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