Цей підручник навчить вас друкувати трикутник Паскаля в Python для заданої кількості рядків.
Ви почнете з того, що навчитеся будувати трикутник Паскаля. Потім ви перейдете до написання функції Python і навчитеся її подальшої оптимізації.
▶️ Починаємо!
Що таке трикутник Паскаля і як його побудувати?
Надрукувати трикутник Паскаля для заданої кількості рядків є популярним питанням на співбесіді.
У трикутнику Паскаля з n рядків рядок номер i має i елементів.
Отже, у першому рядку є один елемент, і це 1. І кожен елемент у наступних рядках є сумою двох чисел безпосередньо над ним.
На наступному малюнку пояснюється, як побудувати трикутник Паскаля з п’ятьма рядками.
Трикутник Паскаля для numRows = 5 (Зображення автора)
Зверніть увагу, як можна додавати нулі, якщо над певним числом є лише одне число.
📝Як швидку вправу, виконайте описану вище процедуру, щоб побудувати трикутник Паскаля для n = 6 і n = 7.
Далі приступимо до написання коду. Ви можете запустити фрагменти коду в Python IDE techukraine.net прямо зі свого браузера — під час роботи з підручником.
Функція Python для друку трикутника Паскаля
У цьому розділі давайте напишемо функцію Python для друку трикутника Паскаля для будь-якої заданої кількості рядків.
Необхідно розглянути два ключових питання:
- Як виразити записи в трикутнику Паскаля?
- Як надрукувати трикутник Паскаля з відповідним інтервалом і форматуванням?
Давайте зараз відповімо на них.
#1. Який вираз для кожного запису в трикутнику Паскаля?
Так сталося, що записи в трикутнику Паскаля можна отримати за допомогою формули для nCr. Якщо ви пам’ятаєте зі шкільної математики, nCr позначає кількість способів, якими ви можете вибрати r елементів із набору з n елементів.
Формула для nCr наведена нижче:
Формула nCr (Зображення автора)
Тепер перейдемо до вираження записів у трикутнику Паскаля за допомогою формули nCr.
Записи трикутника Паскаля з використанням nCr (Зображення автора)
Тепер ми знайшли спосіб виразити записи в матриці.
#2. Як відрегулювати інтервал під час друку викрійки?
У трикутнику Паскаля з numRows рядок №1 має один запис, рядок №2 має два записи і так далі. Щоб надрукувати візерунок у вигляді трикутника, вам знадобиться numRows – i пробілів у рядку #i. І ви можете використовувати для цього функцію діапазону Python у поєднанні з циклом for.
Оскільки функція діапазону за замовчуванням виключає кінцеву точку, обов’язково додайте +1, щоб отримати потрібну кількість пробілів на початку.
Тепер, коли ви навчилися представляти записи, а також регулювати простір під час друку трикутника Паскаля, давайте визначимо функцію pascal_tri.
Розбір визначення функції
Отже, що ви хочете робити від функції pascal_tri?
- Функція pascal_tri повинна приймати кількість рядків (numRows) як аргумент.
- Він повинен надрукувати трикутник Паскаля з numRows.
Щоб обчислити факторіал, давайте скористаємося функцією факторіал із вбудованого математичного модуля Python.
▶️ Запустіть наступну комірку коду, щоб імпортувати факторіал і використовувати його у своєму поточному модулі.
from math import factorial
Наведений нижче фрагмент коду містить визначення функції.
def pascal_tri(numRows):
'''Print Pascal's triangle with numRows.'''
for i in range(numRows):
# loop to get leading spaces
for j in range(numRows-i+1):
print(end=" ")
# loop to get elements of row i
for j in range(i+1):
# nCr = n!/((n-r)!*r!)
print(factorial(i)//(factorial(j)*factorial(i-j)), end=" ")
# print each row in a new line
print("n")
Функція працює таким чином:
- Функція pascal_tri має один обов’язковий параметр numRows: кількість рядків.
- Усього рядків numRows. Для кожного рядка i ми додаємо numRows – i пробіли перед першим записом у рядку.
- Потім ми використовуємо формулу nCr для обчислення окремих записів. Для рядка i записами є iCj, де j = {0,1,2,..,i}.
- Зауважте, що ми використовуємо //, який виконує цілочисельне ділення, оскільки ми хотіли б, щоб записи були цілими числами.
- Після обчислення всіх записів у рядку надрукуйте наступний рядок у новому рядку.
🔗 Оскільки ми додали a рядок документації, ви можете скористатися вбудованою функцією довідки Python або атрибутом __doc__ для доступу до рядка документації функції. Наведений нижче фрагмент коду показує, як це зробити.
help(pascal_tri)
# Output
Help on function pascal_tri in module __main__:
pascal_tri(numRows)
Print Pascal's triangle with numRows.
pascal_tri.__doc__
# Output
Print Pascal's triangle with numRows.
Тепер давайте викличемо функцію з кількістю рядків як аргумент.
pascal_tri(3)
# Output
1
1 1
1 2 1
Перші 3 рядки трикутника Паскаля надруковані, як і очікувалося.
Вивести трикутник Паскаля за допомогою рекурсії
У попередньому розділі ми визначили математичний вираз кожного запису в трикутнику Паскаля. Однак ми не використовували зв’язок між записами в двох послідовних рядках.
Насправді ми використали попередній рядок для обчислення записів у наступному рядку. Чи можемо ми не використовувати це і придумати рекурсивну реалізацію функції pascal_tri?
Так, давайте зробимо це!
У рекурсивній реалізації функція неодноразово викликає сама себе, доки не буде знайдено базовий випадок. У побудові трикутника Паскаля ми починаємо з першого рядка з одним записом 1, а потім будуємо наступні рядки.
Отже, виклик функції pascal_tri(numRows) у свою чергу викликає pascal_tri(numRows-1) і так далі, доки не буде досягнуто базового випадку pascal_tri(1).
Розглянемо приклад, де потрібно надрукувати перші 3 рядки трикутника Паскаля. На наступному зображенні пояснюється, як рекурсивні виклики надсилаються в стек. І як рекурсивні виклики функції повертають рядки трикутника Паскаля.
Стек викликів під час рекурсивних викликів (Зображення автора)
▶️ Запустіть наведений нижче фрагмент коду, щоб рекурсивно згенерувати рядки трикутника Паскаля.
def pascal_tri(numRows):
'''Print Pascal's triangle with numRows.'''
if numRows == 1:
return [[1]] # base case is reached!
else:
res_arr = pascal_tri(numRows-1) # recursive call to pascal_tri
# use previous row to calculate current row
cur_row = [1] # every row starts with 1
prev_row = res_arr[-1]
for i in range(len(prev_row)-1):
# sum of 2 entries directly above
cur_row.append(prev_row[i] + prev_row[i+1])
cur_row += [1] # every row ends with 1
res_arr.append(cur_row)
return res_arr
Ось кілька моментів, на які варто звернути увагу:
- Ми використали вкладений список як структуру даних, де кожен рядок у трикутнику Паскаля сам по собі є списком, ось так: [[row 1], [row 2],…,[row n]].
- Виклик функції pascal_tri(numRows) запускає серію рекурсивних викликів із numRows – 1, numRows – 2 аж до 1 як аргументи. Ці виклики надсилаються в стек.
- Коли numRows == 1, ми досягли базового випадку, і функція повертає [[1]].
- Тепер отриманий список використовується наступними функціями в стеку викликів — для обчислення наступного рядка.
- Якщо cur_row є поточним рядком, cur_row[i] = попередній_ряд[i] + попередній_ряд[i+1]— сума 2 елементів безпосередньо над поточним індексом.
Оскільки повернутий масив є вкладеним списком (списком списків), нам потрібно налаштувати інтервали та роздрукувати записи, як показано в клітинці коду нижче.
tri_array = pascal_tri(5)
for i,row in enumerate(tri_array):
for j in range(len(tri_array) - i + 1):
print(end=" ") # leading spaces
for j in row:
print(j, end=" ") # print entries
print("n") # print new line
Результат правильний, як показано нижче!
# Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Функція Python для друку трикутника Паскаля для numRows ≤ 5
Обидва методи, про які ви дізналися, працюватимуть для друку трикутника Паскаля для довільної кількості рядків numRows.
Однак бувають випадки, коли потрібно надрукувати трикутник Паскаля для меншої кількості рядків. А коли кількість рядків, які вам потрібно надрукувати, становить не більше 5, ви можете використовувати просту техніку.
Перегляньте малюнок нижче. І подивіться, як степені числа 11 ідентичні записам у трикутнику Паскаля. Також зауважте, що це працює лише до 4-го степеня числа 11. Тобто 11, піднесене до степенів {0, 1, 2, 3, 4}, дає записи в рядках з 1 по 5 трикутника Паскаля.
Давайте перепишемо визначення функції, як показано нижче:
def pascal_tri(numRows):
'''Print Pascal's triangle with numRows.'''
for i in range(numRows):
print(' '*(numRows-i), end='')
# compute power of 11
print(' '.join(str(11**i)))
Ось як працює функція pascal_tri:
- Як і в попередніх прикладах, ми регулюємо інтервал.
- Потім ми використовуємо оператор піднесення до степеня Python (**), щоб обчислити степені числа 11.
- Оскільки степені 11 за замовчуванням є цілими числами, перетворіть їх у рядок за допомогою str(). Тепер у вас є повноваження 11 у вигляді рядків.
- Рядки в Python є ітерованими, тому ви можете прокручувати їх і отримувати доступ до одного символу за раз.
- Далі ви можете використати метод join() із синтаксисом:
.join( ), щоб об’єднати елементи в , використовуючи як роздільник. - Тут вам потрібен один пробіл між символами, тому
буде ‘ ‘, — рядок: ступінь 11.
Давайте перевіримо, чи функція працює належним чином.
pascal_tri(5)
# Output
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Як інший приклад, викличте функцію pascal_tri з 4 як аргументом.
pascal_tri(4)
# Output
1
1 1
1 2 1
1 3 3 1
Сподіваюся, ви знаєте, як легко надрукувати трикутник Паскаля для numRows у діапазоні від 1 до 5.
Висновок
Ось що ми дізналися:
- Як побудувати трикутник Паскаля із заданою кількістю рядків. Кожне число в кожному рядку є сумою двох чисел безпосередньо над ним.
- Напишіть функцію Python за формулою nCr = n!/(nr)!.r! обчислити елементи трикутника Паскаля.
- Потім ви навчилися рекурсивної реалізації функції.
- Нарешті ви навчилися найоптимальнішого методу побудови трикутника Паскаля для numRows до 5—використовуючи ступені 11.
Якщо ви хочете вдосконалити навички Python, навчіться множити матриці, перевіряти, чи число є простим, і розв’язувати задачі на операції з рядками. Щасливого кодування!