Introduction
Le temps est magnifique, et 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 noir une forme de triangle étrangement satisfaisante.
En attendant l'arrivée de ton prof de maths, tu ne peux pas t'empêcher de repérer quelques motifs dans ce triangle : les valeurs extérieures sont toutes égales à 1, chaque ligne suivante compte 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 prof entre dans la salle et t'explique que ce triangle est le célèbre triangle de Pascal.
Pendant l'heure qui suit, ton prof te dévoile quelques choses étonnantes cachées dans ce triangle :
- Il permet de calculer le nombre de façons de choisir K éléments parmi N valeurs.
- Il contient la suite de Fibonacci.
- Si tu colores les nombres pairs et impairs de façon différente, tu obtiens un magnifique motif appelé triangle de Sierpiński.
Ton prof t'encourage, toi et tes camarades, à chercher d'autres utilisations, et t'assure qu'il y en a plein 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'étude 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 :
