Вступ
Погода чудова, і зовсім не хочеться проводити годину в класі. Трохи роздратовані, ми заходимо до класної кімнати й помічаємо на дошці трикутник, який чомусь приємно роздивлятися. Чекаючи на прихід учителя математики, ми мимоволі помічаємо в трикутнику деякі закономірності: зовнішні значення - самі одиниці, кожен наступний рядок має на одне значення більше за попередній, а сам трикутник симетричний. Дивно!
Тільки-но ми сідаємо, до класу заходить учитель і пояснює, що цей трикутник - відомий трикутник Паскаля.
Упродовж наступної години вчитель розкриває дивовижні речі, приховані в цьому трикутнику:
- За його допомогою можна обчислити, скільки є способів вибрати 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:
Як цю вправу реалізовано в Python: рекурсія
Цю вправу призначено для виконання з використанням recursion, а не циклів.
Рекурсивна функція - це функція, яка викликає саму себе. Це корисно під час розвʼязування задач, які визначені через самі себе.
Щоб уникнути нескінченної рекурсії (а точніше, щоб не переповнити стек), використовують так званий «базовий випадок».
Коли ми досягаємо базового випадку, повертається нерекурсивне значення, яке дозволяє попередньому виклику функції завершитися й повернути своє значення, і так далі, поки хвиля не прокотиться назад по стеку й перший виклик функції не поверне відповідь.
Ми могли б написати рекурсивну функцію, щоб знайти відповідь на 5! (тобто 5 * 4 * 3 * 2 * 1), ось так:
def factorial(number):
if number <= 1: # base case
return 1
return number * factorial(number - 1) # recursive case
print(factorial(5)) # returns 120
І насамкінець зауважимо, що Python обмежує кількість рекурсивних викликів (типово 1000) і не оптимізує хвостову рекурсію.
Повідомлення про винятки
Іноді буває потрібно порушити виняток.
Коли ми це робимо, слід завжди додавати змістовне повідомлення про помилку, яке вказує, у чому джерело помилки.
Це робить код читабельнішим і значно допомагає з налагодженням.
Якщо ми знаємо, що джерело помилки має певний тип, можна порушити один із вбудованих типів помилок, але все одно варто додати змістовне повідомлення.
У цій конкретній вправі потрібно використати інструкцію raise, щоб «кинути» кілька ValueError, якщо у функцію rows() передано відʼємне число.
Тести пройдуть лише за умови, що ми і порушимо exception, і додамо до нього повідомлення.
Щоб порушити ValueErrors з повідомленням, запишімо повідомлення як аргумент типу exception:
# if the rows function is passed a negative number.
raise ValueError("number of rows is negative")
