Outils pour utilisateurs

Outils du site


factorielle

Calcul de factorielle

Rappel: factorielle de n = 1*2*3*4*…*(n-1)*n et par convention, factorielle de 0 = 1

Le calcul en Python est très intéressant, à cause de sa capacité à calculer avec des nombres entiers de précision limitée seulement par la mémoire de l'ordinateur.

1ère solution: version récursive

Le codage de la fonction est très simple, et ne nécessite pas plus de commentaires, à part que, comme c'est une version récursive, le programme s'appelle lui-même.

Le principe est très simple: si fact(5)=1*2*3*4*5 et fact(4)=1*2*3*4, vous voyez bien que fact(5)=5*fact(4).

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
###########################################################
def fact(n):
    """fact(n): calcule la factorielle de n (entier >= 0)"""
    if n<2:
        return 1
    else:
        return n*fact(n-1)
 
# Exemple d'utilisation:
print fact(50)  # => affiche 30414093201713378043612608166064768844377641568960512000000000000L

Restriction importante: au delà de 1000, vous allez avoir une erreur “RuntimeError: maximum recursion depth exceeded” parce que la pile de calcul sera dépassée. En effet, pour chaque valeur n, on appelle de nouveau la fonction fact(n-1) qui s'empile sur une pile qui a une taille limitée (=1000).

2ème solution: version non récursive

C'est la version que j'utilise, à cause de la pile limitée de Python (maxi = 1000).

Le codage de la fonction est très simple, et ne nécessite pas plus de commentaires:

#!/usr/bin/python
# -*- coding: utf-8 -*-
 
def fact(n):
    """fact(n): calcule la factorielle de n (entier >= 0)"""
    x=1
    for i in xrange(2,n+1):
        x*=i
    return x
 
# Exemple d'utilisation:
print fact(50)  # => affiche 30414093201713378043612608166064768844377641568960512000000000000L

Vous pouvez tester cette fonction avec la Calculext ici: http://calculext.jpvweb.com, mais soyez raisonnable: au delà de fact(5000), vous allez dépasser le temps maxi de calcul autorisé sur le serveur.

Une autre solution, plus inhabituelle, utilise la fonction Python “reduce”:

fact = lambda z : reduce(lambda x,y:x*y,range(1,z+1),1)

Ce qui donne, bien entendu, le même résultat, mais sans avantage de durée d'exécution.


Amusez-vous bien!

factorielle.txt · Dernière modification: 2009/06/14 09:14 par tyrtamos

Outils de la page