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 :
