Introduction
Comme il fait un temps magnifique, tu n'as pas vraiment envie de passer une heure dans une salle de classe.
Agacé, tu entres dans la salle et tu remarques sur le tableau une forme triangulaire étrangement satisfaisante.
Pendant que tu attends l'arrivée de ton professeur de mathématiques, tu ne peux pas t'empêcher de remarquer certains motifs dans le triangle : les valeurs extérieures sont toutes des 1, chaque ligne suivante contient une valeur de plus que la précédente, et le triangle est symétrique.
Bizarre !
Peu de temps après que tu t'es assis, ton professeur entre dans la salle et t'explique que ce triangle est le fameux triangle de Pascal.
Au cours de l'heure qui suit, ton professeur te révèle quelques choses étonnantes cachées dans ce triangle :
- Il permet de calculer de combien de façons on peut choisir K éléments parmi N valeurs.
- Il contient la suite de Fibonacci.
- Si on colore les nombres impairs et pairs différemment, on obtient un magnifique motif appelé le triangle de Sierpiński.
Le professeur t'implore, toi et tes camarades, de chercher d'autres utilisations, et t'assure qu'il y en a beaucoup d'autres !
C'est à ce moment-là que la cloche de l'école sonne.
Tu réalises que depuis une heure, tu étais complètement absorbé par l'apprentissage du triangle de Pascal.
Tu attrapes rapidement ton ordinateur portable dans ton sac et tu sors, prêt à profiter à la fois du soleil et des merveilles du triangle de Pascal.
Instructions
Ta tâche consiste à produire les N premières lignes du triangle de Pascal.
triangle de Pascal est un tableau triangulaire de nombres entiers positifs.
Dans le triangle de Pascal, le nombre de valeurs d'une ligne est égal à son numéro de ligne (qui commence à 1).
Par conséquent, la première ligne contient une valeur, la deuxième en contient deux, et ainsi de suite.
La première ligne (celle du haut) contient une seule valeur : 1.
Les valeurs des lignes suivantes s'obtiennent en additionnant les nombres directement à droite et à gauche de la position actuelle dans la ligne précédente.
Si la ligne précédente ne contient pas de valeur à gauche ou à droite de la position actuelle (ce qui n'arrive que pour les positions les plus à gauche et les plus à droite), considère la valeur de cette position comme zéro (ce qui revient à l'ignorer dans la somme).
Exemple
Voyons les 5 premières lignes du triangle de Pascal :
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
La ligne du haut contient une seule valeur, qui est 1.
Les valeurs les plus à gauche et les plus à droite n'ont qu'une seule position précédente à prendre en compte, à savoir la position située respectivement à leur droite et à leur gauche.
Comme la valeur du haut vaut 1, il en découle que toutes les valeurs les plus à gauche et les plus à droite valent aussi 1.
Les autres valeurs ont toutes deux positions à prendre en compte.
Par exemple, la valeur du milieu de la cinquième ligne (1 4 6 4 1) est 6, car les valeurs à sa gauche et à sa droite dans la ligne précédente sont 3 et 3 :
Cet exercice est conçu pour être résolu à l'aide de recursion, plutôt qu'avec des boucles.
Une fonction récursive est une fonction qui s'appelle elle-même, ce qui est utile pour résoudre des problèmes qui se définissent en termes d'eux-mêmes.
Pour éviter une récursion infinie (ou plus précisément, pour éviter de faire déborder la pile), on utilise ce qu'on appelle un « cas de base ».
Quand le cas de base est atteint, une valeur non récursive est renvoyée, ce qui permet à l'appel de fonction précédent de se résoudre et de renvoyer sa valeur, et ainsi de suite, en se propageant le long de la pile jusqu'à ce que le premier appel de fonction renvoie la réponse.
On pourrait écrire une fonction récursive pour calculer 5! (c'est-à-dire 5 * 4 * 3 * 2 * 1) comme ceci :
def factorial(number):
if number <= 1: # base case
return 1
return number * factorial(number - 1) # recursive case
print(factorial(5)) # returns 120
Enfin, il faut savoir que Python limite le nombre d'appels récursifs (1000 par défaut) et n'optimise pas la récursion terminale.
Messages d'exception
Il est parfois nécessaire de lever une exception.
Quand tu le fais, tu dois toujours inclure un message d'erreur explicite pour indiquer l'origine de l'erreur.
Cela rend le code plus lisible et aide grandement au débogage.
Dans les cas où tu sais que l'origine de l'erreur sera d'un certain type, tu peux choisir de lever l'un des types d'erreur intégrés, mais tu dois quand même inclure un message explicite.
Cet exercice en particulier exige que tu utilises l'instruction raise pour « lancer » plusieurs ValueErrors si un nombre négatif est passé à la fonction rows().
Les tests ne réussiront que si tu fais à la fois un raise de l'exception et que tu y ajoutes un message.
Pour lever une ValueError avec un message, écris le message comme argument du type exception :
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
