Comment imprimer le triangle de Pascal en Python

Ce tutoriel vous apprendra à imprimer Triangle de Pascal en Python pour un nombre donné de lignes.

Vous commencerez par apprendre à construire le triangle de Pascal. Vous procéderez ensuite à l'écriture d'une fonction Python et apprendrez à l'optimiser.

▶️ Commençons !

Qu'est-ce que le triangle de Pascal et comment le construire ?

Imprimer le triangle de Pascal pour un nombre donné de lignes est une question d'entretien courante.

Dans le triangle de Pascal avec n lignes, numéro de ligne i a i éléments.

La première ligne a donc un élément, qui est 1. Et chaque élément des lignes suivantes est la somme des deux nombres directement au-dessus il.

La figure suivante explique comment construire le triangle de Pascal avec cinq rangées.

pascal-triangle-python — Triangle de Pascal pour numRows = 5 (Image de l'auteur)

Remarquez que vous pouvez ajouter des zéros lorsque vous avez un seul numéro au-delà d'un certain nombre.

📝A titre d'exercice rapide, suivez la procédure ci-dessus pour construire le triangle de Pascal pour n = 6 et n = 7.

Ensuite, nous allons écrire du code. Vous pouvez choisir d'exécuter les extraits de code sur L'IDE Python de Geekflare directement à partir de votre navigateur - au fur et à mesure que vous avancez dans le tutoriel.

Fonction Python pour imprimer le triangle de Pascal

Dans cette section, nous allons écrire une fonction Python pour imprimer le triangle de Pascal pour un nombre donné de lignes.

Deux questions essentielles se posent :

Comment exprimer les entrées dans le triangle de Pascal ?
Comment imprimer le triangle de Pascal avec un espacement et un formatage appropriés ?

Répondons-y maintenant.

#1. Quelle est l'expression de chaque entrée du triangle de Pascal ?

Il se trouve que les entrées du triangle de Pascal peuvent être obtenues à l'aide de la formule de nCr. Si vous vous souvenez de vos mathématiques à l'école, nCr indique le nombre de possibilités de choix r à partir d'un ensemble de n articles.

La formule pour nCr est indiqué ci-dessous :

Procédons maintenant à l'expression des entrées du triangle de Pascal à l'aide de la formule nCr formule.

formule pascal-triangle-ncr-formule — Entrées du triangle de Pascal à l'aide de nCr (Image de l'auteur)

Nous avons maintenant trouvé un moyen d'exprimer les entrées de la matrice.

#2. Comment ajuster l'espacement lors de l'impression du modèle ?

Dans le triangle de Pascal avec numRowsLe rang #1 a une entrée, le rang #2 a deux entrées, et ainsi de suite. Pour imprimer le motif sous forme de triangle, vous aurez besoin de numRows - i dans la ligne #i. Et vous pouvez utiliser la fonction range en liaison avec la fonction for pour ce faire.

En tant que range exclut le point de terminaison par défaut, assurez-vous d'ajouter la fonction + 1 pour obtenir le nombre requis d'espaces en tête.

Maintenant que vous avez appris à représenter les entrées et à ajuster l'espace lors de l'impression du triangle de Pascal, allons-y et définissons la fonction pascal_tri.

Analyse de la définition de la fonction

Que voulez-vous que la fonction pascal_tri à faire ?

La fonction pascal_tri doit accepter le nombre de lignes (numRows) comme argument.
Il devrait imprimer le triangle de Pascal avec numRows.

Pour calculer la factorielle, nous utiliserons factorial de la fonction intégrée de Python math module.

▶️ Exécutez la cellule de code suivante pour importer factorial et l'utiliser dans votre module actuel.

from math import factorial

L'extrait de code ci-dessous contient la définition de la fonction.

def pascal_tri(numRows):
  '''Print Pascal's triangle with numRows.'''
  for i in range(numRows):
    # loop to get leading spaces
	  for j in range(numRows-i+1):
		  print(end=" ")
    
    # loop to get elements of row i
	  for j in range(i+1):
		  # nCr = n!/((n-r)!*r!)
		  print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")

	 # print each row in a new line
	  print("\n")

La fonction fonctionne comme suit :

La fonction pascal_tri a un paramètre obligatoire numRows: le nombre de lignes.
Il y a numRows rangées en tout. Pour chaque ligne i, nous ajoutons numRows - i les espaces précédant la première entrée de la ligne.
Nous utilisons ensuite nCr pour calculer les différentes entrées. Pour la ligne i, les entrées sont iCj où j = {0,1,2,..,i}.
Observez que nous utilisons // qui effectue une division entière, car nous souhaitons que les entrées soient des nombres entiers.
Après avoir calculé toutes les entrées d'une ligne, imprimer la ligne suivante sur une nouvelle ligne.

🔗 As we've added a chaîne de documentsvous pouvez utiliser la fonction intégrée de Python help ou la fonction __doc__ pour accéder à la docstring de la fonction. L'extrait de code ci-dessous montre comment procéder.

help(pascal_tri)

# Output
Help on function pascal_tri in module __main__:

pascal_tri(numRows)
    Print Pascal's triangle with numRows.

pascal_tri.__doc__

# Output
Print Pascal's triangle with numRows.

Appelons maintenant la fonction avec le nombre de lignes comme argument.

pascal_tri(3)

# Output
     1
    1 1
   1 2 1

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

Imprimer le triangle de Pascal à l'aide de la récursivité

Dans la section précédente, nous avons identifié l'expression mathématique de chaque entrée du triangle Pascal. Cependant, nous n'avons pas utilisé la relation entre les entrées de deux rangées consécutives.

En fait, nous avons utilisé la ligne précédente pour calculer les entrées de la ligne suivante. Ne pouvons-nous pas nous en servir pour trouver un récursif la mise en œuvre de la fonction pascal_tri?

Oui, faisons-le !

Dans un récursif Dans la mise en œuvre, une fonction s'appelle elle-même de façon répétée jusqu'à ce que la fonction cas de base est rencontrée. Dans la construction du triangle de Pascal, nous commençons par la première ligne avec une entrée 1puis construire les lignes suivantes.

L'appel à la fonction pascal_tri(numRows) appelle à son tour pascal_tri(numRows-1) et ainsi de suite, jusqu'au cas de base pascal_tri(1) est atteint.

Prenons l'exemple où vous devez imprimer les 3 premières lignes du triangle de Pascal. L'image suivante explique comment les appels récursifs sont poussés sur la pile. Et comment les appels de fonctions récursives renvoient les lignes du triangle de Pascal.

pascal-triangle-recursion — Pile d'appels lors d'appels récursifs (Image de l'auteur)

▶️ Exécutez l'extrait de code ci-dessous pour générer les lignes du triangle de Pascal de manière récursive.

def pascal_tri(numRows):
    '''Print Pascal's triangle with numRows.'''
    if numRows == 1:
        return [[1]] # base case is reached!
    else:
        res_arr = pascal_tri(numRows-1) # recursive call to pascal_tri
        # use previous row to calculate current row 
        cur_row = [1] # every row starts with 1
        prev_row = res_arr[-1] 
        for i in range(len(prev_row)-1):
            # sum of 2 entries directly above
            cur_row.append(prev_row[i] + prev_row[i+1]) 
        cur_row += [1] # every row ends with 1
        res_arr.append(cur_row)
        return res_arr

Voici quelques points qui méritent d'être soulignés :

Nous avons utilisé une liste imbriquée comme structure de données, où chaque ligne du triangle de Pascal est une liste en elle-même, comme ceci : [[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 placés sur une pile.
Quand numRows == 1nous avons atteint le cas de base et la fonction renvoie [[1]].
La liste renvoyée est alors utilisée par les fonctions suivantes de la pile d'appels pour calculer la ligne suivante.
Si cur_row est la ligne actuelle, cur_row[i] = prev_row[i] + prev_row[i+1]-la somme des 2 éléments directement supérieurs à l'indice actuel.

Comme le tableau retourné est une liste imbriquée (liste de listes), nous devons ajuster l'espacement et imprimer les entrées, comme le montre la cellule de 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=" ") # leading spaces
  for j in row:
    print(j, end=" ") # print entries
  print("\n")  # print new line

La sortie est correcte, comme on peut le voir ci-dessous !

Fonction Python pour imprimer le triangle de Pascal pour numRows ≤ 5

Les deux méthodes que vous avez apprises permettent d'imprimer le triangle de Pascal pour un nombre arbitraire de lignes numRows.

Cependant, il arrive que vous ayez besoin d'imprimer le triangle de Pascal pour un plus petit nombre de lignes. Et lorsque le nombre de lignes à imprimer est au maximum de 5, vous pouvez utiliser une technique simple.

Parcourez la figure ci-dessous. Observez comment les puissances de 11 sont identiques aux entrées du triangle de Pascal. Remarquez également que cela ne fonctionne que jusqu'à la quatrième puissance de 11, c'est-à-dire que 11 élevé aux puissances {0, 1, 2, 3, 4} donne les entrées des rangées 1 à 5 du triangle de Pascal.

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

def pascal_tri(numRows):
  '''Print Pascal's triangle with numRows.'''
  for i in range(numRows):
    print(' '*(numRows-i), end='')
    # compute power of 11
    print(' '.join(str(11**i)))

Voici comment la fonction pascal_tri œuvre :

Comme dans les exemples précédents, nous ajustons l'espacement.
Ensuite, nous utilisons l'opérateur d'exponentiation de Python (**) pour calculer les puissances de 11.
Comme les puissances de 11 sont des entiers par défaut, convertissez-les en chaînes de caractères à l'aide de str(). Vous avez maintenant les puissances de 11 sous forme de chaînes de caractères.
En Python, les chaînes de caractères sont des itérables, ce qui permet de les parcourir en boucle et d'accéder à un caractère à la fois.
Ensuite, vous pouvez utiliser la fonction join() avec la syntaxe : <sep>.join(<iterable>) pour joindre des éléments dans <iterable> en utilisant <sep> comme séparateur.
Ici, vous avez besoin d'un unique espace entre les caractères, de sorte que <sep> sera ' ', <iterable> est une chaîne de caractères : puissance de 11.

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

pascal_tri(5)

# Output
     1
    1 1
   1 2 1
  1 3 3 1
 1 4 6 4 1

Autre exemple : appelez la fonction pascal_tri avec 4 comme argument.

pascal_tri(4)

# Output
     1
    1 1
   1 2 1
  1 3 3 1

J'espère que vous comprenez comment vous pouvez facilement imprimer le triangle Pascal pour numRows dans une fourchette de 1 à 5.

Conclusion

Voici ce que nous avons appris :

Comment construire le triangle de Pascal avec le nombre de lignes donné. Chaque nombre de chaque rangée est la somme des deux nombres qui lui sont directement supérieurs.
Écrire une fonction Python utilisant la formule nCr = n!/(n-r) !.r ! pour calculer les entrées du triangle de Pascal.
Vous avez ensuite appris un mise en œuvre récursive de la fonction.
Enfin, vous avez appris la méthode la plus optimale pour construire le triangle de Pascal pour numRows jusqu'à 5 en utilisant le pouvoirs de 11.

Si vous souhaitez améliorer vos compétences en Python, apprenez à multiplier les matricesVérifier si un le nombre est premieret résoudre problèmes concernant les opérations sur les chaînes de caractères. Bon codage !