Комментарии 17
n*n*n
Думаю так будет выглядеть более компактно :)
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)])
Насколько я могу судить, сложность этого алгоритма получилась O(n)
Зависит от того, что Вы называете n. Если это номер ряда - то нет. Если это размер пирамиды - то да.
если размазать пирамиду в один слой, то получим:
[1] [3 5] [7 9 11] [13 15 17 19] ... То есть вполне себе арифметическую прогрессию. Сумма ряда в ней - сумма фрагмента этой прогрессии. Осталось найти индексы элементов.
Размер каждого слоя получается такой: 1, 2, 3, 4... - то есть тоже арифметическая прогрессия.
Напомню формулу n-ного элемента прогрессии
Где d - размер шага прогрессии. То есть 1.
А сумма первых n элементов 
если подставить первую формулу во вторую, получим
Итого, хотим индекс 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**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 ?
sum(range(1, 999999999, 2)[int(n/2*(n-1)):int(n/2*(n-1))+n])Но вариант с n**3 куда прекрасней )
Уважаемый коллега, на мой взгляд, вы поделали над своим алгоримом прекрасную работу. Всё же, я полагаю ваше решение недостаточно функциональным, и не соответствующим нормам современного программирования. Кроме того, ваш алгоритм работает всего лишь за O(n^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.
Мы можем видеть, что:
При c>1 index(r, c) = 1 + index(r, c-1)
При r>1 index(r, 1) = 1 + index(r-1, r-1)
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) видится мне вполне достойным.
Посчитайте сумму n-го ряда пирамиды нечетных чисел