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

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 – ряд .

Алгоритм

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

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

  3. Посчитать сумму ряда .

Реализация

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

Сформировать ряд с вершины пирамиды по первый член 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 ?

Ресурсы