Как стать автором
Обновить

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

Закрепленные Закреплённые комментарии

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

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

Да, S(n) = n^3

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

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

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)])

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

😅

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

Сочувствую

Насколько я могу судить, сложность этого алгоритма получилась 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)

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

Ответ, конечно, 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 ?

Ждали n**3

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

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

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

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

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

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

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

Уважаемый коллега, на мой взгляд, вы поделали над своим алгоримом прекрасную работу. Всё же, я полагаю ваше решение недостаточно функциональным, и не соответствующим нормам современного программирования. Кроме того, ваш алгоритм работает всего лишь за 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) видится мне вполне достойным.

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

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории