2

Есть простая задачаПример от 1 до 5

суть заключается в том, что мальчик любит рисовать и надо помочь ему посчитать количество клеток которые он закрасит в зависимости от количества Елок. Вводные данные 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)

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

4
  • 2
    Подумать над тем, можно ли данную реккурентную формулу превратить в обычную.
    – gbg
    14 окт 2021 в 12:55
  • 1
    Это при каких же N долго выполняется - порядка 10 000? А, ну да, я что-то слепой )) Я бы тупо в numba.njit обернул, если думать лениво.
    – CrazyElf
    14 окт 2021 в 12:58
  • это арифметическая прогрессия, решается одной формулой 14 окт 2021 в 13:02
  • Что такое numba.njut и что такое реккурентная формула? да именно после 10000 делается долго, но суть и была в том что ограничение по времени 1секунда. Типо олимпиадное задание. Я новичсок в программировании. Потому буду не против любой инфаормации @CrazyElf
    – Kynomi
    14 окт 2021 в 13:03

3 ответа 3

8

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

Смотрите.

Каждая следкющая ёлка образуется пририсовыванием к предыдущей "буквы Т" с "палочкой" размером 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 - общая площадь всех ёлок.

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

Следующая ёлка из предыдущей

13
  • Буду благодарен примеру кода, ибо пока что я не очень понял суть работы, сейачс вчитаюсь и попробую понять. Мышление реально хорошо, я новичок, рад любому опыту, и любым подсказкам. Спасибо вам
    – Kynomi
    14 окт 2021 в 13:05
  • 2
    не нужен цикл, для суммы членов прогрессии есть простая формула 14 окт 2021 в 13:05
  • 1
    да зачем ее выводить, она известна и есть почти везде, например, в первых строках википедии 14 окт 2021 в 13:09
  • 1
    А, сорян. Это прогрессия второго порядка. Тут действительно чуток посложнее. 14 окт 2021 в 13:13
  • 1
    Только я вижу тут обыкновенную арифметическую прогрессию? И элементарную формулу исходя из этого (3 + n)*n + 1.
    – GrAnd
    14 окт 2021 в 18:09
7

Взглянем на картинку под другим углом зрения...
Возьмём для примера ёлку для числа 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

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

3
  • шикарный ответ!!!
    – S.H.
    14 окт 2021 в 19:07
  • Благодарю, просто шикарный ответ. Это типо олимпиадное задание было и суть в том, что я не получил 20 баллов потому что с сильно большими числами программа выполнялась больше 1 секунды. Благодарю вас за столь подробное объяснение.
    – Kynomi
    15 окт 2021 в 0:08
  • @Kynomi Имея формулу, время вычисления становится константным О(1) и от n в принципе не зависящем. При программировании очень не лишен навык поиска оптимального алгоритма. Иногда в результате поиска, как в данном случае, и на программирование ничего не остаётся, собственно. :)
    – GrAnd
    15 окт 2021 в 0:18
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 если есть недочеты, буду непротив вашей критики.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.