Вступ
Погода чудова, а проводити годину в класі зовсім не хочеться.
Трохи роздратовані, ми заходимо до класу й помічаємо на дошці дивовижно приємну форму трикутника.
Чекаючи на вчителя математики, ми мимоволі помічаємо в трикутнику деякі закономірності: усі зовнішні значення дорівнюють одиниці, у кожному наступному рядку на одне значення більше, ніж у попередньому, а сам трикутник симетричний.
Дивно!
Невдовзі після того, як ми всідаємося, до класу заходить учитель і пояснює, що цей трикутник відомий як трикутник Паскаля.
Упродовж наступної години вчитель розкриває нам дивовижні речі, приховані в цьому трикутнику:
- Його можна використовувати, щоб обчислювати, скількома способами можна вибрати 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:
