Nous allons voir sur cette page plusieurs manières de calculer une factorielle en Python.
https://www.mathweb.fr/euclide/produit/python-en-mathematiques-au-lycee/
Qu'est-ce qu'une factorielle du point de vue mathématique ?
Du point de vue mathématiques, la factorielle d’un entier naturel n est le produit noté n! tel que :\(n!=1\times2\times3\times4\times\cdots\times(n-1)\times n.\) Par exemple,
- \(5!=1\times2\times3\times4\times5\)
- \(2!=1\times2\)
- \(1!=1\)
- \(0!=1\) (par convention)
Python et factorielle: une approche naïve
À partir de la définition mathématique précédente, on peut imaginer une première approche d’un programme Python nous permettant de calculer une factorielle :
def factorielle(n):
if n == 0:
return 1
else:
F = 1
for k in range(2,n+1):
F = F * k
return F >>> factorielle(5)
120
Exécution pas à pas du programme
Que s’est-il passé ici pour voir ce résultat ?
- On appelle factorielle(5) :
- quand on entre dans la fonction factorielle, on teste avant tout si l’argument vaut 0, ce qui n’est pas le cas donc on passe à la ligne 5.
- On initialise alors une variable F à 1,
- puis on entre dans une boucle où la variable k varie de 2 à n.
- À chaque passage, la valeur contenue dans F est multipliée par k, ce qui donne (sous forme de tableau):
| k | – | 2 | 3 | 4 | 5 |
| F | 1 | 1×2 = 2 | 2×3 = 6 | 6×4 = 24 | 24×5 = 120 |
Le résultat final retourné est donc 120.
Python et factorielle: une approche récursive
On peut remarquer que si on pose :\(f(n)=n!\) alors,$$\begin{align}f(n+1)&=(n+1)!\\&=\underbrace{1\times2\times3\times\cdots\times n}_{=n!}\times(n+1)\\&=f(n) \times (n+1).\end{align}$$
On peut alors imaginer un deuxième programme légèrement différent du premier:
def factorielle(n):
if n == 0:
return 1
else:
return n * factorielle(n-1) C’est ce que l’on appelle la forme récursive du programme. On l’appelle ainsi car pour calculer la factorielle d’un entier n, on fait appel à la factorielle de l’entier précédent, à l’instar d’une suite récursive de la forme \(u_{n+1}=f(u_n)\).
Une variante avec la fonction lambda.
On peut légèrement simplifier la syntaxe précédente tout en gardant la forme récursive à l’aide de la fonction lambda de Python:
factorielle = lambda n: n * factorielle(n-1) if n != 0 else 1
Vous me croyez si vous voulez, mais je vous assure que cette simple ligne fait le même job que le programme précédent ! En mode console, on a:
>>> factorielle(7)
5040
Python et factorielle: en utilisant une liste
Maintenant que l’on sait calculer une factorielle, on pourrait créer une liste des premières valeurs, mais de façon intelligente tant qu’affaire. Ainsi, on ne va pas écrire:
F = [] for k in range(50): F.append( factorielle(k) )
Ben non… Et je suis sûr que vous voyez pourquoi…
Ben oui ! C’est tout de même ballot de faire toutes ces opérations à chaque fois que l’on veut calculer un terme de la liste.
Par exemple, pour le n-ième élément de la liste, on demande de calculer factorielle(n – 1), soit n – 2 multiplications, plus une multiplication par n, alors qu’il suffirait de multiplier l’élément précédent par (n – 1).
Autrement dit, ce programme nécessite: \(0+1+2+3+\cdots+n=\frac{n(n+1)}{2}\) multiplications (pour les connaisseurs, je ne parle pas de la complexité du programme, mais cette complexité est du même ordre de grandeur), soit un ordre de grandeur de \(\frac{n^2}{2}\) multiplications.
Il est donc préférable d’utiliser ce programme:
F = [1]
for k in range(1,50):
F.append( F[k-1] * k )
Ce programme est bien plus rapide pour les grandes valeurs de n car il ne nécessite que n produits (qui est bien moins grand que \(\frac{n^2}{2}\)).
Si l’on souhaite écrire une fonction, on pourra donc par exemple écrire ceci:
global F
F = [1]
def factorial(n):
if len(F) > n:
return F[n]
for k in range(len(F),n+1):
F.append( F[k-1] * k )
return F[n]
Le fait de déclarer la liste F en “global” permet de la garder en mémoire. Ainsi, lors du premier appel de la fonction factorial(n), toutes les factorielles sont calculées jusqu’à n!, mais lors du deuxième appel, si l’argument de la fonction est inférieur au premier n, il n’y a pas de calculs supplémentaires. Et si l’argument est supérieur à la première valeur de n, seules les factorielles qu’il reste à calculer le sont.
Python et factorielle: avec le module math
Bien entendu, il existe le module math, dédié aux fonctions mathématiques, dans lequel est déjà implémentée la fonction factorial.
Gardons en tête que toutes les fonctions de ce module sont écrites en langage C, et donc leur exécution est très rapide par rapport à ce que l’on peut implémenter en Python.
Et n’oubliez pas que si vous avez des problèmes en maths, je peux vous aider par webcam !
super !! je bricole avec Python depuis plus d’un an ,mais jamais eu l’occasion d’utiliser les factorielles .j’essaie d’écrire un programme de statistique
sur les courses de chevaux . je suis à la retraite et je m’éclate avec les classes,les méthodes mon livre de chevet : apprendre à programmer avec Python 3
de Gerard Swinnen .tres bon bouquin mais pas question de factorielle !!
par hasard je tombe sur un pb de factorielle
merçi encore
Les factorielles sont utilisées dans certains modules utiles. À chaque fois qu’il il a une opération de permutation de combinaison, etc., il y a de la factorielle. Il ne faut pas oublier que la performances d’un programme dépend des outils mathématiques utilisés pour le concevoir
Vu : 7!,! …8!! …!6 ..sur une vidéo de Youtube .ne sont pas mentionnés sur les calculatrices ( TI …)
Utilisations ???
Je ne comprends pas votre commentaire. Peut-être qu’en indiquant le lien de la vidéo Youtube, je comprendrais ce que vous demandez. Merci 🙂