Вступ
Погода чудова, і зовсім не хочеться проводити годину в класі. Трохи роздратовані, ми заходимо до класної кімнати й помічаємо на дошці трикутник, який чомусь приємно роздивлятися. Чекаючи на прихід учителя математики, ми мимоволі помічаємо в трикутнику деякі закономірності: зовнішні значення - самі одиниці, кожен наступний рядок має на одне значення більше за попередній, а сам трикутник симетричний. Дивно!
Тільки-но ми сідаємо, до класу заходить учитель і пояснює, що цей трикутник - відомий трикутник Паскаля.
Упродовж наступної години вчитель розкриває дивовижні речі, приховані в цьому трикутнику:
- За його допомогою можна обчислити, скільки є способів вибрати K елементів із N значень.
- У ньому є послідовність Фібоначчі.
- Якщо розфарбувати парні й непарні числа по-різному, отримаємо красиву закономірність під назвою трикутник Серпінського.
Учитель закликає нас і наших однокласників пошукати інші застосування й запевняє, що їх набагато більше! Саме тоді дзвенить шкільний дзвінок. Ми розуміємо, що останню годину були цілком захоплені вивченням трикутника Паскаля. Ми швидко виймаємо ноутбук із сумки, виходимо надвір, готові насолоджуватися і сонячним світлом, і дивовижами трикутника Паскаля.
Вказівки
Ваше завдання - вивести перші N рядків трикутника Паскаля.
Трикутник Паскаля - це трикутний масив додатних цілих чисел.
У трикутнику Паскаля кількість значень у рядку дорівнює номеру цього рядка (нумерація починається з одиниці).
Отже, у першому рядку одне значення, у другому - два, і так далі.
Перший (найверхніший) рядок має єдине значення: 1.
Значення наступних рядків обчислюються додаванням чисел безпосередньо праворуч і ліворуч від поточної позиції в попередньому рядку.
Якщо в попередньому рядку немає значення ліворуч або праворуч від поточної позиції (це буває лише для найлівішої та найправішої позицій), вважайте значення цієї позиції нулем (фактично «ігноруючи» його під час додавання).
Приклад
Розгляньмо перші 5 рядків трикутника Паскаля:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
У найверхнішому рядку одне значення, і воно дорівнює 1.
Для найлівішого та найправішого значень треба врахувати лише одну позицію в попередньому рядку: праворуч від нього для лівого краю і ліворуч від нього для правого краю.
Оскільки найверхніше значення дорівнює 1, з цього випливає, що всі найлівіші та найправіші значення теж дорівнюють 1.
У решти значень є дві позиції, які треба врахувати.
Наприклад, середнє значення пʼятого рядка (1 4 6 4 1) дорівнює 6, бо значення ліворуч і праворуч від нього в попередньому рядку - це 3 і 3:
