Как ускорить циклы?

Question

Есть простая задача

суть заключается в том, что мальчик любит рисовать и надо помочь ему посчитать количество клеток которые он закрасит в зависимости от количества Елок. Вводные данные N Выходные данные площадь закрашенной поверхности Я сделал простоt решение на питоне:

N = 10000
b = 0
a = 0
for i in range(1, N+1):
    a += i*2+1
    for g in range(1, i+1):
        b += g*2
print(a+b)

но дело в том, что когда слшком большие числа такой код выполняется очень долго, как я могу его ускорить используя именно питон? Заранее благодарю за проявленный интерес.Желательно встроенными библиотеками, если они понадобятся.

Answer 1

По моему, здача не очень сложнА.

Смотрите.

Каждая следкющая ёлка образуется пририсовыванием к предыдущей "буквы Т" с "палочкой" размером 2N+1 и одной дополнительной клеткой внизу - "ножкой".

То есть,площадь следующей ёлки S(n) = S(n-1) + 2n+2.

| n | S(n) | SumS(n) |
----------------------
| 0 | 1    |         |
| 1 | 5    | 5       |
| 2 | 11   | 16      |
| 3 | 19   | 35      |
| 4 | 29   | 64      |

Вообще, выскажу смелое предположение, что S(n) = (n+1)**2 + n. Я не проверял, но похоже на правду.

А теперь мы всё можем посчитать за один цикл: в одной переменной считать площать очередной ёлки, в другой - накапливать сумму всех площадей.

Код нужен?

Вот он:

    N = 10000
    SumS = 0
    S = 1
    for i in range(1, N+1):
        S += 2*i+2
        SumS += S
    print(SumS)

Только проверьте, я всё таки из головы писал, без пайтона под рукой

Я вообще не понимаю как ваша формула работает. Что значит S(n-1)

S(n) - площадь n-той ёлки

в коде SumS - общая площадь всех ёлок.

А формула получается, если заметить следующую закономерность, нарисованную на картинке (грубо говоря, дорисовыванием чего следующая ёлка получается из предыдущей):

Answer 2

n = 10000
d = 5
sa = 5
for i in range(2, n+1):
    d = d + (2*i+2)
    sa += d
print(sa)

Использовав информацию @S.H., сделал такой код. Он намного быстрее моего старого.

PS если есть недочеты, буду непротив вашей критики.

Answer 3

Взглянем на картинку под другим углом зрения...
Возьмём для примера ёлку для числа 3:

Слева (красным) у нас получается арифметическая прогрессия 1,2,3. Её сумма будет: (1+n)/2*n.
Правая часть (жёлтая) - то же самое. Так что умножаем на 2: (1+n)/2*n * 2. Деление и умножение на 2 сокращаем: (1+n)*n.
Ствол (зелёный) - ни что иное как n*2 + 1. Прибавляем к предыдущему: (1+n)*n + n*2 + 1. 2n заносим под скобку, и...

Конечная формула площади одной ёлки: (3+n)*n + 1.

Теперь составим ещё одну последовательность, уже из этих формул:

(3 + 1)*1 + 1
(3 + 2)*2 + 1
(3 + 3)*3 + 1
(3 + 4)*4 + 1
...
(3 + n)*n + 1

Или если раскрыть скобки:

3*1 + 1*1 + 1
3*2 + 2*2 + 1
3*3 + 3*3 + 1
3*4 + 4*4 + 1
...
3*n + n*n + 1

Итого:

первый столбец: нужно посчитать сумму арифметической прогрессии 3*(1+2+3+...+n) = 3*(1+n)/2*n
второй столбец: сумму квадратов 1^2 + 2^2 + 3^2 + ... + n^2 = n*(n+1)*(2*n+1)/6
ну и в третьем столбце сумма равна n

3*(1+2+3+...+n) + (1^2+2^2+3^2+...+n^2) + n = 3*(1+n)/2*n + n*(n+1)*(2*n+1)/6 + n

Дальше выносим деление за скобки, группируем, раскрываем скобки:

(3*(1+n)/2*n*6 + n*(n+1)*(2*n+1)/6*6 + n*6)/6
(9*(1+n)*n + n*(n+1)*(2*n+1) + n*6)/6
((2*n+10)*(1+n)*n + n*6)/6
((2*n+10)*(n+n*n) + n*6)/6
(2*n*n + 10*n + 2*n*n*n + 10*n*n + n*6)/6
(2*(n**3) + 12*(n**2) + 16*n)/6

И получаем конечную формулу для суммы площадей всех ёлок.

((n**3) + 6*(n**2) + 8*n)/3

Упс. Забыл, что для решения задачи зачем-то должны быть использованы умения программирования на Питон. Ну да ладно... :)

БЛОГ НА HUSL

Как ускорить циклы?

Ответы (3 шт):