Comment imprimer le triangle de Pascal en Python

Ce guide vous expliquera comment réaliser l'affichage du triangle de Pascal en Python, en fonction d'un nombre de lignes spécifié.

Vous commencerez par découvrir la méthode de construction du triangle de Pascal. Ensuite, vous apprendrez à élaborer une fonction Python et à l'optimiser pour une meilleure performance.

▶️ Allons-y !

Le triangle de Pascal : Définition et construction

L'impression du triangle de Pascal pour un nombre de lignes donné est un exercice fréquemment rencontré lors des entretiens techniques.

Dans un triangle de Pascal de *n* lignes, la ligne *i* contient *i* éléments.

Ainsi, la première ligne comporte un seul élément, qui est 1. Chaque élément des lignes suivantes est obtenu par l'addition des deux nombres situés directement au-dessus de lui.

L'illustration ci-dessous détaille la construction d'un triangle de Pascal avec cinq lignes.

Triangle de Pascal pour numRows = 5 (Image de l'auteur)

Notez qu'il est possible de considérer des zéros lorsque seul un chiffre est présent au-dessus d'une position donnée.

📝À titre d'exercice, essayez de construire le triangle de Pascal pour *n* = 6 et *n* = 7 en suivant la même démarche.

Passons maintenant à la phase de codage. Vous pouvez exécuter les fragments de code directement dans l'environnement Python de toptips.fr, depuis votre navigateur, à mesure que vous progressez dans ce tutoriel.

Fonction Python pour l'affichage du triangle de Pascal

Dans cette partie, nous allons concevoir une fonction Python pour afficher le triangle de Pascal pour un nombre de lignes donné.

Deux questions clés doivent être abordées :

Comment déterminer les valeurs dans le triangle de Pascal ?
Comment organiser l'affichage du triangle de Pascal avec un espacement et une mise en forme adéquate ?

Voyons comment résoudre ces questions.

#1. Comment calculer chaque entrée du triangle de Pascal ?

Il s'avère que les entrées du triangle de Pascal peuvent être calculées en utilisant la formule des combinaisons *n*Cr. Pour rappel, *n*Cr représente le nombre de combinaisons possibles de *r* éléments dans un ensemble de *n* éléments.

La formule de *n*Cr est la suivante :

Formule nCr (Image de l'auteur)

Appliquons maintenant cette formule pour déterminer les entrées du triangle de Pascal.

Entrées du triangle de Pascal utilisant nCr (Image de l'auteur)

Nous avons maintenant une méthode pour calculer les éléments du triangle.

#2. Comment gérer l'espacement lors de l'affichage ?

Dans le triangle de Pascal avec *numRows*, la ligne #1 possède un élément, la ligne #2 en a deux, et ainsi de suite. Pour afficher le motif sous forme de triangle, il faudra prévoir *numRows - i* espaces sur la ligne #*i*. La fonction `range` de Python, combinée avec une boucle `for`, est parfaite pour cela.

Puisque la fonction `range` exclut la borne supérieure, assurez-vous d'ajouter + 1 pour obtenir le nombre exact d'espaces initiaux.

Maintenant que vous savez comment calculer les entrées et gérer l'espacement lors de l'affichage du triangle de Pascal, nous pouvons définir la fonction `pascal_tri`.

Analyse de la fonction

Que doit faire la fonction `pascal_tri` ?

Elle doit accepter le nombre de lignes (*numRows*) comme argument.
Elle doit afficher le triangle de Pascal avec *numRows* lignes.

Pour calculer la factorielle, nous allons utiliser la fonction `factorial` du module `math` intégré de Python.

▶️ Exécutez le code suivant pour importer la fonction `factorial`.

from math import factorial

Voici la définition de la fonction :

def pascal_tri(numRows):
  '''Afficher le triangle de Pascal avec numRows lignes.'''
  for i in range(numRows):
    # Boucle pour ajouter les espaces en début de ligne
	  for j in range(numRows-i+1):
		  print(end=" ")
    
    # Boucle pour obtenir les éléments de la ligne i
	  for j in range(i+1):
		  # nCr = n!/((n-r)!*r!)
		  print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")

	 # Aller à la ligne après chaque ligne
	  print("n")

Le fonctionnement de la fonction est le suivant :

La fonction `pascal_tri` prend en paramètre obligatoire *numRows* : le nombre de lignes.
Il y a *numRows* lignes au total. Pour chaque ligne *i*, nous ajoutons *numRows - i* espaces avant le premier élément.
Nous utilisons ensuite la formule *n*Cr pour calculer chaque élément. Pour la ligne *i*, les éléments sont *i*C*j* où *j* = {0,1,2,..,i}.
Notez que nous utilisons `//` qui effectue une division entière, car nous souhaitons obtenir des entiers.
Après avoir calculé tous les éléments d'une ligne, nous passons à la ligne suivante.

🔗 Puisque nous avons ajouté une chaîne de documentation, vous pouvez utiliser la fonction d'aide intégrée de Python ou l'attribut `__doc__` pour accéder à la documentation de la fonction. Voici comment procéder :

help(pascal_tri)

# Sortie
Help on function pascal_tri in module __main__:

pascal_tri(numRows)
    Afficher le triangle de Pascal avec numRows lignes.

pascal_tri.__doc__

# Sortie
Afficher le triangle de Pascal avec numRows lignes.

Appelons maintenant la fonction avec le nombre de lignes souhaité.

pascal_tri(3)

# Sortie
     1
    1 1
   1 2 1

Les 3 premières lignes du triangle de Pascal sont affichées, comme prévu.

Affichage du triangle de Pascal par récursivité

Dans la partie précédente, nous avons identifié la formule mathématique pour calculer chaque élément du triangle de Pascal. Cependant, nous n'avons pas exploité la relation entre les éléments de deux lignes consécutives.

En fait, nous avons utilisé la ligne précédente pour calculer les éléments de la ligne suivante. N'est-il pas possible d'utiliser cela pour une implémentation récursive de la fonction `pascal_tri` ?

Absolument ! C'est ce que nous allons faire.

Dans une approche récursive, une fonction s'appelle elle-même à plusieurs reprises, jusqu'à ce qu'elle atteigne un cas de base. Dans la construction du triangle de Pascal, nous commençons par la première ligne qui contient un 1, puis nous construisons les lignes suivantes.

L'appel de la fonction `pascal_tri(numRows)` va donc appeler `pascal_tri(numRows-1)` et ainsi de suite, jusqu'à ce que le cas de base `pascal_tri(1)` soit atteint.

Prenons l'exemple où nous devons afficher les 3 premières lignes du triangle de Pascal. L'image suivante montre comment les appels récursifs sont empilés et comment les appels de fonction renvoient les lignes du triangle de Pascal.

Pile d'appels lors d'appels récursifs (Image de l'auteur)

▶️ Exécutez le code ci-dessous pour générer les lignes du triangle de Pascal par récursivité.

def pascal_tri(numRows):
    '''Afficher le triangle de Pascal avec numRows lignes.'''
    if numRows == 1:
        return [[1]] # le cas de base est atteint !
    else:
        res_arr = pascal_tri(numRows-1) # appel récursif à pascal_tri
        # utilisation de la ligne précédente pour calculer la ligne actuelle
        cur_row = [1] # chaque ligne commence par 1
        prev_row = res_arr[-1] 
        for i in range(len(prev_row)-1):
            # somme des 2 entrées directement au-dessus
            cur_row.append(prev_row[i] + prev_row[i+1]) 
        cur_row += [1] # chaque ligne finit par 1
        res_arr.append(cur_row)
        return res_arr

Points importants à retenir :

Nous avons utilisé une liste de listes comme structure de données, où chaque ligne du triangle de Pascal est une liste : `[[ligne 1], [ligne 2],…,[ligne n]]`.
L'appel de fonction `pascal_tri(numRows)` déclenche une série d'appels récursifs avec *numRows - 1*, *numRows - 2* jusqu'à 1 comme arguments. Ces appels sont empilés.
Quand `numRows == 1`, nous atteignons le cas de base et la fonction retourne `[[1]]`.
La liste renvoyée est ensuite utilisée par les fonctions suivantes dans la pile d'appels pour calculer la ligne suivante.
Si `cur_row` est la ligne actuelle, alors `cur_row[i]` = `prev_row[i]` + `prev_row[i+1]` — la somme des deux éléments situés juste au-dessus de l'index courant.

Étant donné que le tableau renvoyé est une liste de listes, nous devons gérer l'espacement et afficher les éléments, comme le montre le code ci-dessous.

tri_array = pascal_tri(5)

for i,row in enumerate(tri_array):
  for j in range(len(tri_array) - i + 1):
    print(end=" ") # espaces en début de ligne
  for j in row:
    print(j, end=" ") # affichage des éléments
  print("n")  # passage à la ligne suivante

Le résultat est correct, comme on peut le voir ci-dessous !

Fonction Python pour afficher le triangle de Pascal avec numRows ≤ 5

Les deux méthodes que nous avons abordées peuvent servir à afficher le triangle de Pascal pour un nombre de lignes quelconque *numRows*.

Cependant, il existe des cas où nous devons afficher le triangle de Pascal pour un nombre de lignes plus petit. Lorsque le nombre de lignes que nous devons afficher est au maximum 5, nous pouvons utiliser une technique plus simple.

Examinez l'image ci-dessous. Remarquez comment les puissances de 11 correspondent aux valeurs du triangle de Pascal. Cette correspondance n'est valable que jusqu'à la puissance 4 de 11. Autrement dit, 11 élevé aux puissances {0, 1, 2, 3, 4} donne les entrées des lignes 1 à 5 du triangle de Pascal.

Réécrivons la définition de la fonction, comme indiqué ci-dessous :

def pascal_tri(numRows):
  '''Afficher le triangle de Pascal avec numRows lignes.'''
  for i in range(numRows):
    print(' '*(numRows-i), end='')
    # calcul de la puissance de 11
    print(' '.join(str(11**i)))

Voici comment fonctionne la fonction `pascal_tri` :

Comme dans les exemples précédents, nous gérons l'espacement.
Puis, nous utilisons l'opérateur d'exponentiation de Python (**) pour calculer les puissances de 11.
Les puissances de 11 étant par défaut des entiers, nous les convertissons en chaînes de caractères avec `str()`. Vous avez maintenant les puissances de 11 sous forme de chaînes.
Les chaînes de caractères en Python sont itérables, nous pouvons les parcourir et accéder à chaque caractère un par un.
Ensuite, nous utilisons la méthode `join()` avec la syntaxe : `~~.join()` pour concaténer les éléments de `` en utilisant `~~` comme séparateur.~~~~
Ici, nous avons besoin d'un seul espace entre les caractères, donc `~~` sera `' '`, `` est une chaîne : la puissance de 11.~~

Vérifions si la fonction fonctionne comme prévu.

pascal_tri(5)

# Sortie
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Pour un autre exemple, appelons la fonction `pascal_tri` avec 4 comme argument.

pascal_tri(4)

# Sortie
     1
    1 1
   1 2 1
  1 3 3 1

Vous savez maintenant comment afficher facilement le triangle de Pascal pour *numRows* compris entre 1 et 5.

Conclusion

Voici ce que nous avons appris :

Comment construire le triangle de Pascal avec un nombre de lignes donné. Chaque nombre dans une ligne est la somme des deux nombres directement au-dessus.
Comment écrire une fonction Python utilisant la formule *n*Cr = *n*!/(*n*-*r*)!. *r*! pour calculer les valeurs du triangle de Pascal.
Vous avez ensuite découvert une implémentation récursive de cette fonction.
Enfin, vous avez appris une méthode optimisée pour construire le triangle de Pascal pour *numRows* jusqu'à 5, en utilisant les puissances de 11.

Si vous souhaitez approfondir vos compétences en Python, apprenez à multiplier des matrices, à vérifier si un nombre est premier et à résoudre des problèmes sur les opérations sur les chaînes. Bon codage !