Minifets
@Minifets
Hello world!!!

Как оптимизировать сумму ряда?

Доброго времени суток, подскажите как можно оптимизировать алгоритм по подсчету ряда для больших значений k?
59fe09277fe53018373858.png
  • Вопрос задан
  • 293 просмотра
Решения вопроса 1
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Аналитически.
59fe144ebe173368222815.gif
Я нашёл этому поистине чудесное доказательство, но поле ввода слишком узко для него. (C) Ферма.
Решение
Рассмотрим дроби - слагаемые данной суммы. Очевидно, что знаменатели могут меняться от 2 до 2k.
Попробуем определить, какие числители будут в дробях со знаменателем n. Для этого нам надо разложить n на пары x и y всеми возможными способами, учитывая ограничения 1 ≤ x ≤ k, 1 ≤ y ≤ k и взять допустимые значения x.
Если 2 ≤ n ≤ k, то допустимыми значениями x будут 1 ... n-1. Для k+1 ≤ n ≤ 2k допустимыми значениями x будут n-k ... k. Таким образом, мы можем записать сумму числителей для каждого знаменателя:
59fef5831ed62261528289.png
Теперь, с учётом полученной системы запишем, как будет выглядеть полная сумма всех дробей:
59fef5c331774953483286.png
Заметим, что если в первой сумме начать суммирование не с 2, а с 1, то сумма не изменится, поскольку добавленное слагаемое равняется нулю. Во второй сумме перенесём k из пределов суммирования в слагаемое. Получим две суммы с одинаковыми пределами, а значит их можно объединить в одну:
59fef699cef72869621752.png
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
05 июн. 2020, в 15:07
1000 руб./за проект
05 июн. 2020, в 14:53
400 руб./в час
05 июн. 2020, в 14:40
1000 руб./за проект