Курс по Python: https://stepik.org/course/100707
На этом занятии мы с вами напишем
программу для построения треугольника Паскаля. Этот треугольник состоит из
особых чисел, которые вычисляются по правилу: по краям каждой строки стоят
единицы, а каждое из остальных чисел равно сумме двух стоящих над ним из предыдущей
строки. Именно в таком виде его привел французский математик Блез Паскаль в «Трактате
об арифметическом треугольнике». Популярность этого треугольника возникла из-за
того, что эти числа довольно часто встречаются в самых разных задачах
математики: алгебре, комбинаторике, теории вероятностей и многих других. Мы
сейчас не будем вдаваться в их анализ, так как перед нами стоит несколько
другая задача – написать программу формирования такого треугольника.
Первый вопрос,
на который, обычно, требуется ответить при разработке новой программы – как
хранить данные? В данном случае, как хранить эти числа? Я это сделаю с помощью
неравномерного вложенного списка. Смотрите, весь этот треугольник можно
представить как набор вложенных списков постоянно увеличивающейся длины:
P = [ [1],
[1, 1],
[1, 2, 1],
…
]
Далее, в
программе мы запишем два вложенных цикла for со счетчиками: i – для перебора
строк треугольника Паскаля; j – для перебора элементов формируемой
строки. Причем, j будет меняться в диапазоне [0; i]. То есть, для
первой строки принимает только одно значение 0, для второй – два значения [0;
1], для третьей – три [0; 1; 2] и так далее.
А формировать
значения строк будем следующим образом. Для каждой новой (i-й) строки мы
создадим список длиной i+1, состоящий из всех единиц:
Затем, все
крайние элементы с индексами:
j == 0 or j == i
мы трогать не
будем, так как там уже стоят нужные нам единицы. А все другие значения
формировать на основе суммы двух предыдущих:
row[j] = P[i-1][j-1] + P[i-1][j]
В итоге, всю
программу можно записать, так:
N = 7
P = []
for i in range(0, N):
row = [1] * (i + 1)
for j in range(i + 1):
if j != 0 and j != i:
row[j] = P[i-1][j-1] + P[i-1][j]
P.append(row)
for r in P:
print(r)
Мы вначале
определяем общее число строк, затем коллекцию P, которая будет
хранить значения треугольника Паскаля и, далее, вложенные циклы. Первый цикл со
счетчиком i перебирает
строки, а второй – со счетчиком j перебирает элементы текущей строки row. Внутри
вложенного цикла проверяем, если индекс j ссылается не на
крайние элементы строки, то формируем их значения на основе суммы двух чисел из
предыдущей строки. После этого добавляем строку в список P и проделываем
эту операцию N раз. В конце
программы выводим результат и давайте посмотрим, что у нас получится.
Как видите, у
нас сформировался треугольник Паскаля, состоящий из семи строк. Вот так, с
помощью вложенных циклов можно решить эту, относительно несложную задачку.
Опять же, все
программы, что я привожу на учебном курсе не являются истиной в последней
инстанции. У вас могут получаться другие программные реализации той же самой
задачи. Здесь главное помнить, что лучшая реализация будет та, которая
расходует меньше памяти и работает быстрее. Это два самых главных критерия
построения любых программ. Ну и, разумеется, программы должны приводить к
корректным результатам, иначе их можно считать неработоспособными.
Надеюсь, из
этого занятия вы хорошо себе представили, как можно запрограммировать задачу
формирования треугольника Паскаля с произвольным числом строк. Если здесь
никаких вопросов не возникает, то смело переходите к следующему уроку.
Курс по Python: https://stepik.org/course/100707