Plusieurs façons de calculer une factorielle en Python - Mathweb.fr (2024)

Nous allons voir sur cette page plusieurs manières de calculer une factorielle en Python.

Plusieurs façons de calculer une factorielle en Python - Mathweb.fr (1)

Python en mathématiques au lycée

Au menu sur cette page...

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):
k2345
F11×2 = 22×3 = 66×4 = 2424×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 FF = [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 !

Plusieurs façons de calculer une factorielle en Python - Mathweb.fr (2024)

References

Top Articles
Latest Posts
Article information

Author: Gregorio Kreiger

Last Updated:

Views: 5967

Rating: 4.7 / 5 (77 voted)

Reviews: 84% of readers found this page helpful

Author information

Name: Gregorio Kreiger

Birthday: 1994-12-18

Address: 89212 Tracey Ramp, Sunside, MT 08453-0951

Phone: +9014805370218

Job: Customer Designer

Hobby: Mountain biking, Orienteering, Hiking, Sewing, Backpacking, Mushroom hunting, Backpacking

Introduction: My name is Gregorio Kreiger, I am a tender, brainy, enthusiastic, combative, agreeable, gentle, gentle person who loves writing and wants to share my knowledge and understanding with you.