Посчитайте сумму 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
из массивов 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-ряд пирамиды
for i in range(prev_row[-1]+2, (prev_row[-1]+n*2)+2, 2):
n_row.append(i)
Этот цикл следует последовательно за предыдущем. В качестве нижней границы ряда передаем последний элемент prev_row,
сформированный на предыдущем шаге, и прибавляем к нему 2
. При
Итак, я получил 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 ?