Посчитайте сумму n-го ряда пирамиды нечетных чисел

Эта задача преследовала меня на двух интервью подряд, и я решил ее!

TL;DR

def row_sum(n: int):     prev_row: list[int] = []     n_row: list[int] = []      if n > 1:         for i in range(1,n*(n-1),2):             prev_row.append(i)          for i in range(prev_row[-1]+2, prev_row[-1]+(n*2)+2, 2):             n_row.append(i)     else:         n_row.append(n)      return sum(n_row)

Постановка задачи

Вообще, на интервью мне ничего толком не объясняли, а только показывали вот это:

     1     3 5    7 9 11  13 15 17 19 21 23 25 27 29

Я сформулировал условие задачи так (не сразу):

Существует конечная числовая последовательность $y_{n} = 2_n-1$ , в которой $y_{1}$ есть вершина пирамиды, а каждая нижележащая ступень есть ряд вида:

$x_n = \sum_{n=y_n}^{y_n+2n}y_{n-1}$ ;

Найти сумму ряда .

Иными словами, каждый ряд пирамиды есть подмножество всего ряда, составляющего пирамиду. Можно представить себе это как двумерный массив y длины n из массивов x длины y[i].

Разделяй и властвуй

Техника Divide-and-conquer – это известный шаблон проектирования алгоритмов. Его принцип заключается в рекурсивном разбиении задачи (набора данных) на меньшие подзадачи, которые достаточно малы (просты) чтобы решить их. Затем решения всех подзадач объединяются в конченое решение изначальной задачи.

В моем решении нет прямой рекурсии, но есть принцип разбиения набора данных. Я разделил последовательность на два списка:

prev_row – ряд $z_n = \sum_{n=1}^{n(n-1)}y_{n-1}$ – все числа с основания пирамиды до первого члена ряда .
n_row – ряд .

Алгоритм

Сформировать ряд – он нужен мне для того, чтобы выделить члены последовательности из последовательности .
Сформировать ряд , который содержит только члены n-го ряда пирамиды.
Посчитать сумму ряда .

Реализация

Не буду касаться всех нюансов своего кода, только основных.

Сформировать ряд с вершины пирамиды по первый член n-го ряда

prev_row: list[int] = []  for i in range(1,n*(n-1),2):     prev_row.append(i)

Список prev_row понадобится на следующем шаге формирования n-го ряда пирамиды. Он содержит нижнюю границу ряда в виде последнего элемента. Она же является верхней границей самого ряда .

Так как в задаче используется нечетная последовательность чисел, то я передаю 2 в качестве аргумента step функции range. Это означает, что при формировании последовательности начиная с 1, она прибавляет 2 к каждому предыдущему члену.

Предположим, что мы хотим получить сумму 3-го ряда пирамиды. В этом случае , так как цикл находится в функции, которая принимает порядковый номер ряда. На первой итерации получим , на второй , на третьей , а затем конец и выход из цикла, ведь аргумент n*(n-1)передается во второй параметр stop функции rangeи задает верхнюю границу последовательности: .

Итак, на данном шаге я получил – последовательность, которая включает все ряды пирамиды до n-ряда.

Сформировать n-ряд пирамиды

for i in range(prev_row[-1]+2, (prev_row[-1]+n*2)+2, 2):     n_row.append(i)

Этот цикл следует последовательно за предыдущем. В качестве нижней границы ряда передаем последний элемент prev_row,сформированный на предыдущем шаге, и прибавляем к нему 2. При получаем – первый член n-го ряда пирамиды. На следующей итерации: , далее – последний член ряда, так как .

Итак, я получил n-ряд пирамиды, дальше проще.

Посчитать сумму n-го ряда

return sum(n_row)

Так как в n_row хранятся члены исключительно n-го ряда, их сумму очень легко посчитать.

Листинг

def row_sum(n: int):     prev_row: list[int] = []     n_row: list[int] = []      if n > 1:         for i in range(1,n*(n-1),2):             prev_row.append(i)          for i in range(prev_row[-1]+2, prev_row[-1]+(n*2)+2, 2):             n_row.append(i)     else:         n_row.append(n)      return sum(n_row)

Послесловие

Насколько я могу судить, сложность этого алгоритма получилась O(n). Возможно, мой код не идеален, если вы так считаете, прошу написать свой вариант решения в комментариях. Было бы интересно посмотреть более мастерский вариант.

Понравилась статья?

Pro разработку

t.me

Мой канал в Telegram ?

Ресурсы

ссылка на оригинал статьи https://habr.com/ru/post/702162/