Эта задача преследовала меня на двух интервью подряд, и я решил ее!
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 из массивов x длины y[i].
Разделяй и властвуй
Техника Divide-and-conquer – это известный шаблон проектирования алгоритмов. Его принцип заключается в рекурсивном разбиении задачи (набора данных) на меньшие подзадачи, которые достаточно малы (просты) чтобы решить их. Затем решения всех подзадач объединяются в конченое решение изначальной задачи.
В моем решении нет прямой рекурсии, но есть принцип разбиения набора данных. Я разделил последовательность 
на два списка:
prev_row– ряд
– все числа с основания пирамиды до первого члена ряда 
. 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). Возможно, мой код не идеален, если вы так считаете, прошу написать свой вариант решения в комментариях. Было бы интересно посмотреть более мастерский вариант.
Понравилась статья?
Мой канал в Telegram 👆
