На codewars.com есть ката на 7 кю (кодирование) под названием Сумма нечетных чисел. Дан треугольник из нечетных чисел, начиная с 1, в первой строке 1 число, 1. Во второй строке 2 числа, 3 и 5. В третьей строке 3 числа, 7, 9 и 11. Итак, далее. Ката запрашивает функцию с 1 параметром n, который будет целым числом, чтобы вернуть сумму чисел в строке nᵗʰ. Итак, как бы вы решили это?
Мы замечаем, что в строке nᵗʰ есть n чисел, и первое число строки равно
Кодирование этого в рубине будет,
Это масштабируется линейно с n, поэтому выполняется n сложений. Это может быть проблемой, если n действительно огромное число. Итак, давайте попробуем другой подход.
Эта сумма, odd_num_tri(n), представляет собой следующую математическую сумму:
Слагаемое первой суммы можно вывести из суммирования, поскольку оно не зависит от индекса k. Суммирование 1 от 0 до n-1 раз равно сумме 1 n раз, что равно n. Итак, первая сумма равна
Вторая сумма немного интереснее. Согласно Википедии,
Это многообещающе. В этих двух суммах отсутствует только одно слагаемое, n.
Наконец, собрав все воедино,
Эта простая формула возводит основание в степень, которая равна постоянному времени по мере увеличения размера основания. Это огромное улучшение по сравнению с масштабированием с помощью n.
