Ян (ahiin) wrote,
Ян
ahiin

Category:

Решение менее типичной задачи

Условие задачи здесь.

Первым задачу успешно решил уважаемый nabbla1, еще до того, как я опубликовал "точные" значения. Его объяснения я обильно цитирую ниже.

Так же не могу не отметить упорство son_0f_morning, который подошел к задаче с другой стороны и, таки, прорвался в итоге к решению.

Под катом само решение (теория) и несколько вариантов реализации.


Цитируя nabbla1:
"Внутри суммы прибавим и отнимем 1/k2:


Первые два слагаемых приведём к общему знаменателю, получая:


Зная, что сумма по 1/k2 даёт π2/6 и вынося x за знак суммы, получим:



эта сумма сходится существенно лучше, поскольку "хвост" пропорционален 1/k2, т.е возьмём в 10 раз больше слагаемых - в 100 раз выше точность.

"Прикинуть" точность можно по x = 1, поскольку нетрудно показать, что результатом должна стать единица:


При суммировании сократятся все слагаемые, кроме самого первого (=1) и самого последнего, стремящегося к нулю. "

Процитированное решение практически дословно повторяет мое собственное, далекого 2002 года, когда мне эта задача попалась на всероссийской олимпиаде по прикладной математике.

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

Подобный фокус: выделить некую "главную часть", посчитать аналитически, а оклонения от нее уже считать численно — исключительно полезен и встречается повсеместно, особенно в приложениях. Например, таким способом прекрасно берутся численно некоторые интегралы и т.п.

Очевидно, что с рядом можно проделать тот же фокус (и так много раз).

Пока мне не надоело, я успел получить следующее выражение:



Здесь — дзета-функция Римана, которая определяется следующим образом:


Нужные нам значения хорошо известны, есть в том числе в Википедии. Лично я воспользовался Вольфрамом, как заведомо более надежным источником.

Моя версия решения под спойлером.
[Код на C++]



На моей машине (Intel® Core™ i7-4720HQ) время счета составляет 8 микросекунд. До лимита в 10 секунд достаточно далеко, как видим.

Можно пойти и другим путем. son_0f_morning предложил несколько вариантов, о которых он сам расскажет при желании, здесь рассмотрим его решение, которое я зачел первым.

Оно базируется на следующей идее: при достаточно большом k, члены рядов и становятся практически неразличимы.

Таким образом, если взять n достаточно большим, получим:


Идея вполне годная, авторская реализация под спойлером.
[Код на C++]



Для языкового разнообразия, привожу так же вариант уважаемого alexis_m.
[Код на Python]


Tags: #include, математика, ответ к задачке, программирование, численные методы
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 5 comments