Треугольник Паскаля как пример работы вложенных циклов

Курс по 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, состоящий из всех единиц:

row = [1] * (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

Видео по теме