29.11.2022 11:49
cybran24 17 2700 Источник

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

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};

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

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

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

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

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

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

  • n_row – ряд x_n.

Алгоритм

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

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

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

Реализация

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

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

prev_row: list[int] = []

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

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

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

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

Итак, на данном шаге я получил z_3=1,3,5– последовательность, которая включает все ряды пирамиды до 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=3получаем x_1=5+2=7– первый член n-го ряда пирамиды. На следующей итерации: x_2=7+2=9, далее x_3=9+2=11– последний член ряда, так как 5+(3*2)=11.

Итак, я получил 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 ????

Ресурсы

Комментарии (17)


  1. just-a-dev
    29.11.2022 12:06
    #0
    +12

    n*n*n


  1. just-a-dev
    29.11.2022 12:06
    #24960460
    +12

    n*n*n


    1. petropavel
      29.11.2022 12:16
      #24960508
      +5

      не, ну это ж решение на собеседовании, надо оформить:

      def row_sum(n: int):
    return n*n*n


    1. sp17
      29.11.2022 12:29
      #24960556
      +1

      Да, S(n) = n^3


  1. ifilonov
    29.11.2022 12:11
    #24960486
    +4

    Задача сводится к тому, чтобы 2 раза посчитать суммы элементов арифметических последовательностей. Сумма для номера ряда даст сколько нечетных чисел от начала надо пропустить. Сумма для (номер ряда) чисел после пропущенных — уже ответ. На все про все O(1).


  1. lyagushkaa
    29.11.2022 12:20
    #24960524

    Думаю так будет выглядеть более компактно :)

    def row_sum(n: int):
    nrow_first_el = 1 + sum([i for i in range(0, n * 2, 2)])
    return sum([i for i in range(nrow_first_el, nrow_first_el + n * 2 - 1, 2)])


    1. lyagushkaa
      29.11.2022 12:21
      #24960534
      +1

      Ладно, n*n*n выглядит компактнее xDD


      1. cybran24 Автор
        29.11.2022 12:22
        #24960536

        ????


    1. Vova-Grib
      29.11.2022 12:48
      #24960646
      +2

      Ничего не понятно и читать невозможно.


      1. cybran24 Автор
        29.11.2022 12:48
        #24960648

        Сочувствую


  1. plFlok
    29.11.2022 12:34
    #24960578
    +3

    Насколько я могу судить, сложность этого алгоритма получилась O(n)

    Зависит от того, что Вы называете n. Если это номер ряда - то нет. Если это размер пирамиды - то да.

    если размазать пирамиду в один слой, то получим: 

    [1] [3 5] [7 9 11] [13 15 17 19] ...

    То есть вполне себе арифметическую прогрессию. Сумма ряда в ней - сумма фрагмента этой прогрессии. Осталось найти индексы элементов.

    Размер каждого слоя получается такой: 1, 2, 3, 4... - то есть тоже арифметическая прогрессия.

    Напомню формулу n-ного элемента прогрессии
    a_n= a_1 + d(n - 1)
    Где d - размер шага прогрессии. То есть 1.

    А сумма первых n элементов
    S = (a_1 + a_n) n / 2

    если подставить первую формулу во вторую, получим
    S = (2a_1 + d(n-1)) n / 2

    Итого, хотим индекс 4 ряда. Нам нужно знать сумму размеров предыдущих 3 рядов.
    S = (2*1 + 1 (3 - 1)) * 3 / 2 = 6.
    А конец нашего ряда имеет индекс
    S = (2* 1 + 1(4 - 1)) * 4 / 2 = 10.

    Итого возвращаемся к исходной последовательности.

    Нам нужна сумма первых 10 чисел минус сумма первых 6.
    S = (2 * 1 + 2 (10 - 1)) * 10 / 2 - (2 * 1 + 2 (6 - 1)) * 6 / 2 = 100 - 36 = 64.

    В результате задача решается за O(1), применив 3 формулы, зависящие от n. 

    function progressionSum(n, a1, d) {
	return (2 * a1 + d * (n -1 )) * n / 2
}

function sumNPyramidRow(n) {
  let prevIdx = n - 1;
  let fromIdx = progressionSum(prevIdx, 1, 1)
  let toIdx = progressionSum(n, 1, 1)
  return progressionSum(toIdx, 1, 2) - progressionSum(fromIdx, 1, 2)
}

    Решение за O(1)


    1. cybran24 Автор
      29.11.2022 12:40
      #24960604
      -1

      Спасибо! Конечно, n — это не номер ряда, передаваемый в функцию, а общее число итераций при образующейся последовательности.


  1. bvvbvv
    29.11.2022 12:36
    #24960588
    +3

    Ответ, конечно, n**3.
    Получаем его так:
    1. строки нумеруются с 1
    2. строка номер n начинается с числа n*n - n +1, в ней n чисел, значение последнего числа n*n - n +1 + (n - 1)*2
    3. Среднее значение числа в строке (n*n - n +1 + n*n - n +1 + (n - 1)*2)/2 = n**2
    4. Сумма в строке: n (чисел) * n**2 = n**3

    Ну и итог остался непонятным - задачу зачли или они ждали ответа n**3 ?


    1. cybran24 Автор
      29.11.2022 12:40
      #24960608

      Ждали n**3


    1. Alexandroppolus
      29.11.2022 12:56
      #24960688
      +2

      Я чуть по-другому решил:

      В пирамидке высотой n строк всего T(n) первых нечетных чисел, то есть их сумма равна

      T(n) ** 2 = (n(n+1)/2) ** 2

      где T(n) - n-ное треугольное число, а сумма нечетных - известный факт

      Вычитаем T(n) ** 2 - T(n-1) ** 2, выносим за скобки и сокращаем, выходит n**3


  1. grisha_lu
    29.11.2022 12:48
    #24960654
    +2

    sum(range(1, 999999999, 2)[int(n/2*(n-1)):int(n/2*(n-1))+n])

    Но вариант с n**3 куда прекрасней )


  1. celen
    29.11.2022 13:59
    #24961028
    +11

    Уважаемый коллега, на мой взгляд, вы поделали над своим алгоримом прекрасную работу. Всё же, я полагаю ваше решение недостаточно функциональным, и не соответствующим нормам современного программирования. Кроме того, ваш алгоритм работает всего лишь за O(n^2) - учитывая тяжелую ситуацию в экономике на данный момент, это слишком мало. Я вижу возможность реализации вашего алгоритма с гораздо большим временем работы, что, несомненно, будет вести к повышению спроса на более мощные компьютеры для решения вашей задачи, а, следовательно, ко всеобщей выгоде.

    Прежде всего, нам нужно понять, что такое нечетное число. Воспользуемя следующим определением:

    1. Единица - нечетное число

    2. Если к нечетному числу прибавить 2, мы получим следующее нечетное число.

    Таким образом, мы можем определить функцию n-ного нечетного числа в ряду нечетных натуральных чисел:

    def odd(x):
    assert x > 0 and type(x) == int and x != 'Фреди Крюгер' # с детства его боюсь и проверяю каждую переменную, что он в неё не прячется
    if x == 1:
        return 1
    else:
        return 2+odd(x-1)

    Теперь нам нужно суммировать все числа в строке n. Встает вопрос - сколько их, этих чесел? С помощью сложных математических выкладок с применением функционального анализа и интегрального исчисления, которые мы не будем приводить здесь, поскольку поля данного сайта слишком узки для них, мы получим, что число чисел в строке n есть n. n есть число чисел, которые нам нужно сложить, и число их есть n. n+1 число складывать не надо, как и n-1, если только после того мы не прибавим к ним ещё одно, и получим, что их n. И пировали люди... так, о чем это я.

    А, да. Нам нужно сложить n нечетных чисел. У нас уже есть способ определения нечетного числа нужного порядкового номера, написанный с применением высокой математики и функционального программирования. Теперь нужно определить порядковые номера этих чисел. Для этого напишем функцию определения порядковых номеров чисел в пирамиде. Рассмотрим пирамиду из натуральных чисел - порядковых номеров - внимательно:

        1
   2 3
  4 5 6
 7 8 9 10
   ...

    Обозначим функцию порядковых номеров за index(r, c), где r - номер строки, а c - номер диагонального столбца. К примеру, index(4, 2) = 8.

    Мы можем видеть, что:

    1. При c>1 index(r, c) = 1 + index(r, c-1)

    2. При r>1 index(r, 1) = 1 + index(r-1, r-1)

    3. index(1, 1) = 1

    (Предлагаю вам доказать эти наблюдения в качестве несложного домашнего задания)

    Таким образом, итоговый код выглядит так (если опустить все проверки на типы и Фреди Крюгера):

    def odd(x:int):
    if x == 1:
        return 1
    else:
        return 2+odd(x-1)

def index(r:int, c:int):
    if r == 1 and c == 1:
        return 1
    elif c > 1:
        return 1 + index(r, c-1)
    elif r > 1:
        return 1 + index(r-1, r-1)

def row_sum(n: int):
    return sum(map(lambda x: odd(index(n,x)),range(1,n+1)))

    Легко проверить, что на первых 44 строках (пока не будет достигнут предел рекурсии) функция row_sum выдаст 1, 8, 27, 64, 125..., что численно совпадает с вашим результатом.

    К сожалению, мне не удалось добиться экспоненциальности для данной реализации. Однако, достигнутый результат O(n^4) видится мне вполне достойным.


    1. cybran24 Автор
      29.11.2022 14:13
      #24961108
      +1

      Благодарю, ваш результат впечатляет! В целом код написан весьма элегантно. Помимо вашей сложности, отдельно отмечу ваши заслуги в достижении ограничения рекурсивных вызовов.